Prague Stringology Conference 2026
Enno Adler, Stefan Böttcher and Rita Hartel
Updating Permutation-Compressed Hypergraphs
| Abstract: |
| Hypergraphs model complex, non-binary relationships such as co-authorships, social group memberships, and recommendation systems. Like traditional graphs, hypergraphs can grow large, posing challenges for storage, transmission, and query performance. Moreover, the data can change as new papers are published, new social groups form, existing social groups accept or remove members, and new products are published. In this paper, we extend the hypergraph compression method HyperCSA to perform updates of the compressed hypergraph. Dynamic HyperCSA computes the exact compressed hypergraph representation that the steps decompress-update-compress of HyperCSA produce, but is orders of magnitude faster. Thereby, dynamic HyperCSA achieves the same compression ratios of 26 % to 79 % as HyperCSA on the modified, real-world hypergraphs and the query performance of being 6 to 40 times faster on real-world hypergraphs than other approaches. |
| Download paper: |  |
 |
|
| BibTeX reference |