电子学报 ›› 2017, Vol. 45 ›› Issue (2): 368-375.DOI: 10.3969/j.issn.0372-2112.2017.02.015

• 学术论文 • 上一篇    下一篇

ERSearch:一种高效的子图查询算法

黄云1,2, 洪佳明3, 覃遵跃1,2, 钟键2, 李梦婷1, 印鉴1   

  1. 1. 中山大学信息科学与技术学院, 广东广州 510006;
    2. 吉首大学软件服务外包学院, 湖南张家界 427000;
    3. 广州中医药大学医学信息工程学院, 广东广州 510006
  • 收稿日期:2015-09-02 修回日期:2015-12-31 出版日期:2017-02-25 发布日期:2017-02-25
  • 作者简介:黄云,男,1976年生,副教授,中山大学信息科学与技术学院博士研究生.研究方向为数据挖掘、智能信息系统.E-mail:huangyun109@sina.com;洪佳明,男,1984年生,博士,讲师,研究方向为数据挖掘、医学信息处理;覃遵跃,男,1974年生,副教授,中山大学信息科学与技术学院博士研究生.研究方向为数据挖掘、XML处理;钟键,男,1983年生,硕士.研究方向为数据挖掘、社交网络分析;李梦婷,女,1988年生,博士.研究方向为交通网络挖掘;印鉴,男,1968年生,教授,博士生导师.研究方向为大数据分析、机器学习等.
  • 基金资助:

    国家自然科学基金(No.61033010,No.61272065,No.61472453);广东省自然科学基金(No.S2011020001182,No.2014A030309013);广东省科技计划基金(No.2009B090200450,No.2010A040303004,No.2011B040200007);广东省医学科研基金(No.B2014174)

ERSearch: An Efficient Subgraph Query Algorithm

HUANG Yun1,2, HONG Jia-ming3, QIN Zun-yue1,2, ZHONG Jian2, LI Meng-ting1, YIN Jian1   

  1. 1. School of Information Science and Technology, Sun Yat-sen University, Guangzhou, Guangdong 510006, China;
    2. School of Software and Service Outsourcing, Jishou University, Zhangjiajie, Hunan 427000, China;
    3. School of Medical Information Engineering, Guangzhou University of Chinese Medicine, Guangzhou, Guangdong 510006, China
  • Received:2015-09-02 Revised:2015-12-31 Online:2017-02-25 Published:2017-02-25

摘要:

子图查询是图数据库研究中的一个重要问题,许多方法基于“过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌入关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比,ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.

关键词: 子图查询, 特征模式, 嵌入关系, 图索引, 图数据库

Abstract:

Subgraph query is an important problem in the research of graph databases,and many methods about subgraph query are based on "filtering-verification strategy",which key target is to find effective feature patterns.Through the analysis of the embedding information of feature patterns in the data graphs,we propose to construct embedding relation indexing in the offline stage,and propose a new feature pattern embedding based subgraph query algorithm ERSearch.When query graph is given,we will use the co-occurrence relations and embedding relations combined to prune the unmatched data graphs,and the comparing results of embedded relationship in filtering phase can be used in the verification process,improving the efficiency of the verification.Via the experiment in the real and synthetic datasets,compared with PathIndex and other methods,we show that our algorithm can effectively reduce the size of candidate set,and effectively improve the efficiency of filtering and verification stages.

Key words: subgraph query, feature pattern, embedding relationship, graph index, graph database

中图分类号: