分布式Top-<em>k</em>子图匹配技术

doi:10.16511/j.cnki.qhdxxb.2016.25.026

摘要
图/表
参考文献
相关文章
Metrics

全文: PDF(1238 KB)
输出: BibTeX | EndNote (RIS)

摘要 Top-k子图匹配是一种应用广泛的图搜索技术。相比于单机环境，分布式环境下的Top-k子图匹配问题具有更大的挑战性。该文分析了已有方法在分布式环境下存在的问题，提出了包括查询拆分、查询执行、结果连接3个步骤的算法。算法通过查询拆分，彻底避免了生成中间结果过程中的数据传输，同时通过优化查询执行和结果连接步骤，避免不必要的中间结果生成，降低单个节点的计算量，提升整体效率。在此基础上，该文对分布式环境下Top-k连接策略进行了进一步优化。在真实图数据上进行的实验测试表明：该文提出的算法能够有效解决分布式环境下Top-k子图匹配问题，具有很好的扩展性，而且使用优化连接策略的算法性能较基础算法的效率有明显的提升。

	服务

	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS

	作者相关文章
	兰超
	张勇
	邢春晓

关键词 ：图搜索, 子图匹配, Top-k子图匹配, 分布式

Abstract：Top-k subgraph matching is a key operation in graph queries which is widely used in all kinds of applications such as social networks and knowledge graphs. Top-k subgraph matching is more challenging in distributed environments since it involves data and task transfers. Thus, existing local Top-k subgraph matching methods do not work well in distributed environments. An algorithm was developed to address this issue by dividing the problem into query decomposition, query execution, and ranked join stages. The query decomposition avoids unnecessary data transfers during the querying stage. The ranked join technique avoids generating unnecessary temporal results that reduces the overall latency of the algorithm. The algorithm effectiveness and efficiency were tested using real data and the results indicate that the algorithm, especially the optimized version, effectively solves the distributed Top-k subgraph matching problem.

Key words： graph search subgraph matching Top-k subgraph matching distributed systems

收稿日期: 2016-01-29 出版日期: 2016-08-15

ZTFLH:

TP319

通讯作者: 邢春晓,研究员,E-mail:xingcx@tsinghua.edu.cn E-mail: xingcx@tsinghua.edu.cn

引用本文:

兰超, 张勇, 邢春晓. 分布式Top-k子图匹配技术[J]. 清华大学学报（自然科学版）, 2016, 56(8): 871-877.
LAN Chao, ZHANG Yong, XING Chunxiao. Distributed Top-k subgraph matching. Journal of Tsinghua University(Science and Technology), 2016, 56(8): 871-877.

链接本文:

http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2016.25.026 或 http://jst.tsinghuajournals.com/CN/Y2016/V56/I8/871

图1 分布式Top-k 子图匹配查询示例

图2 查询划分示例

图3 最优匹配示例

图4 子查询连接示例

图5 采用优化评价函数的子图匹配连接

表1 DBPedia数据统计

图6 实验结果对比

[1] Gupta M,Gao J,Yan X,et al.Top-k interesting subgraph discovery in information networks[C]//ICDE2014.Chicago,IL,USA:IEEE,2014:820-831.
[2] Huang J,Abadi D J,Ren K.Scalable SPARQL querying of large RDF graphs[J].Proc VLDB Endow,2011,4(11):1123-1134.
[3] Yang S,Wu Y,Sun H,et al.Schemaless and structureless graph querying[J].Proc VLDB Endow,2014,7(7):565-576.
[4] Khan A,Wu Y,Aggarwal C C,et al.NeMa:Fast graph search with label similarity[J].Proc VLDB Endow,2013,6(3):181-192.
[5] Gonzalez J E,Low Y,Gu H,et al.PowerGraph:Distributed graph-parallel computation on natural graphs[C]//USENIX 2012.Hollywood,CA,USA:USENIX Association,2012:17-30.
[6] Albert R,Jeong H,Barabási A.Error and attack tolerance of complex networks[J].Nature,2000,406(6794):378-382.
[7] Abou-Rjeili A,Karypis G.Multilevel algorithms for partitioning power-law graphs[C]//Proceedings of the 20th International Conference on Parallel and Distributed Processing.Rhodes Island,Greece:IEEE Computer Society,2006:124-124.
[8] Xin R S,Gonzalez J E,Franklin M J,et al.GraphX:A resilient distributed graph system on spark[C]//First International Workshop on Graph Data Management Experiences and Systems.New York,USA:ACM,2013:1-6.
[9] Ullmann J R.An algorithm for subgraph isomorphism[J].J ACM,1976,23(1):31-42.
[10] He H,Wang H,Yang J,et al.BLINKS:Ranked keyword searches on graphs[C]//SIGMOD2007.New York,USA:ACM,2007:305-316.
[11] Sun Z,Wang H,Wang H,et al.Efficient subgraph matching on billion node graphs[J].Proc VLDB Endow,2012,5(9):788-799.
[12] Gou G,Chirkova R.Efficient algorithms for exact ranked twig-pattern matching over graphs[C]//SIGMOD2008.New York,USA:ACM,2008:581-594.
[13] Ilyas I F,Beskales G,Soliman M A.A survey of top-k query processing techniques in relational database systems[J].ACM Comput Surv,2008,40(4):1-58.
[14] Dbpedia.Dbpedia[Z/OL].(2015-01-01).http://wiki.dbpedia.org/.

