一种应用于频繁子图查询的频繁子图索引方法及装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113722551A(43)申请公布日2021.11.30(21)申请号202111055107.2(22)申请日2021.09.09(71)申请人国网电子商务有限公司地址100053北京市西城区广安门内大街311号申请人国网电商科技有限公司(72)发明人毕立伟孙喜民周晶李晓明王帅孙博(74)专利代理机构北京集佳知识产权代理有限公司11227代理人尹秀(51)Int.Cl.G06F16/901(2019.01)G06F16/903(2019.01)权利要求书2页说明书8页附图2页(54)发明名称一种应用于频繁子图查询的频繁子图索引方法及装置(57)摘要本发明公开了一种应用于频繁子图查询的频繁子图索引方法及装置，确定频繁子图集，将频繁子图集划范围各个图集块，为各个图集块建立外存索引；为频繁子图中的各个频繁子图建立内存索引，将各个内存索引存入内存中，将各个内存索引、外存索引和各个图集块存入外存中；在接收对目标图的查询请求的情况下，判断目标图是否为频繁子图；若是，在内存中确定所述目标图的目标内存索引，基于目标内存索引在外存中确定目标图所属目标图集块，获取目标图集块的目标外存索引；基于目标内存索引和目标外存索引为所述目标图建立目标连接。在对目标图进行查询过程中，基于内存索引和外存索引实现了对目标图的查询，不需要提取目标图的特征，提高了查询的速度。CN113722551ACN113722551A权利要求书1/2页1.一种应用于频繁子图查询的频繁子图索引方法，其特征在于，包括：确定频繁子图集，将所述频繁子图集划分为各个图集块，为所述各个图集块建立外存索引；为所述频繁子图中的各个频繁子图建立内存索引，将各个内存索引存入内存中，将所述外存索引和所述各个图集块存入外存中；在接收对目标图的查询请求的情况下，判断所述目标图是否为频繁子图；若是，在所述内存中确定所述目标图的目标内存索引，基于所述目标内存索引在所述外存中确定所述目标图所属目标图集块，获取所述目标图集块的目标外存索引；基于所述目标内存索引和所述目标外存索引为所述目标图建立目标连接。2.根据权利要求1所述的方法，其特征在于，为所述频繁子图中的各个频繁子图建立内存索引，包括：获取每个频繁子图的属性特征；为每个频繁子图分配内存索引，将所述内存索引与对应的属性特征建立关联。3.根据权利要求1所述的方法，其特征在于，判断所述目标图是否为频繁子图，包括：获取所述目标图中的各个点和各个边；将所述各个点与预设基准频繁子图中的各个基准点进行比较，和，将所述各个边与所述预设基准频繁子图中的各个基准边进行比较；判断所述各个点和所述各个边的比较结果是否满足预设的相似度阈值。4.根据权利要求1所述的方法，其特征在于，基于所述目标内存索引和所述目标外存索引为所述目标图建立目标连接，包括：基于所述目标内存索引确定第一最短路径；基于所述目标外存索引确定第二最短路径；基于所述第一最短路径和所述第二最短路径确定所述目标链接。5.根据权利要求4所述的方法，其特征在于，还包括：若否，为所述目标图在所述内存中建立内存索引，检索所述内存索引在所述内存中的第三最短路径；基于所述第二最短路径与所述第三最短路径确定所述目标连接。6.一种应用于频繁子图查询的频繁子图索引装置，其特征在于，包括：划分和建立模块，用于确定频繁子图集，将所述频繁子图集划分为各个图集块，为所述各个图集块建立外存索引；第一建立模块，用于为所述频繁子图中的各个频繁子图建立内存索引，将各个内存索引存入内存中，将所述外存索引和所述各个图集块存入外存中；判断模块，用于在接收对目标图的查询请求的情况下，判断所述目标图是否为频繁子图；确定和获取模块，用于若是，在所述内存中确定所述目标图的目标内存索引，基于所述目标内存索引在所述外存中确定所述目标图所属目标图集块，获取所述目标图集块的目标外存索引；第二建立模块，用于基于所述目标内存索引和所述目标外存索引为所述目标图建立目标连接。2CN113722551A权利要求书2/2页7.根据权利要求6所述的装置，其特征在于，所述第一建立模块包括：第一获取单元，用于获取每个频繁子图的属性特征；分配和建立单元，用于为每个频繁子图分配内存索引，将所述内存索引与对应的属性特征建立关联。8.根据权利要求6所述的装置，其特征在于，所述判断模块包括：第二获取单元，用于获取所述目标图中的各个点和各个边；比较单元，用于将所述各个点与预设基准频繁子图中的各个基准点进行比较，和，将所述各个边与所述预设基准频繁子图中的各个基准边进行比较；判断单元，用于判断所述各个点和所述各个边的比较结果是否满足预设的相似度阈值。9.根据权利要求6所述的装置，其特征在于，所述第二建立模块包括：第一确定单元，