基于索引的子图查询技术研究进展

doi:10.11772/j.issn.1001-9081.2018071593

计算机应用 ›› 2019, Vol. 39 ›› Issue (1): 39-45.DOI: 10.11772/j.issn.1001-9081.2018071593

• 2018年全国开放式分布与并行计算学术年会(DPCS 2018)论文 • 上一篇下一篇

基于索引的子图查询技术研究进展

施炜杰¹, 董一鸿¹, 王雄¹, 潘剑飞^1,2

1. 宁波大学信息科学与工程学院, 浙江宁波 315211;
2. 北京百度在线科技有限公司, 北京 100084

收稿日期:2018-07-19 修回日期:2018-08-09 出版日期:2019-01-10 发布日期:2019-01-21
通讯作者: 董一鸿
作者简介:施炜杰(1993-),男,浙江宁波人,硕士研究生,主要研究方向:数据挖掘、机器学习;董一鸿(1969-),男,浙江宁波人,教授,博士,主要研究方向:大数据、数据挖掘、人工智能;王雄(1993-),男,江苏泰州人,硕士研究生,主要研究方向:大数据、数据挖掘;潘剑飞(1991-),男,安徽黄山人,工程师,硕士,主要研究方向:大数据、数据挖掘。
基金资助:
国家自然科学基金资助项目（61572266）；浙江省自然科学基金资助项目（LY16F020003）；宁波市自然科学基金资助项目（2017A610114）。

Research progress of index-based subgraph query technology

SHI Weijie¹, DONG Yihong¹, WANG Xiong¹, PAN Jianfei^1,2

1. College of Information Science and Engineering, Ningbo University, Ningbo Zhejiang 315211, China;
2. Baidu Online Technology Company Limited, Beijing 100084, China

Received:2018-07-19 Revised:2018-08-09 Online:2019-01-10 Published:2019-01-21
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572266), the Natural Science Foundation of Zhejiang Province (LY16F020003), the Natural Science Foundation of Ningbo City (2017A610114).

摘要/Abstract

摘要： 图作为表示实体间的数据结构，在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛的应用。对于大规模数据下进行实时的图查询问题，通过构建合适的索引可以有效降低查询响应时间，提高查询精确度。首先介绍基于索引的子图查询算法的基本结构；然后按索引的构建方式将主流算法分为基于枚举的方法和基于频繁模式挖掘的方法两大类，分别从索引特征、索引结构、应用数据集等方面进行介绍和分析；最后对基于索引的子图查询算法面临的主要问题进行总结和分析，阐述了最新的分布式系统下图查询技术，并对未来趋势进行展望。

关键词: 子图同构, 索引, 子图查询, 频繁模式

Abstract: As a type of data structure representing entities, graphs are widely used in fields that have high requirements on data relevance, such as community data discovery, biochemical analysis and social security analysis. Focusing on the issue of real-time graph query operation under large-scale data, building a suitable index can effectively reduce query response time and improve query accuracy. The basic structure of index-based subgraph query algorithm was firstly introduced and then state-of-the-art algorithms were divided into two categories by construction method of index:enumeration construction and frequent pattern mining construction. Then these algorithms were introduced and analyzed from three aspects:index features, index structures and application datasets. Finally, main problems toward index-based subgraph query algorithm were summarized and analyzed, the latest query technology based on the distributed system was briefly described, and the future trend was forecasted.

Key words: subgraph isomorphism, index, subgraph query, frequent pattern

中图分类号:

TP391

施炜杰, 董一鸿, 王雄, 潘剑飞. 基于索引的子图查询技术研究进展[J]. 计算机应用, 2019, 39(1): 39-45.

SHI Weijie, DONG Yihong, WANG Xiong, PAN Jianfei. Research progress of index-based subgraph query technology[J]. Journal of Computer Applications, 2019, 39(1): 39-45.

参考文献

[1] BERMAN H M, WESTBROOK J, FENG Z, et al. The protein data bank[J]. Genetica, 2000, 106(1/2):149-158.
[2] DESHPANDE M, KURAMOCHI M, WALE N, et al. Frequent substructure-based approaches for classifying chemical compounds[C]//ICDM 2003:Proceedings of the 2003 International Conference on IEEE International Conference on Data Mining. Washington, DC:IEEE Computer Society, 2003:35.
[3] LIANG R, HAI Z, JIANG X, et al. Scaling hop-based reachability indexing for fast graph pattern query processing[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(11):2803-2817.
[4] YUAN Y, WANG G, XU J Y, et al. Efficient distributed subgraph similarity matching[J]. VLDB Journal, 2015, 24(3):369-394.
[5] LAPPAS T, LIU K, TERZI E. Finding a team of experts in social networks[C]//KDD 2009:Proceedings of the 2009 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2009:467-476.
[6] 王超珲,黄一夫.基于增量信息索引的子图查询算法[J].计算机应用与软件,2016,33(10):37-40.(WANG C H, HUANG Y F. A subgraph query algorithm based on incremental information index[J]. Computer Applications & Software, 2016, 33(10):37-40.)
[7] DINARI H. A survey on graph queries processing:techniques and methods[J]. International Journal of Computer Network & Information Security, 2017, 9(4):48-56.
[8] KATSAROU F, NTARMOS N, TRIANTAFILLOU P. Performance and scalability of indexed subgraph query processing methods[J]. Proceedings of the VLDB Endowment, 2015, 8(12):1566-1577.
[9] YAN X, YU P S, HAN J. Graph indexing:a frequent structure-based approach[C]//ICMD 2004:Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2004:335-346.
[10] 陆慧琳,黄博.基于双索引的子图查询算法[J].计算机工程,2015, 41(1):44-48.(LU H L, HUANG B. Subgraph query algorithm based on dual index[J]. Computer Engineering, 2015, 41(1):44-48.)
[11] 黄云,洪佳明,覃遵跃,等.ERSearch:一种高效的子图查询算法[J].电子学报,2017,45(2):368-375(HUANG Y, HONG J M, TAN Z Y, et al. ERSearch:an efficient subgraph query algorithm[J]. Acta Electronica Sinica, 2017, 45(2):368-375.)
[12] SOMKUNWAR M R, VAZE V M. Subgraph isomorphism algorithms for matching graphs:a survey[EB/OL]. (2017-07-01)[2017-12-10]. http://ijett.in/index.php/IJETT/article/view/279/173.
[13] ZOU L, CHEN L, YU J X, et al. A novel spectral coding in a large graph database[C]//EDBT 2008:Proceedings of the 2008 International Conference on Extending Database Technology. New York:ACM, 2008:181-192.
[14] BONNICI V, FERRO A, GIUGNO R, et al. Enhancing graph database indexing by suffix tree structure[C]//PRIB 2010:Proceedings of the 2010 International Conference on Pattern Recognition in Bioinformatics. Berlin:Springer, 2010:195-203.
[15] GIUGNO R, BONNICI V, BOMBIERI N, et al. GRAPES:a software for parallel searching on biological graphs targeting multi-core architectures[J]. PLoS One, 2013, 8(10):e76911.
[16] JIANG H, WANG H, YU P S, et al. GString:a novel approach for efficient search in graph databases[C]//ICDE2007:Proceedings of the 2007 IEEE International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2007:566-575.
[17] DI NATALE R, FERRO A, GIUGNO R, et al. SING:subgraph search in non-homogeneous graphs[J]. BMC Bioinformatics, 2010, 11(1):1-15.
[18] ZHAO P, HAN J. On graph query optimization in large networks[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2):340-351.
[19] ZHANG S, YANG J, JIN W. SAPPER:subgraph indexing and approximate matching in large graphs[J]. Proceedings of the VLDB Endowment, 2010, 3(1):1185-1194.
[20] ZHANG S, HU M, YANG J. TreePi:a novel graph indexing method[C]//ICDE2007:Proceedings of the 2007 IEEE International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2007:966-975.
[21] ZHAO P, YU J X, YU P S. Graph indexing:tree+delta<=graph[C]//VLDB 2007:Proceedings of the 33rd International Conference on Very Large Data Bases. Trondheim:VLDB Endowment, 2007:938-949.
[22] CHENG J, KE Y, NG W, et al. FG-index:towards verification-free query processing on graph databases[C]//SIGMOD 2017:Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2007:857-872.
[23] YUAN D, MITRA P. Lindex:a lattice-based index for graph databases[J]. The VLDB Journal-The International Journal on Very Large Data Bases, 2013, 22(2):229-252.
[24] YUAN D, MITRA P, YU H, et al. Iterative graph feature mining for graph indexing[C]//ICDE2012:Proceedings of the 2012 IEEE International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2012:198-209.
[25] KLEIN K, KRIEGE N, MUTZEL P. CT-index:fingerprint-based graph indexing combining cycles and trees[C]//ICDE2011:Proceedings of the 2011 IEEE International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2011:1115-1126.
[26] LYU B, QIN L, LIN X, et al. Scalable supergraph search in large graph databases[C]//ICDE2016:Proceedings of the 2016 IEEE International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2016:157-168.
[27] YUAN D, MITRA P, GILES C L. Mining and indexing graphs for supergraph search[J]. Proceedings of the VLDB Endowment, 2013, 6(10):829-840.
[28] XIE Y, YU P S. CP-index:on the efficient indexing of large graphs[C]//CIKM:Proceedings of the 2011 ACM International Conference on Information and Knowledge Management. New York:ACM, 2011:1795-1804.
[29] ULLMANN J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1):31-42.
[30] CORDELLA L P, FOGGIA P, SANSONE C, et al. A (sub)graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2004, 26(10):1367.
[31] HU H, WEN Y, CHUA T S, et al. Toward scalable systems for big data analytics:a technology tutorial[J]. IEEE Access, 2017, 2(1):652-687.
[32] MA S, CAO Y, HUAI J, et al. Distributed graph pattern matching[C]//WWW'12:Proceedings of the 2013 Conference on World Wide Web. New York:ACM, 2012:949-958.
[33] SUN Z, WANG H Z, WANG H X, et al. Efficient subgraph matching on billion node graphs[J]. Proceedings of the VLDB Endowment, 2012, 5(9):788-799.

基于索引的子图查询技术研究进展

Research progress of index-based subgraph query technology

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	吴悦, 雒江涛, 刘锐, 胡钟尹. 基于感知哈希和切块的视频相似度检测方法[J]. 计算机应用, 2021, 41(7): 2070-2075.
[2]	崔双双, 王宏志. 基于日志结构合并树的轻量级分布式索引实现方法[J]. 计算机应用, 2021, 41(3): 630-635.
[3]	姜琨, 刘征, 朱磊, 李晓星. 基于有向无环图的倒排链等字长划分压缩算法[J]. 计算机应用, 2021, 41(3): 727-732.
[4]	邹志文, 秦程. 基于k-means++的动态构建空间主题R树方法[J]. 计算机应用, 2021, 41(3): 733-737.
[5]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[6]	徐周波, 李珍, 刘华东, 李萍. 基于邻居信息聚合的子图同构匹配算法[J]. 计算机应用, 2021, 41(1): 43-47.
[7]	兰海, 韩珂, 申砾, 崔秋, 彭煜玮. TiDB的多索引访问优化[J]. 计算机应用, 2020, 40(2): 410-415.
[8]	徐江峰, 谭玉龙. 基于HBase的多维索引查询机制的优化[J]. 计算机应用, 2020, 40(2): 571-577.
[9]	杜明, 杨安平, 周军锋, 陈子阳, 杨云. 有向无环图上k步可达查询优化算法[J]. 计算机应用, 2020, 40(2): 426-433.
[10]	张恩, 侯缨盈, 李功丽, 李会敏, 李钰. 基于错误学习的自适应等级可搜索加密方案[J]. 计算机应用, 2020, 40(1): 148-156.
[11]	韩萌, 丁剑. 数据流频繁模式挖掘综述[J]. 计算机应用, 2019, 39(3): 719-727.
[12]	戴厚乐, 杨庚, 闵兆娥. 分布式环境下多关键词并行密文检索方案[J]. 计算机应用, 2019, 39(10): 2948-2954.
[13]	汪小寒, 韩慧慧, 张泽培, 俞庆英, 郑孝遥. 树索引数据差分隐私预算分配方法[J]. 计算机应用, 2018, 38(7): 1960-1966.
[14]	杨洁, 李松斌, 邓浩江. 基于贝叶斯网络的压缩语音信息隐藏检测[J]. 计算机应用, 2018, 38(7): 1967-1973.
[15]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.