HHP: A Hybrid Partitioner for Large-Scale Hypergraph
摘要
Hypergraphs have diverse applications in building n-ary relationships, and their partitioning is crucial for distributed systems that utilize hypergraph-structured data. Hypergraph partitioners can be classified into offline and online strategies. Offline strategies deliver high-quality results but demand significant time and memory resources. Conversely, online strategies require fewer resources but may produce lower-quality partitions. In this paper, we introduce a novel hypergraph partitioner, the Hybrid Hypergraph Partitioner (HHP), designed to achieve high-quality partitioning with limited resources. HHP adapts resource consumption by splitting the hypergraph into two sub-hypergraphs and completing the partitioning in two steps. First, HHP applies offline partitioning to one sub-hypergraph, followed by an online strategy that uses the stateful information from the first step to partition the remaining sub-hypergraph. Our evaluation of large-scale hypergraphs shows that HHP achieves superior partitioning quality while reducing both time and memory consumption.