【摘要】 本发明公开了一种在大型网络图中基于邻接节点树的子图查询方法。本发明利用节点间的邻接关系构成索引树，并以邻接节点树作为大型网络图的索引特征实现子图查询过程。首先，根据图节点的邻接关系建立图的标签表、逐层特征表以及边列表，并以此为基础构建邻接节点树索引；其次，通过将查询图分解成邻接节点树集，并利用已建立的邻接节点树索引对候选的节点进行裁剪获得节点匹配候选集；最后，采用邻接节点树集覆盖查询图的策略，基于节点匹配的方式获得子图查询结果。本发明利用节点的邻接关系实现候选节点的有效过滤和查询图的快速覆盖，能够支持大型网络图中子图的快速查询。 【专利类型】发明授权 【申请人】浙江大学 【申请人类型】学校 【申请人地址】310027 浙江省杭州市西湖区浙大路38号 【申请人地区】中国 【申请人城市】杭州市 【申请人区县】西湖区 【申请号】CN201210063543.9 【申请日】2012-03-12 【申请年份】2012 【公开公告号】CN102662974B 【公开公告日】2014-02-26 【公开公告年份】2014 【授权公告号】CN102662974B 【授权公告日】2014-02-26 【授权公告年份】2014.0 【IPC分类号】G06F17/30 【发明人】贝毅君; 徐俊; 干红华; 刘二腾 【主权项内容】1.一种基于邻接节点树的网络图索引方法，包括步骤：(1)、根据网络图节点间的邻接关系，建立网络图的邻接节点树索引，根据查询图节点间的邻接关系，分解查询图；(2)、将网络图中与查询图节点标签相同的节点集合作为查询图节点的初始匹配候选集；(3)、通过剪枝获得每一个查询图节点对应的节点匹配候选集；v是查询图中的节点，u是节点v的初始匹配候选集中的节点，所述步骤(3)包括步骤：3.1)、比较v和u的相邻节点标签表，设节点v中有标签为X的邻接节点数为nv，如果节点u没有标签为X的邻接节点或者邻接节点数小于nv，则从初始匹配候选集中剔除u，并转入步骤3.4)，否则，继续下面步骤3.2)；3.2)、查询节点v和u的逐层特征表，比较相同层边的数量，设边相对于节点v和u的层为k时，具有某相同边e的数量分别为count(e, v)、count(e, u)，如果count(e, v)小于count(e, u)，则从初始匹配候选集中剔除u，并转入步骤3.4)，否则，继续下面步骤3.3); 3.3)、比较节点v和u邻接节点树的字符串，如果节点u的字符串不能包含节点v的字符串，则从初始匹配候选集中剔除u；3.4)、若初始匹配候选集中还有未访问过的节点则转入步骤3.1)，遍历初始匹配候选集中每一个节点，否则结束；(4)、采用邻接节点树集的覆盖策略实现子图匹配。 【当前权利人】浙江大学 【当前专利权人地址】浙江省杭州市西湖区浙大路38号 【专利权人类型】公立 【统一社会信用代码】12100000470095016Q 【引证次数】5.0 【被引证次数】2 【他引次数】5.0 【被他引次数】2.0 【家族引证次数】5.0 【家族被引证次数】28

未经允许不得转载：http://www.zhongzhencnc.com/1791563260.html