A Scalable Distributed Graph Partitioner


Margo, Daniel W., and Margo I. Seltzer. 2015. “A Scalable Distributed Graph Partitioner .” Proceedings of the VLDB Endowment. Kohala Coast, Hawaii: The VLDB Endowment, 8, 1478-1489. Copy at http://www.tinyurl.com/mulnnk4


We present Scalable Host-tree Embeddings for Efficient Partitioning (Sheep), a distributed graph partitioning algorithm capable of handling graphs that far exceed main memory. Sheep produces high quality edge partitions an order of magnitude faster than both state of the art offline (eg, METIS) and streaming partitioners (eg, Fennel). Sheep’s partitions are independent of the input graph distribution, which means that graph elements can be assigned to processing nodes arbitrarily without affecting the partition quality.

Last updated on 01/06/2017