SQM:基于Spark的大规模单图上的子图匹配算法

doi:10.11772/j.issn.1001-9081.2018071594

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

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

SQM:基于Spark的大规模单图上的子图匹配算法

李龙洋¹, 董一鸿¹, 施炜杰¹, 潘剑飞^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）。

SQM: subgraph matching algorithm for single large-scale graphs under Spark

LI Longyang¹, DONG Yihong¹, SHI Weijie¹, 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

摘要： 针对大规模数据图下基于回溯法的子图查询算法的准确率低、开销大等问题，为提高查询准确率，降低大图下的查询开销，提出一种基于Spark的子图匹配（SQM）算法。首先根据结构信息过滤数据图，再将查询图分割成基本查询单元；然后对每一个基本查询单元分别匹配后进行Join操作；最后运用并行化提高了算法的运行效率，减小了搜索空间。实验结果表明，与Stwig、TurboISO算法相比，SQM算法在保证查询结果不变的情况下，速度提高了50%。

关键词: 子图匹配, 图分割, 大规模单图, 并行化, Spark

Abstract: Focusing on low accuracy and high costs of backtracking-based subgraph query algorithm applied to large-scale graphs, a Spark-based Subgraph Query Matching (SQM) algorithm was proposed to improve query accuracy and reduce query overhead for large graphs. The data graph was firstly filtered according to structure information, and the query graph was divided into basic query units. Then each basic query unit was matched and joined together. Finally, the algorithm's efficiency was improved and search space was reduced by parallelization. The experimental results show that compared with Stwig (Sub twig) algorithm and TurboISO algorithm, SQM algorithm can increase the speed by 50% while ensuring the same query results.

Key words: subgraph matching, graph segmentation, single large-scale graph, parallelization, Spark

中图分类号:

TP392

李龙洋, 董一鸿, 施炜杰, 潘剑飞. SQM:基于Spark的大规模单图上的子图匹配算法[J]. 计算机应用, 2019, 39(1): 46-50.

LI Longyang, DONG Yihong, SHI Weijie, PAN Jianfei. SQM: subgraph matching algorithm for single large-scale graphs under Spark[J]. Journal of Computer Applications, 2019, 39(1): 46-50.

参考文献

