大规模标签图中的动态Top-K兴趣子图查询

doi:10.11772/j.issn.1001-9081.2017082360

计算机应用 ›› 2018, Vol. 38 ›› Issue (2): 471-477.DOI: 10.11772/j.issn.1001-9081.2017082360

大规模标签图中的动态Top-K兴趣子图查询

宋宝燕, 贾春杰, 单晓欢, 丁琳琳, 丁兴艳

辽宁大学信息学院, 沈阳 110036

收稿日期:2017-08-28 修回日期:2017-09-28 出版日期:2018-02-10 发布日期:2018-02-10
通讯作者: 单晓欢
作者简介:宋宝燕(1965-),女,辽宁开原人,教授,博士,CCF高级会员,主要研究方向:数据库、RFID事件流处理、大数据管理、图数据管理;贾春杰(1991-),女,河北廊坊人,硕士研究生,主要研究方向:图数据管理;单晓欢(1987-),女,辽宁沈阳人,助理实验师,博士研究生,主要研究方向:数据库、图数据管理;丁琳琳(1983-),女,辽宁阜新人,副教授,博士,CCF会员,主要研方向:大数据管理、分布式数据管理、不确定数据管理;丁兴艳(1991-),女,贵州贵阳人,硕士研究生,主要研究方向:图数据管理。
基金资助:
国家自然科学基金资助项目（61472169，61502215）；国家重点研发计划项目（2016YFC0801406）；辽宁省教育厅一般项目（L2015193）；辽宁省博士科研启动基金项目（201501127）。

Dynamic Top-K interesting subgraph query on large-scale labeled graph

SONG Baoyan, JIA Chunjie, SHAN Xiaohuan, DING Linlin, DING Xingyan

College of Information, Liaoning University, Shenyang Liaoning 110036, China

Received:2017-08-28 Revised:2017-09-28 Online:2018-02-10 Published:2018-02-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61472169, 61502215), the National Key Research and Development Program of China (2016YFC0801406), the General Science Research Project of Liaoning Province Education Department (L2015193), Doctoral Scientific Research Start Foundation of Liaoning Province (201501127).

摘要/Abstract

摘要： 针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题，提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性（NTF）索引和边特性（EF）索引的图拓扑结构特性（GTSF）索引，利用该索引可有效剪枝过滤不满足限制条件的无效节点及边；基于GTSF索引提出了多因素候选集过滤策略，通过对查询图候选集进一步剪枝以获得较少的候选集；考虑到图的动态变化可能对匹配结果产生影响，提出了Top-K兴趣子图匹配验证方法——DISQtop-K，将匹配验证过程分为初始匹配和动态修正两个阶段，以尽可能保证查询结果的实时、准确。大量实验结果表明，相比RAM、RWM算法，DISQtop-K方法的索引创建时间较短且占用空间较少，能有效处理大规模标签图中的动态Top-K兴趣子图查询。

关键词: 大规模标签图, 动态Top-K, 兴趣子图, 子图查询

Abstract: The traditional algorithms are difficult to implement the Top-K subgraph query on large-scale dynamic labeled graph due to high time or space complexity. For this reason, a dynamic Top-K interesting subgraph query method named DISQtop-K was proposed. In this algorithm, a Graph Topology Structure Feature (GTSF) index that include Node Topology Feature (NTF) index and Edge Feature (EF) index was established, which can effectively prune and filter the invalid nodes and edges. Then a multi-factor candidate set filtering strategy was put forward based on GTSF index, which can be used to further prune the query graph candidate sets. Considering that the dynamic changes in the graph may have an impact on the matching results, to ensure the real-time and accuracy of the query results, a new matching-verification method for Top-K interesting subgraph was also given, which has two stages of initial matching and dynamic correction. Experimental results show that compared with RAM and RWM, DISQtop-K method costs shorter time for index creation and occupies less space, which can effectively deal with dynamic Top-K interesting subgraph query on large-scale labeled graph.

Key words: large-scale labeled graph, dynamic Top-K, interesting subgraph, subegraph query

中图分类号:

TP311

宋宝燕, 贾春杰, 单晓欢, 丁琳琳, 丁兴艳. 大规模标签图中的动态Top-K兴趣子图查询[J]. 计算机应用, 2018, 38(2): 471-477.

SONG Baoyan, JIA Chunjie, SHAN Xiaohuan, DING Linlin, DING Xingyan. Dynamic Top-K interesting subgraph query on large-scale labeled graph[J]. Journal of Computer Applications, 2018, 38(2): 471-477.

参考文献

[1] SONMEZ A B, CAN T. Comparison of tissue/disease specific integrated networks using directed graphlet signatures[J]. BMC Bioinformatics, 2017, 18(Suppl. 4):135.
[2] 张海威,解晓芳,段媛媛,等.一种基于自适应结构概要的有向标签子图匹配查询算法[J].计算机学报,2017,40(1):52-71. (ZHANG H W, XIE J F, DUAN Y Y, et al.An algorithm for subgraph matching based on adaptive structural summary of labeled directed graph data[J]. Chinese Journal of Computers, 2017, 40(1):52-71.)
[3] ULLMANN J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM (JACM), 1976, 23(1):31-42.
[4] 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-1372.
[5] SUN Z, WANG H, WANG H, et al. Efficient subgraph matching on billion node graphs[J]. Proceedings of the VLDB Endowment, 2012, 5(9):788-799.
[6] HAN W-S, LEE J, LEE J-H. Turbo_ISO:towards ultrafast and robust subgraph isomorphism search in large graph databases[C]//SIGMOD'13:Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2013:337-348.
[7] REN X, WANG J. Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs[J]. Proceeding of the VLDB Endowment, 2015, 8(5):617-628.
[8] BI F, CHANG L, LIN X, et al. Efficient subgraph matching by postponing Cartesian products[C]//SIGMOD'16:Proceedings of the 2016 International Conference on Management of Data. New York:ACM, 2016:1199-1214.
[9] HOLDER L B, COOK D, DJOKO S. Substructure discovery in the SUBDUE system[C]//AAAIWS'94:Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. Seattle, WA:IAAA, 1994:169-180.
[10] ZHU F, QU Q, LO D, et al. Mining Top-K large structural patterns in a massive network[J]. Proceedings of the VLDB Endowment, 2011, 4(11):807-818.
[11] ZHAO P, HAN J. On graph query optimization in large networks[J]. Proceedings of the VLDB Endowment, 2010, 3(1/2):340-351.
[12] HE H, SINGH A K. Query language and access methods for graph databases[M]//Managing and Mining Graph Data. Boston:Springer, 2010:125-160.
[13] YAN X, HE B, ZHU F, et al. Top-K aggregation queries over large networks[C]//ICDE 2010:Proceedings of the 2010 IEEE 26th International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2010:377-380.
[14] GUPTA M, GAO J, YAN X, et al. Top-K interesting subgraph discovery in information networks[C]//ICDE 2014:Proceedings of the 2014 IEEE 30th International Conference on Data Engineering. Washington, DC:IEEE Computer Society, 2014:820-831.
[15] SUN Y, YU Y, HAN J. Ranking-based clustering of heterogeneous information networks with star network schema[C]//KDD'09:Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2009:797-806.
[16] CHAKRABARTI D, ZHAN Y, FALOUTSOS C. R-MAT:a recursive model for graph mining[C]//SIAM International Conference on Data Mining. Philadelphia, PA:Society for Industrial and Applied Mathematics (SIAM), 2004:442-446.

大规模标签图中的动态Top-K兴趣子图查询

Dynamic Top-K interesting subgraph query on large-scale labeled graph

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics