Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2016, Vol. 56 Issue (8): 871-877    DOI: 10.16511/j.cnki.qhdxxb.2016.25.026
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
分布式Top-k子图匹配技术
兰超, 张勇, 邢春晓
清华大学 计算机科学与技术系, 信息科学与技术国家实验室, 北京 100084
Distributed Top-k subgraph matching
LAN Chao, ZHANG Yong, XING Chunxiao
National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
全文: 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 wordsgraph 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] 苗旭鹏, 张敏旭, 邵蓥侠, 崔斌. PS-Hybrid: 面向大规模推荐模型训练的混合通信框架[J]. 清华大学学报(自然科学版), 2022, 62(9): 1417-1425.
[2] 朱唯一, 张雪芹, 顾春华. 基于EDLATrust算法的社交网络信息泄露节点概率预测[J]. 清华大学学报(自然科学版), 2022, 62(2): 355-366.
[3] 刘迪, 曹军威, 刘明爽. 分布式数据中心信息能量协同优化策略[J]. 清华大学学报(自然科学版), 2022, 62(12): 1864-1874.
[4] 张彤, 任丰原, 舒然. 基于分布式优化的数据中心网络混流调度机制[J]. 清华大学学报(自然科学版), 2021, 61(6): 618-625.
[5] 宋宇波, 杨慧文, 武威, 胡爱群, 高尚. 软件定义网络DDoS联合检测系统[J]. 清华大学学报(自然科学版), 2019, 59(1): 28-35.
[6] 谢丽霞, 丁颖. 链路洪泛攻击的SDN移动目标防御机制[J]. 清华大学学报(自然科学版), 2019, 59(1): 36-43.
[7] 方元坤, 孟子阳, 尤政. 多模式分布式遥感微纳航天器集群自然编队构型[J]. 清华大学学报(自然科学版), 2018, 58(5): 482-488.
[8] 曹来成, 刘宇飞, 董晓晔, 郭显. 基于属性加密的用户隐私保护云存储方案[J]. 清华大学学报(自然科学版), 2018, 58(2): 150-156.
[9] 马锐, 朱天保, 马科, 胡昌振, 赵小林. 基于单证人节点的分布式节点复制攻击检测[J]. 清华大学学报(自然科学版), 2017, 57(9): 909-913,920.
[10] 袁小虎, 吴热冰, 李春文. 基于分布式压缩感知的量子过程层析[J]. 清华大学学报(自然科学版), 2017, 57(10): 1089-1095.
[11] 王璟, 王燕敏, 冯伟, 肖立民, 周世东. 多小区分布式天线系统高能效协同传输方案[J]. 清华大学学报(自然科学版), 2017, 57(1): 67-71.
[12] 赵俊韬, 冯伟, 赵明, 王京. 频谱共享系统中基于大尺度信道状态信息的资源优化[J]. 清华大学学报(自然科学版), 2016, 56(7): 692-695.
[13] 王璟, 王燕敏, 冯伟, 肖立民, 周世东. 分布式天线系统中基于大尺度信道信息的功耗优化[J]. 清华大学学报(自然科学版), 2016, 56(7): 696-699,706.
[14] 杨德亮, 谢旭东, 李春文, 牛小铁. 基于分布式视频网络的交叉口车辆精确定位方法[J]. 清华大学学报(自然科学版), 2016, 56(3): 281-286,293.
[15] 田文洪, 李国忠, 陈瑜, 黄超杰, 杨吴同. 一种兼顾负载均衡的Hadoop集群动态节能方法[J]. 清华大学学报(自然科学版), 2016, 56(11): 1226-1231.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn