Distributed Landmark Selection for Lower Bound Estimation of Distances in Large Graphs
Distributed Landmark Selection for Lower Bound Estimation of Distances in Large Graphs
复制标题
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
给定图中的两个顶点，计算它们的距离是图上的基本操作。然而，这个问题的经典精确方法往往不能扩展到快速发展的图形在最近的应用。已经提出了许多近似方法，包括一些基于地标的方法，这些方法已被证明具有良好的可扩展性，并以可接受的精度估计距离的上界。在本文中，我们提出了一个新的基于地标的框架，基于一个新的措施，称为覆盖率，以更准确地估计距离的下限。虽然我们可以证明，选择最佳的地标集是NP难的，我们提出了一个启发式算法，可以保证近似比。在此基础上，结合分布式图处理系统的特点，将该方法应用于分布式图处理系统中。在大型真实的图上的实验证实了我们方法的优越性。
Given two vertices in a graph, computing their distance is a fundamental operation over graphs. However, classical exact methods for this problem often cannot scale up to the rapidly evolving graphs in recent applications. Many approximate methods have been proposed, including some landmark-based methods that have been shown to have good scalability and estimate the upper bound of the distance in acceptable accuracy. In this paper, we propose a new landmark-based framework based a new measure calledcoverageto more accurately estimate the lower bound of the distance. Although we can prove that selecting the optimal set of landmarks is NP-hard, we propose a heuristic algorithm that can guarantee the approximation ratio. Furthermore, we implement our method through the distributed graph processing systems while considering the characteristic of the distributed graph processing systems. Experiments on large real graphs confirm the superiority of our methods.