[1] 中国互联网信息中心.中国互联网络发展状况统计报告[EB/OL].(2017-02-03)[2018-05-20]. http://www.cac.gov.cn/2018zt/cnnic41/index.htm.(China Internet Information Center. Statistical Report on the Development of China's Internet.[EB/OL]. (2017-02-03)[2018-05-20].http://www.cac.gov.cn/2018zt/cnnic41/index.htm.)
[2] 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.
[3] ULLMANN J R. An algorithm for subgraph isomorphism[J]. Journal of the ACM, 1976, 23(1):31-42.
[4] CORDELLA L P, FOGGIA P. A (sub)graph isomorphism algorithm for matching large graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(10):1367-1372.
[5] HE H, SINGH A K. Graphs-at-a-time:query language and access methods for graph databases[C]//SIGMOD 2008:Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2008:405-418.
[6] ZHANG S, LI S, YANG J. GADDI:distance index based subgraph matching in biological networks[C]//Proceedings of the 12th International Conference on Extending Database Technology:Advances in Database Technology. New York:ACM, 2009:192-203.
[7] 张硕,李建中,高宏,等.一种多到一子图同构检测方法[J].软件学报,2010,21(3):401-414.(ZHANG S, LI J Z, GAO H, et al. A multi-to-one subgraph isomorphism detection method[J]. Journal of Software, 2010, 21(3):401-414.)
[8] HAN W S, LEE J, LEE J H. TurboISO:towards ultrafast and robust subgraph isomorphism search in large graph databases[C]//ICMD 2013:Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2013:337-348.
[9] AFRATI F N, FOTAKIS D, ULLMAN J D. Enumerating subgraph instances using Map-Reduce[C]//ICDE2013:Proceedings of the 2013 IEEE International Conference on Data Engineering. Piscataway, NJ:IEEE, 2013:62-73.
[10] PLANTENGA T. Inexact subgraph isomorphism in MapReduce[J]. Journal of Parallel & Distributed Computing, 2013, 73(2):164-175.
[11] 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.
[12] 于静,刘燕兵,张宇,等.大规模图数据匹配技术综述[J].计算机研究与发展,2015,52(2):391-409.(YU J, LIU Y B, ZHANG Y, et al. Survey on large-scale graph pattern matching[J]. Journal of Computer Research and Development, 2015, 52(2):391-409.)
[13] ZOU L, CHEN L, LU Y. Top-k subgraph matching query in a large graph[C]//PIKM 2007:Proceedings of the ACM first Ph. D. Workshop in Sixteenth ACM Conference on Information and Knowledge Management. New York:ACM, 2007:139-146.
[14] NEUMANN T, WEIKUM G. The RDF-3X engine for scalable management of RDF data[J]. The VLDB Journal, 2010, 19(1):91-113.
[15] ATRE M, CHAOJI V, ZAKI M J, et al. Matrix "bit" loaded:a scalable lightweight join query processor for RDF data[C]//IW3C2:Proceedings of the 2010 International World Wide Web Conference Committee. New York:ACM, 2010:41-50.
[16] HONG L, ZOU L, LIAN X, et al. Subgraph matching with set similarity in a large graph database[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(9):2507-2521.
[17] YAN X, YU P S, HAN J. Substructure similarity search in graph databases[C]//SIGMOD 2005:Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York:ACM, 2005:766-777.
[18] Apache. Spark[EB/OL].[2018-02-03]. http://spark.apache.org.
[19] CHANG Z, ZOU L, LI F. Privacy preserving subgraph matching on large graphs in cloud[C]//ICMD2016:Proceedings of the 2016 International Conference on Management of Data. New York:ACM, 2016:199-213.
[20] LESKOVEC J. SNAP[EB/OL].[2018-03-03]. http://snap.stanford.edu/snappy.

SQM:基于Spark的大规模单图上的子图匹配算法

SQM: subgraph matching algorithm for single large-scale graphs under Spark

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[2]	蒋林, 施佳琪, 李远成. 可重构结构下合成视点失真变化算法并行设计与实现[J]. 计算机应用, 2021, 41(6): 1734-1740.
[3]	谢云霞, 黄海于, 胡建斌. 基于深度卷积神经网络的糖尿病视网膜病变分期及病灶检测[J]. 计算机应用, 2020, 40(8): 2460-2464.
[4]	顾军华, 王锋, 戚永军, 孙哲然, 田泽培, 张亚娟. 基于多尺度卷积特征融合的肺结节图像检索方法[J]. 计算机应用, 2020, 40(2): 561-565.
[5]	章夏杰, 朱敬华, 陈杨. Spark下的分布式粗糙集属性约简算法[J]. 计算机应用, 2020, 40(2): 518-523.
[6]	刘斌, 何进荣, 李远成, 韩宏. 基于分布式神经网络的苹果价格预测方法[J]. 计算机应用, 2020, 40(2): 369-374.
[7]	宋祥帅, 杨伏长, 谢江, 张武. Graphlet Degree Vector方法的优化与并行[J]. 计算机应用, 2020, 40(2): 398-403.
[8]	程文亮, 王志宏, 周虞, 过弋, 赵俊锋. 面向外汇市场监测的分布式计算框架设计[J]. 计算机应用, 2020, 40(1): 173-180.
[9]	崔艺馨, 陈晓东. Spark框架优化的大规模谱聚类并行算法[J]. 计算机应用, 2020, 40(1): 168-172.
[10]	郭良敏, 朱莹, 孙丽萍. 障碍空间中基于并行蚁群算法的k近邻查询[J]. 计算机应用, 2019, 39(3): 790-795.
[11]	关皓元, 朱斌, 李冠宇, 蔡永嘉. 基于资源描述框架图切分与顶点选择性的高效子图匹配方法[J]. 计算机应用, 2019, 39(2): 360-369.
[12]	刘靖, 肖冠烽. 基于Spark与粒子滤波算法的公交到站时间预测系统[J]. 计算机应用, 2019, 39(2): 429-435.
[13]	刘子豪, 李凌, 叶枫. 基于SparkR的水文传感器数据的异常检测方法[J]. 计算机应用, 2019, 39(2): 436-440.
[14]	赵文芳, 王京丽, 尚敏, 刘亚楠. 基于粒子群优化和支持向量机的花粉浓度预测模型[J]. 计算机应用, 2019, 39(1): 98-104.
[15]	孙佳敏, 朱嘉富, 杨伏长, 谢江. 大规模生物网络马尔可夫聚类的并行化算法[J]. 计算机应用, 2019, 39(1): 66-71.