arXiv:2106.07501 · v3

Improved Streaming Algorithm for Balanced Hypergraph Partitioning

首次提交 2021-06-14 23:30

版本更新 2026-11-11 21:46

雷达观测 2026-11-13 14:16

摘要

Balanced hypergraph partitioning is an essential task for massive hypergraph analysis in distributed computing. Existing methods usually use the entire hypergraph to obtain structural information before the assignment process. However, many applications require online partitioning, motivating the development of streaming algorithms. In the streaming order, vertices are assigned in real time and their ownership does not change. Therefore, partitioning the streamed vertices under the balance constraint is challenging. In this paper, we propose a method for balanced hypergraph partitioning in the streaming mode. By defining a modularity function under the Erdos-Renyi random hypergraph model, we build the Erdos-Renyi Hypergraph Modularity Greedy. We approximate the hypergraph as a uniform hypergraph and optimize the modularity function with lower computational complexity. Compared with other modularity functions, our modularity function is more suitable for streaming algorithms. Finally, we design a data structure to reduce the execution time for finding the block with minimum capacity. Overall, our method achieves the state-of-the-art performance when evaluated with the cut-net metric.

作者备注：CIKM 2026