Optimizing Distance Computation in Distributed Graph Systems
Optimizing Distance Computation in Distributed Graph Systems
复制标题
优化分布式图系统中的距离计算
DOI：
10.1109/access.2020.3032727
复制
发表时间：
2020
期刊：
影响因子：
3.9
通讯作者：
Qin Zheng
中科院分区：
文献类型：
--
作者：
Wang Qing;Ji Shengyi;Peng Peng;Li Mingdao;Huang Ping;Qin Zheng
给定一个大型图，如社交网络或知识图，一个基本的查询是如何找到从图中的源顶点到另一个顶点的距离。随着真实的图的规模越来越大，许多分布式图系统如Pregel、Pregel+、Giant、GraphX等相继出现，如何利用分布式图系统处理单源距离查询问题成为人们关注的焦点。在本文中，我们提出了一个基于地标的框架来优化分布式图系统的距离计算。我们还使用一种称为集介数的度量来选择用于距离计算的最佳地标集。虽然我们可以证明，选择最佳的地标集是NP难的，我们提出了一个启发式分布式算法，可以保证近似比。在大型真实的图上的实验证实了我们方法的优越性。
Given a large graph, such as a social network or a knowledge graph, a fundamental query is how to find the distance from a source vertex to another vertex in the graph. As real graphs become very large and many distributed graph systems, such as Pregel, Pregel+, Giraph, and GraphX, are proposed, how to employ distributed graph systems to process single-source distance queries should attract more attention. In this paper, we propose a landmark-based framework to optimize the distance computation over distributed graph systems. We also use a measure called set betweenness to select the optimal set of landmarks for distance computation. Although we can prove that selecting the optimal set of landmarks is NP-hard, we propose a heuristic distributed algorithm that can guarantee the approximation ratio. Experiments on large real graphs confirm the superiority of our methods.
登录
查看更多内容
影响因子：
5.3
作者：
Da Yan;Yuzhen Huang;Miao Liu;Hongzhi Chen;James Cheng;Huanhuan Wu;Chengcui Zhang
通讯作者：
Da Yan;Yuzhen Huang;Miao Liu;Hongzhi Chen;James Cheng;Huanhuan Wu;Chengcui Zhang
DOI：
10.1145/2505515.2505724
发表时间：
2013-10
期刊：
Proceedings of the 22nd ACM international conference on Information & Knowledge Management
影响因子：
--
作者：
Yosuke Yano;Takuya Akiba;Yoichi Iwata;Yuichi Yoshida
通讯作者：
Yosuke Yano;Takuya Akiba;Yoichi Iwata;Yuichi Yoshida
DOI：
10.1007/978-3-030-26072-9_16
发表时间：
2019-08
期刊：
--
影响因子：
--
作者：
Mingdao Li;Peng Peng-Peng;Yang Xu;Hao Xia;Zheng Qin
通讯作者：
Mingdao Li;Peng Peng-Peng;Yang Xu;Hao Xia;Zheng Qin
DOI：
10.1109/icde.2012.53
发表时间：
2012-04
期刊：
2012 IEEE 28th International Conference on Data Engineering
影响因子：
--
作者：
Miao Qiao;Hong Cheng;Lijun Chang;J. Yu
通讯作者：
Miao Qiao;Hong Cheng;Lijun Chang;J. Yu
DOI：
--
发表时间：
2014-06
期刊：
--
影响因子：
--
作者：
J. Leskovec;A. Krevl
通讯作者：
J. Leskovec;A. Krevl