Metraipolis › archive › dc_ae8f982a8239
Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance — arXiv:2609.39778
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.39778
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:13:33.491Z
- SHA-256 of the archived text
2c938d0883650d50deaf07789a74ada75aa21967525a46522c1d9114a4516d1e- Stable URL of this page
https://metraipolis.com/documento/dc_ae8f982a8239
How to cite
Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance — arXiv:2609.39778 — arXiv (en), https://arxiv.org/abs/2609.39778 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ae8f982a8239 (Metraipolis archive dc_ae8f982a8239, sha256 2c938d0883650d50deaf07789a74ada75aa21967525a46522c1d9114a4516d1e)
BibTeX
@misc{dcae8f982a8239,
title = {Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance — arXiv:2609.39778},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.39778},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ae8f982a8239; sha256 2c938d0883650d50deaf07789a74ada75aa21967525a46522c1d9114a4516d1e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39778. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm that explicitly maintains a $(1+\epsilon)$-approximate densest subhypergraph under hyperedge insertions and deletions. The algorithm keeps a solution candidate together with an endpoint allocation that bounds the optimum density. The candidate's density guides maintenance: an update triggers repair only when this bound is too large to establish the required approximation. Local searches redistribute load or find a denser candidate, allowing CAP to retain useful solutions across many updates. We give an analysis that relates maintenance work to the size of the regions searched and the density lost by the maintained solution. It identifies conditions under which local repair remains inexpensive and provides a theoretical explanation for the observed efficiency. Experiments on real-world hypergraphs show speedups of up to nearly four orders of magnitude over the evaluated dynamic baselines, while supporting frequent queries and high accuracy. CAP also remains competitive with specialized dynamic graph methods on ordinary graphs, with speedups of up to approximately $64\times$ on the tested workloads. Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-10-01 in cs.DB). Categorie arXiv: Databases (cs.DB). Pagina del lavoro: https://arxiv.org/abs/2609.39778 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-07T14:47:20.138Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).