  Partitioning the vertices of a (hyper)graph into k roughly balanced blocks
such that few (hyper)edges run between blocks is a key problem for large-scale
distributed processing. A current trend for partitioning huge (hyper)graphs
using low computational resources are streaming algorithms. In this work, we
propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an
adaptation of the widely-known graph-based algorithm Fennel. By using an
efficient data structure, we make the overall running of FREIGHT linearly
dependent on the pin-count of the hypergraph and the memory consumption
linearly dependent on the numbers of nets and blocks. The results of our
extensive experimentation showcase the promising performance of FREIGHT as a
highly efficient and effective solution for streaming hypergraph partitioning.
Our algorithm demonstrates competitive running time with the Hashing algorithm,
with a difference of a maximum factor of four observed on three fourths of the
instances. Significantly, our findings highlight the superiority of FREIGHT
over all existing (buffered) streaming algorithms and even the in-memory
algorithm HYPE, with respect to both cut-net and connectivity measures. This
indicates that our proposed algorithm is a promising hypergraph partitioning
tool to tackle the challenge posed by large-scale and dynamic data processing.

Data Structures and Algorithms