Metraipolis › archive › dc_ba3454e9eac2
Consensus for Compressed Static Functions — arXiv:2609.39557
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.39557
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T15:17:10.351Z
- SHA-256 of the archived text
388807b261b15966accfaa8df11443152d616331a3f4a93077755c98fba31ce7- Stable URL of this page
https://metraipolis.com/documento/dc_ba3454e9eac2
How to cite
Consensus for Compressed Static Functions — arXiv:2609.39557 — arXiv (en), https://arxiv.org/abs/2609.39557 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ba3454e9eac2 (Metraipolis archive dc_ba3454e9eac2, sha256 388807b261b15966accfaa8df11443152d616331a3f4a93077755c98fba31ce7)
BibTeX
@misc{dcba3454e9eac2,
title = {Consensus for Compressed Static Functions — arXiv:2609.39557},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.39557},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ba3454e9eac2; sha256 388807b261b15966accfaa8df11443152d616331a3f4a93077755c98fba31ce7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39557. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The Consensus technique marked a breakthrough in the construction of minimal perfect hash functions (MPHFs), reaching a linear tradeoff between construction time and space overhead relative to the optimum. Consensus provides a clever scheme to search for and encode seeds of tasks in random data structures. We apply Consensus to the related field of compressed static functions (CSFs). These data structures store a function $f: S \to \Sigma$ such that querying a key $x \in S$ returns $f(x)$ and querying $x \not \in S$ returns an arbitrary value. CSFs do not need to store the keys $S$ and only need space close to the zeroth-order empirical entropy of the multiset of values. Often, some values are much more common than others. In these cases, CSFs can use less space than their non-compressed counterparts. CSFs are a useful building block, for example in database design and bioinformatics. We introduce Consensus-CSF, which can reach arbitrarily close to the empirical entropy $n H_0$, with a construction time of $n \exp(\tilde{\cal{O}} (\sqrt{1 / \delta}))$ for space usage of $n H_0 (1 + \delta)$ when assuming some parameters of the value distribution to be constants. This tradeoff beats previously implemented approaches that can only reach some fixed threshold above the entropy lower bound. We enable Consensus in the setting of CSFs, which is less structured than MPHFs, with the introduction of task insertions. Our approach randomly distributes the keys into one-bit Consensus tasks and then strategically inserts additional tasks in places where the construction would get stuck otherwise. We provide an implemented version of our algorithm which reaches the same order of magnitude in space overhead as competitors but is not competitive in practice. Beyond these results, we present a new way to think and reason about Consensus, which may also be applied to other problems.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.39557 — 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:50:37.645Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).