Optimizing Distance Computation in Distributed Graph Systems
| Autor: | Peng Peng, Zheng Qin, Qing Wang, Mingdao Li, Shengyi Ji, Ping Huang |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Theoretical computer science
General Computer Science Computer science Computation graph theory 02 engineering and technology Upper and lower bounds Data modeling distributed computing distributed graph systems Betweenness centrality landmark 020204 information systems Web page 0202 electrical engineering electronic engineering information engineering General Materials Science Electrical and Electronic Engineering Heuristic business.industry General Engineering Distributed information systems Graph Vertex (geometry) distance computation Distributed algorithm 020201 artificial intelligence & image processing The Internet lcsh:Electrical engineering. Electronics. Nuclear engineering business lcsh:TK1-9971 MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | IEEE Access, Vol 8, Pp 191673-191682 (2020) |
| ISSN: | 2169-3536 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|