计算机应用 ›› 2012, Vol. 32 ›› Issue (07): 1994-1997.DOI: 10.3724/SP.J.1087.2012.01994

• 人工智能 • 上一篇    下一篇

基于双索引的近似子图匹配

黄云1,2,洪佳明2,覃遵跃1,2   

  1. 1. 吉首大学 软件服务外包学院,湖南 张家界427000
    2. 中山大学 信息科学与技术学院,广州510006
  • 收稿日期:2012-01-29 修回日期:2012-03-21 发布日期:2012-07-05 出版日期:2012-07-01
  • 通讯作者: 黄云
  • 作者简介:黄云(1976-),男(土家族),湖南张家界人,讲师,博士研究生,主要研究方向:数据挖掘;洪佳明(1984-),男,广东揭阳人,博士研究生,主要研究方向:数据挖掘;覃遵跃(1974-),男(土家族),湖南张家界人,副教授,博士研究生,主要研究方向:时空数据库。

Approximate subgraph matching based on dual index

HUANG Yun1,2,HONG Jia-ming2,QIN Zun-yue1,2   

  1. 1. School of Software, Jishou University, Zhangjiajie Hunan 427000, China
    2. School of Information Science and Technology, Sun Yat-sen University, Guangzhou Guangdong 510006, China
  • Received:2012-01-29 Revised:2012-03-21 Online:2012-07-05 Published:2012-07-01
  • Contact: HUANG Yun

摘要: 越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。

关键词: 图结构, 近似匹配, 近邻关系, 图划分, 双索引

Abstract: The fast increasing large and complex networks make the research of graph structure more and more important, in which approximate subgraph query is of big concern. Constructing index for each vertex by the adjacency characteristics was able to reduce the number of matched vertices, and partitioning the large graph based on label and structure information was able to reduce the matching search space. Using the dual index built in offline time, large amount of candidate vertices were filtered out according to the adjacency discriminant formula, and then the edge matching was carried out in some partition spaces. The experiments on real dataset show that, compared with many other existing methods, the dual-index query mechanism improves the efficiency and accuracy of subgraph matching significantly.

Key words: graph structure, approximate matching, neighborhood relation, graph partition, dual index

中图分类号: