Stuffed IBLTs: Optimal Linear Multiset Sketches

Abstract

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\le n$ and $||v|{|}_{\infty }\le 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\ge 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.

Abstract shortened to comply with arXiv requirements