TY - GEN
T1 - Partitioning Trillion-Edge Graphs in Minutes
AU - Slota, George M.
AU - Rajamanickam, Sivasankaran
AU - Devine, Karen
AU - Madduri, Kamesh
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/30
Y1 - 2017/6/30
N2 - We introduce XtraPuLP, a new distributed-memory graph partitioner designed to process trillion-edge graphs. XtraPuLP is based on the scalable label propagation community detection technique, which has been demonstrated as a viable means to produce high quality partitions with minimal computation time. On a collection of large sparse graphs, we show that XtraPuLP partitioning quality is comparable to state-of-the-art partitioning methods. We also demonstrate that XtraPuLP can produce partitions of real-world graphs with billion+ vertices in minutes. Further, we show that using XtraPuLP partitions for distributed-memory graph analytics leads to significant end-to-end execution time reduction.
AB - We introduce XtraPuLP, a new distributed-memory graph partitioner designed to process trillion-edge graphs. XtraPuLP is based on the scalable label propagation community detection technique, which has been demonstrated as a viable means to produce high quality partitions with minimal computation time. On a collection of large sparse graphs, we show that XtraPuLP partitioning quality is comparable to state-of-the-art partitioning methods. We also demonstrate that XtraPuLP can produce partitions of real-world graphs with billion+ vertices in minutes. Further, we show that using XtraPuLP partitions for distributed-memory graph analytics leads to significant end-to-end execution time reduction.
UR - http://www.scopus.com/inward/record.url?scp=85027726099&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027726099&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2017.95
DO - 10.1109/IPDPS.2017.95
M3 - Conference contribution
AN - SCOPUS:85027726099
T3 - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017
SP - 646
EP - 655
BT - Proceedings - 2017 IEEE 31st International Parallel and Distributed Processing Symposium, IPDPS 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 31st IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017
Y2 - 29 May 2017 through 2 June 2017
ER -