Compressing Hypergraphs using Suffix Sorting
Provides a practical compression method for large hypergraphs, benefiting applications like co-authorship and recommendation systems.
HyperCSA compresses hypergraphs to 26%-79% of original size, outperforming existing methods on large datasets, and speeds up neighbor queries by 6-40x.
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.