[1]	余嘉茵, 何玉林, 崔来中, 黄哲学. 针对大规模数据的分布一致缺失值插补算法[J]. 清华大学学报（自然科学版）, 2023, 63(5): 740-753.
[2]	刘子平, 孙俊. 含分布式内热源复合平板等效导热系数模型[J]. 清华大学学报（自然科学版）, 2023, 63(1): 104-113.
[3]	苗旭鹏, 张敏旭, 邵蓥侠, 崔斌. PS-Hybrid: 面向大规模推荐模型训练的混合通信框架[J]. 清华大学学报（自然科学版）, 2022, 62(9): 1417-1425.
[4]	朱唯一, 张雪芹, 顾春华. 基于EDLATrust算法的社交网络信息泄露节点概率预测[J]. 清华大学学报（自然科学版）, 2022, 62(2): 355-366.
[5]	刘迪, 曹军威, 刘明爽. 分布式数据中心信息能量协同优化策略[J]. 清华大学学报（自然科学版）, 2022, 62(12): 1864-1874.
[6]	张彤, 任丰原, 舒然. 基于分布式优化的数据中心网络混流调度机制[J]. 清华大学学报（自然科学版）, 2021, 61(6): 618-625.
[7]	宋宇波, 杨慧文, 武威, 胡爱群, 高尚. 软件定义网络DDoS联合检测系统[J]. 清华大学学报（自然科学版）, 2019, 59(1): 28-35.
[8]	谢丽霞, 丁颖. 链路洪泛攻击的SDN移动目标防御机制[J]. 清华大学学报（自然科学版）, 2019, 59(1): 36-43.
[9]	方元坤, 孟子阳, 尤政. 多模式分布式遥感微纳航天器集群自然编队构型[J]. 清华大学学报（自然科学版）, 2018, 58(5): 482-488.
[10]	曹来成, 刘宇飞, 董晓晔, 郭显. 基于属性加密的用户隐私保护云存储方案[J]. 清华大学学报（自然科学版）, 2018, 58(2): 150-156.
[11]	马锐, 朱天保, 马科, 胡昌振, 赵小林. 基于单证人节点的分布式节点复制攻击检测[J]. 清华大学学报（自然科学版）, 2017, 57(9): 909-913,920.
[12]	袁小虎, 吴热冰, 李春文. 基于分布式压缩感知的量子过程层析[J]. 清华大学学报（自然科学版）, 2017, 57(10): 1089-1095.
[13]	王璟, 王燕敏, 冯伟, 肖立民, 周世东. 多小区分布式天线系统高能效协同传输方案[J]. 清华大学学报（自然科学版）, 2017, 57(1): 67-71.
[14]	赵俊韬, 冯伟, 赵明, 王京. 频谱共享系统中基于大尺度信道状态信息的资源优化[J]. 清华大学学报（自然科学版）, 2016, 56(7): 692-695.
[15]	王璟, 王燕敏, 冯伟, 肖立民, 周世东. 分布式天线系统中基于大尺度信道信息的功耗优化[J]. 清华大学学报（自然科学版）, 2016, 56(7): 696-699,706.

Viewed

Full text

Abstract

Cited

Shared

Discussed