Compressing Hypergraphs using Suffix Sorting
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_ | 1866913033993846784 |
|---|---|
| author | Adler, Enno Böttcher, Stefan Hartel, Rita |
| author_facet | Adler, Enno Böttcher, Stefan Hartel, Rita |
| contents | Hypergraphs model complex, non-binary relationships like co-authorships, social group memberships, and recommendations. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. We propose HyperCSA, a novel compression method for hypergraphs that maintains support for standard queries over the succinct representation. HyperCSA achieves compression ratios of 26% to 79% of the original file size on real-world hypergraphs - outperforming existing methods on all large hypergraphs in our experiments. Additionally, HyperCSA scales to larger datasets than existing approaches. Furthermore, for common real-world hypergraphs, HyperCSA evaluates neighbor queries 6 to 40 times faster than both standard data structures and other hypergraph compression approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05023 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Compressing Hypergraphs using Suffix Sorting Adler, Enno Böttcher, Stefan Hartel, Rita Data Structures and Algorithms Hypergraphs model complex, non-binary relationships like co-authorships, social group memberships, and recommendations. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. We propose HyperCSA, a novel compression method for hypergraphs that maintains support for standard queries over the succinct representation. HyperCSA achieves compression ratios of 26% to 79% of the original file size on real-world hypergraphs - outperforming existing methods on all large hypergraphs in our experiments. Additionally, HyperCSA scales to larger datasets than existing approaches. Furthermore, for common real-world hypergraphs, HyperCSA evaluates neighbor queries 6 to 40 times faster than both standard data structures and other hypergraph compression approaches. |
| title | Compressing Hypergraphs using Suffix Sorting |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.05023 |