一种基于邻接节点树的网络图索引方法

摘要

本发明公开了一种在大型网络图中基于邻接节点树的子图查询方法。本发明利用节点间的邻接关系构成索引树，并以邻接节点树作为大型网络图的索引特征实现子图查询过程。首先，根据图节点的邻接关系建立图的标签表、逐层特征表以及边列表，并以此为基础构建邻接节点树索引；其次，通过将查询图分解成邻接节点树集，并利用已建立的邻接节点树索引对候选的节点进行裁剪获得节点匹配候选集；最后，采用邻接节点树集覆盖查询图的策略，基于节点匹配的方式获得子图查询结果。本发明利用节点的邻接关系实现候选节点的有效过滤和查询图的快速覆盖，能够支持大型网络图中子图的快速查询。

主权项

一种基于邻接节点树的网络图索引方法，包括步骤：(1)、根据网络图节点间的邻接关系，建立网络图的邻接节点树索引，根据查询图节点间的邻接关系，分解查询图；(2)、将网络图中与查询图节点标签相同的节点集合作为查询图节点的初始匹配候选集；(3)、通过剪枝获得每一个查询图节点对应的节点匹配候选集；(4)、采用邻接节点树集的覆盖策略实现子图匹配。