Optimizing Distance Computation in Distributed Graph Systems

Qing Wang, Shengyi Ji, Peng Peng, Mingdao Li, Ping Huang, Zheng QinIEEE Access 2020 · OpenReview

Abstract

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.
BibTeX
@inproceedings{wang2020optimizing,
  author = {Qing Wang and Shengyi Ji and Peng Peng and Mingdao Li and Ping Huang and Zheng Qin},
  title = {{Optimizing Distance Computation in Distributed Graph Systems}},
  booktitle = {IEEE Access},
  year = {2020},
  url = {https://openreview.net/forum?id=Ei9oYiBSk5Q},
}

Loading related content...

Figure