Effective Techniques for Message Reduction and Load Balancing in Distributed Graph Computation
Authors:
Open Access
- 18 May 2015
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1307-1317
Abstract
Massive graphs, such as online social networks and communication networks, have become common today. To efficiently analyze such large graphs, many distributed graph computing systems have been developed. These systems employ the "think like a vertex" programming paradigm, where a program proceeds in iterations and at each iteration, vertices exchange messages with each other. However, using Pregel's simple message passing mechanism, some vertices may send/receive significantly more messages than others due to either the high degree of these vertices or the logic of the algorithm used. This forms the communication bottleneck and leads to imbalanced workload among machines in the cluster. In this paper, we propose two effective message reduction techniques: (1)vertex mirroring with message combining, and (2)an additional request-respond API. These techniques not only reduce the total number of messages exchanged through the network, but also bound the number of messages sent/received by any single vertex. We theoretically analyze the effectiveness of our techniques, and implement them on top of our open-source Pregel implementation called Pregel+. Our experiments on various large real graphs demonstrate that our message reduction techniques significantly improve the performance of distributed graph computation.Keywords
All Related Versions
Funding Information
- Shun Hing Institute of Advanced Engineering (8115048)
This publication has 20 references indexed in Scilit:
- Large-scale distributed graph computing systemsProceedings of the VLDB Endowment, 2014
- Pregel algorithms for graph connectivity problems with performance guaranteesProceedings of the VLDB Endowment, 2014
- BlogelProceedings of the VLDB Endowment, 2014
- An experimental comparison of pregel-like graph processing systemsProceedings of the VLDB Endowment, 2014
- How Well Do Graph-Processing Platforms Perform? An Empirical Performance Evaluation and Analysis2014
- Optimizing graph algorithms on pregel-like systemsProceedings of the VLDB Endowment, 2014
- Mizan2013
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- Combating Web Spam with TrustRank2004
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982