Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner

Very Large Data Bases Conference (VLDB)


We design and implement a distributed algorithm for balanced k-way hypergraph partitioning that minimizes fanout, a fundamental hypergraph quantity also known as the communication volume and (k − 1)-cut metric, by optimizing a novel objective called probabilistic fanout. This choice allows a simple local search heuristic to achieve comparable solution quality to the best existing hypergraph partitioners. Our algorithm is arbitrarily scalable due to a careful design that controls computational complexity, space complexity, and communication. In practice, we commonly process hypergraphs with billions of vertices and hyperedges in a few hours. We explain how the algorithm’s scalability, both in terms of hypergraph size and bucket count, is limited only by the number of machines available. We perform an extensive comparison to existing distributed hypergraph partitioners and find that our approach is able to optimize hypergraphs roughly 100 times bigger on the same set of machines. We call the resulting tool Social Hash Partitioner, and accompanying this paper, we open-source the most scalable version based on recursive bisection.

Related Publications

All Publications

ArXiv/SSRN - December 28, 2020

Social Distancing During a Pandemic: The Role of Friends

Michael Bailey, Drew Johnston, Martin Koenen, Theresa Kuchler, Dominic Russel, Johannes Stroebel

HPCA - March 3, 2021

Heterogeneous Dataflow Accelerators for Multi-DNN Workloads

Hyoukjun Kwon, Liangzhen La, Michael Pellauer, Tushar Krishna, Yu-Hsin Chen, Vikas Chandra

MLSys - April 8, 2021

CPR: Understanding and Improving Failure Tolerant Training for Deep Learning Recommendation with Partial Recovery

Kiwan Maeng, Shivam Bharuka, Isabel Gao, Mark C. Jeffrey, Vikram Saraph, Bor-Yiing Su, Caroline Trippel, Jiyan Yang, Mike Rabbat, Brandon Lucia, Carole-Jean Wu

AISTATS - April 30, 2021

Accelerating Metropolis-Hastings with Lightweight Inference Compilation

Feynman Liang, Nimar Arora, Nazanin Tehrani, Yucen Li, Michael Tingley, Erik Meijer

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy