Metraipolis › archive › dc_7d1cbfd8b703
Stuffed IBLTs: Optimal Linear Multiset Sketches — arXiv:2609.17487
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.17487
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T21:59:12.544Z
- SHA-256 of the archived text
d24e152470c01dce5c9b811684a9c7e4d71b704d0723bd1d9707f4e2ec5f17c7- Stable URL of this page
https://metraipolis.com/documento/dc_7d1cbfd8b703
How to cite
Stuffed IBLTs: Optimal Linear Multiset Sketches — arXiv:2609.17487 — arXiv (en), https://arxiv.org/abs/2609.17487 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7d1cbfd8b703 (Metraipolis archive dc_7d1cbfd8b703, sha256 d24e152470c01dce5c9b811684a9c7e4d71b704d0723bd1d9707f4e2ec5f17c7)
BibTeX
@misc{dc7d1cbfd8b703,
title = {Stuffed IBLTs: Optimal Linear Multiset Sketches — arXiv:2609.17487},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.17487},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7d1cbfd8b703; sha256 d24e152470c01dce5c9b811684a9c7e4d71b704d0723bd1d9707f4e2ec5f17c7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17487. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A \emph{linear sketch} is a randomized linear mapping of a vector $v$ to a lower dimensional sketch vector, designed to preserve relevant information about $v$. We consider sketches of vectors $v \in Z^u$ (for $u \in N$), designed for exact recovery of $v$ from its sketch. Concretely, our \emph{Stuffed IBLT} is a linear sketch configured with a capacity $n \in N$ and a multiplicity limit $L \in N$ and will recover $v$ with high probability whenever $||v||_0 \leq n$ and $||v||_\infty \leq L$. The sketch can be maintained efficiently under unrestricted updates to $v$, i.e., $v$ is not subject to any constraints in between decoding requests. This makes the sketch useful for streaming algorithms and for solving the (multi)set reconciliation problem. For any positive constants $c$, $\epsilon$, and for large enough $n$ and $u \geq n^{1+\Omega(1)}$, the space usage of a Stuffed IBLT is within a factor $1+\epsilon$ from the information-theoretic optimum while allowing updates in constant time, and decoding in time $O(n)$ with failure probability $n^{-c}$. This improves the space/time/error probability trade-off over all prior constructions with similar functionality, including the Invertible Bloom Lookup Table (IBLT). The performance of the Stuffed IBLT is essentially the best we could hope for, up to the dependence on $c$ and $\epsilon$. We make the dependence on these parameters explicit, and further show a lower bound demonstrating that the dependence on $c$ is optimal within the class of peeling-based approaches. Our improvement comes from a careful combination of Walzer's spatial coupling technique (SODA '21), the purity heuristic of Houen, Pagh, and Walzer (SOSA '23), and backyarding (Belazzougui, Kucherov, and Walzer, ESA '24; Fleischhacker, Green Larsen, Obremski, and Simkin, ICALP '24), allowing us to eliminate bottlenecks of past approaches.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.17487 — 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-15T21:46:54.584Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).