HybHuff: Lossless Compression for Hypergraphs via Entropy-Guided Huffman-Bitwise Coordination
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912439643144192 |
|---|---|
| author | Zhao, Tianyu Zhao, Dongfang Guo, Luanzheng Tallent, Nathan |
| author_facet | Zhao, Tianyu Zhao, Dongfang Guo, Luanzheng Tallent, Nathan |
| contents | Hypergraphs provide a natural representation for many-to-many relationships in data-intensive applications, yet their scalability is often hindered by high memory consumption. While prior work has improved computational efficiency, reducing the space overhead of hypergraph representations remains a major challenge. This paper presents a hybrid compression framework for integer-based hypergraph adjacency formats, which adaptively combines Huffman encoding and bitwise encoding to exploit structural redundancy. We provide a theoretical analysis showing that an optimal encoding ratio exists between the two schemes, and introduce an empirical strategy to approximate this ratio for practical use. Experiments on real-world hypergraphs demonstrate that our method consistently outperforms standard compressors such as Zip and ZFP in compression rate by up to 2.3x with comparable decoding overhead. To assess practical utility, we integrate our framework with three common hypergraph workloads: breadth-first search, PageRank, and k-core label propagation, and show that compression incurs negligible performance loss. Extensive evaluations across four benchmark datasets confirm the efficiency and applicability of our approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15844 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | HybHuff: Lossless Compression for Hypergraphs via Entropy-Guided Huffman-Bitwise Coordination Zhao, Tianyu Zhao, Dongfang Guo, Luanzheng Tallent, Nathan Data Structures and Algorithms Hypergraphs provide a natural representation for many-to-many relationships in data-intensive applications, yet their scalability is often hindered by high memory consumption. While prior work has improved computational efficiency, reducing the space overhead of hypergraph representations remains a major challenge. This paper presents a hybrid compression framework for integer-based hypergraph adjacency formats, which adaptively combines Huffman encoding and bitwise encoding to exploit structural redundancy. We provide a theoretical analysis showing that an optimal encoding ratio exists between the two schemes, and introduce an empirical strategy to approximate this ratio for practical use. Experiments on real-world hypergraphs demonstrate that our method consistently outperforms standard compressors such as Zip and ZFP in compression rate by up to 2.3x with comparable decoding overhead. To assess practical utility, we integrate our framework with three common hypergraph workloads: breadth-first search, PageRank, and k-core label propagation, and show that compression incurs negligible performance loss. Extensive evaluations across four benchmark datasets confirm the efficiency and applicability of our approach. |
| title | HybHuff: Lossless Compression for Hypergraphs via Entropy-Guided Huffman-Bitwise Coordination |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.15844 |