TY - JOUR
T1 - Optimizing graph algorithms on pregel-like systems
AU - Salihoglu, Semih
AU - Widom, Jennifer
N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: This work was supported by the National Science Foundation(IIS-0904497), the Boeing Corporation, a KAUST research grant,and a research grant from Amazon Web Services.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.
PY - 2014/3/1
Y1 - 2014/3/1
N2 - 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 inefficiencies such as slow convergence or high communication or computation cost, typically due to structural properties of the input graphs such as large diameters or skew in component sizes. We describe several optimization techniques to address these inefficiencies. Our most general technique is based on the idea of performing some serial computation on a tiny fraction of the input graph, complementing Pregel's vertex-centric parallelism. We base our study on thorough implementations of several fundamental graph algorithms, some of which have, to the best of our knowledge, 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 experiments showing that our optimization techniques improve runtime significantly on a variety of very large graph datasets.
AB - 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 inefficiencies such as slow convergence or high communication or computation cost, typically due to structural properties of the input graphs such as large diameters or skew in component sizes. We describe several optimization techniques to address these inefficiencies. Our most general technique is based on the idea of performing some serial computation on a tiny fraction of the input graph, complementing Pregel's vertex-centric parallelism. We base our study on thorough implementations of several fundamental graph algorithms, some of which have, to the best of our knowledge, 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 experiments showing that our optimization techniques improve runtime significantly on a variety of very large graph datasets.
UR - http://hdl.handle.net/10754/599105
UR - http://dl.acm.org/doi/10.14778/2732286.2732294
UR - http://www.scopus.com/inward/record.url?scp=84896850348&partnerID=8YFLogxK
U2 - 10.14778/2732286.2732294
DO - 10.14778/2732286.2732294
M3 - Article
SN - 2150-8097
VL - 7
SP - 577
EP - 588
JO - Proceedings of the VLDB Endowment
JF - Proceedings of the VLDB Endowment
IS - 7
ER -