首页 | 本学科首页   官方微博 | 高级检索  
     

基于双索引的近似子图匹配
引用本文:黄云,洪佳明,覃遵跃.基于双索引的近似子图匹配[J].计算机应用,2012,32(7):1994-1997.
作者姓名:黄云  洪佳明  覃遵跃
作者单位:1. 吉首大学 软件服务外包学院,湖南 张家界427000 2. 中山大学 信息科学与技术学院,广州510006
摘    要:越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。

关 键 词:图结构    近似匹配    近邻关系    图划分    双索引
收稿时间:2012-01-29
修稿时间:2012-03-21

Approximate subgraph matching based on dual index
HUANG Yun , HONG Jia-ming , QIN Zun-yue.Approximate subgraph matching based on dual index[J].journal of Computer Applications,2012,32(7):1994-1997.
Authors:HUANG Yun  HONG Jia-ming  QIN Zun-yue
Affiliation: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
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.
Keywords:graph structure  approximate matching  neighborhood relation  graph partition  dual index
本文献已被 CNKI 万方数据 等数据库收录!
点击此处可从《计算机应用》浏览原始摘要信息
点击此处可从《计算机应用》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号