Effective techniques for message reduction and load balancing in distributed graph computation
Refereed conference paper presented and published in conference proceedings


Times Cited
Altmetrics Information
.

Other information
AbstractMassive 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 requestrespond 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.
All Author(s) ListYan D., Cheng J., Lu Y., Ng W.
Name of Conference24th International Conference on World Wide Web, WWW 2015
Start Date of Conference18/05/2015
End Date of Conference22/05/2015
Place of ConferenceFlorence
Country/Region of ConferenceItaly
Detailed descriptionorganized by the International World Wide Web Conference Committee (IW3C2),
Year2015
Month5
Day18
Pages1307 - 1317
ISBN9781450334693
LanguagesEnglish-United Kingdom
KeywordsDistributed Graph Computing, Graph Analytics, Pregel

Last updated on 2020-08-07 at 03:17