Optimizing Graph Algorithms on Pregel-like Systems

We study the problem of implementing graph algorithms efficiently on Pregel-like systems, which can be surprisingly challenging. Standard graph algorithms in this setting can incur unnecessary in-efficiencies such as slow convergence or high communication or computation cost, typically due to structural properties of the in-put graphs such as large diameters or skew in component sizes. We describe several optimization techniques to address these in-efficiencies. Our most general technique is based on the idea of performing some serial computation on a tiny fraction of the in-put graph, complementing Pregel’s vertex-centric parallelism. We base our study on thorough implementations of several fundamen-tal graph algorithms, some of which have, to the best of our knowl-edge, not been implemented on Pregel-like systems before. The algorithms and optimizations we describe are fully implemented in our open-source Pregel implementation. We present detailed exper-iments showing that our optimization techniques improve runtime significantly on a variety of very large graph datasets. 1