Optimizing Distance Computation in Distributed Graph Systems
Lists
Only you see this
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...