Metraipolis › archive › dc_bd8b71ccb746
The Power of Bidegeneracy for Hypergraph Data Structures — arXiv:2611.04900
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04900
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T12:58:32.852Z
- SHA-256 of the archived text
f37efae54f1c200c892ae05b351abb4970031924d91f469279e3b2408bc72408- Stable URL of this page
https://metraipolis.com/documento/dc_bd8b71ccb746
How to cite
The Power of Bidegeneracy for Hypergraph Data Structures — arXiv:2611.04900 — arXiv (en), https://arxiv.org/abs/2611.04900 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bd8b71ccb746 (Metraipolis archive dc_bd8b71ccb746, sha256 f37efae54f1c200c892ae05b351abb4970031924d91f469279e3b2408bc72408)
BibTeX
@misc{dcbd8b71ccb746,
title = {The Power of Bidegeneracy for Hypergraph Data Structures — arXiv:2611.04900},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04900},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bd8b71ccb746; sha256 f37efae54f1c200c892ae05b351abb4970031924d91f469279e3b2408bc72408},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04900. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$. Hypergraphs are increasingly popular in network science, as they represent interactions between subsets of vertices. A natural challenge is to design a data structure for $H$ to quickly answer basic questions about it, e.g. how many neighbors a vertex $v$ has or whether a hyperedge contains a vertex subset $S$. Such questions are trivial for graphs, for which we simply inspect the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary $H$, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded $\infty$-degeneracy. We show that bounded bidegeneracy yields fast hypergraph data structures. For a large set of fundamental queries, including their listing and sampling versions, we obtain near-linear preprocessing and (poly)logarithmic query time. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that, without assumptions on the input, these structures require almost-quadratic preprocessing or almost-linear query time. We use bidegeneracy to compute a compressed representation of $H$ and perform careful reductions to stabbing and searching problems in $\mathbb{R}^d$. Our framework significantly extends the well-studied "partial matching" problem of finding database entries through wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the complexity of hypergraph primitives. We also find remarkably low bidegeneracy in hypergraph datasets from the literature, suggesting practical consequences.
Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.DB, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Databases (cs.DB); Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2611.04900 — 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-11-04T12:34:17.029Z dalla pagina https://arxiv.org/list/cs.DB/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).