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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

HHP: A Hybrid Partitioner for Large-Scale Hypergraph

  • Junlin Shang,
  • Zhenyu Zhang,
  • Wenwen Qu,
  • Xiaoling Wang

摘要

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.