2026-07-23T12:44:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18365 2024-03-06T11:01:36Z ddc:004 open_access

FREIGHT: Fast Streaming Hypergraph Partitioning Eyubov, Kamal Fonseca Faraj, Marcelo Schulz, Christian Hypergraph partitioning graph partitioning edge partitioning streaming 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kamal Eyubov and Marcelo Fonseca Faraj and Christian Schulz 2023 Is Part Of LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2023.15 urn:nbn:de:0030-drops-183657 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.15 eng https://creativecommons.org/licenses/by/4.0/legalcode