We design and implement a distributed algorithm for balanced @math -way hypergraph partitioning that minimizes fanout, a fundamental hypergraph quantity also known as the communication volume and ( @math )-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 @math times bigger on the same set of machines. We call the resulting tool Social Hash Partitioner (SHP), and accompanying this paper, we open-source the most scalable version based on recursive bisection.
There exists a rich literature on graph partitioning from both theoretical and practical points of view. We refer the reader to surveys by Bichot and Siarry @cite_32 and by Bulu c et al. @cite_3 . Next we discuss existing approaches for storage sharding that utilize graph partitioning and review theoretical results on the problem. Then we describe existing libraries for hypergraph partitioning, focusing on the publicly available ones. Finally, we analyze limitations of the tools, which motivate the development of our new solution, SHP .
@cite_32 @cite_3
2113513143 2949888389
In this paper we consider the problem of (k, υ)-balanced graph partitioning - dividing the vertices of a graph into k almost equal size components (each of size less than υ • n k) so that the capacity of edges between different components is minimized. This problem is a natural generalization of several other problems such as minimum bisection, which is the (2,1)-balanced partitioning problem. We present a bicriteria polynomial time approximation algorithm with an O(log2n)-approximation for any constant υ > 1. For υ = 1 we show that no polytime approximation algorithm can guarantee a finite approximation ratio unless P=NP. Previous work has only considered the (k, υ)-balanced partitioning problem for υ ≥ 2. We survey recent trends in practical algorithms for balanced graph partitioning together with applications and future research directions.