FREIGHT: Fast Streaming Hypergraph Partitioning
Algorithmica · 2025-03 · 87 (3) · 405-428
DOI: 10.1007/s00453-024-01291-8 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithmica, online erschienen am 03.01.2025. Verfasst von Kamal Eyubov und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Deutsche Forschungsgemeinschaft, Ruprecht-Karls-Universität Heidelberg.
Abstract (Originalsprache)
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 geometric mean runtime within a factor of four compared to the Hashing algorithm. 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.
Förderung
- Deutsche Forschungsgemeinschaft
- Ruprecht-Karls-Universität Heidelberg
Zitieren
APA
Eyubov, K., Faraj, M. F., & Schulz, C. (2025). FREIGHT: Fast Streaming Hypergraph Partitioning. Algorithmica, 87(3), 405-428. https://doi.org/10.1007/s00453-024-01291-8
Vancouver
Eyubov K, Faraj MF, Schulz C. FREIGHT: Fast Streaming Hypergraph Partitioning. Algorithmica. 2025;87(3):405-428. doi:10.1007/s00453-024-01291-8
BibTeX
@article{Eyubov2025,
author = {Eyubov, Kamal and Faraj, Marcelo Fonseca and Schulz, Christian},
title = {FREIGHT: Fast Streaming Hypergraph Partitioning},
journal = {Algorithmica},
year = {2025},
volume = {87},
number = {3},
pages = {405--428},
doi = {10.1007/s00453-024-01291-8}
}
EUVIMED