2023/02/13 by Kamal Eyubov, Eyubov, Kamal, Marcelo Fonseca Faraj +3 · 1 citation
Computer Science · Mathematics · #Algorithm #Caching and Content Delivery #Combinatorics #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph #Graph Theory and Algorithms #Hash function #Hypergraph #Interconnection Networks and Systems #Key (lock) #Mathematics #Parallel computing #Streaming algorithm #Theoretical computer science
paper · pdf · doi:10.48550/arxiv.2302.06259
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.