Linear sketches enable near optimal exact recovery of sparse integer vectors
Stuffed IBLTs: Optimal Linear Multiset Sketches
Data Structures and Algorithms
Summary
Sometimes you want to keep track of a large list of numbers, but only have space to store a smaller summary. The authors created a new method called Stuffed IBLT that can compactly store and accurately recover lists with only a few nonzero numbers, even when those numbers repeat up to a certain limit. This method improves on older techniques by being more space efficient while allowing quick updates and fast recovery. It is especially useful for streaming data or comparing collections when elements and their counts vary.
What this means in practice
- •For network engineers: Correctly identify differences in network flow counts using compact sketches even when flows vary in number and multiplicity.
- •For database synchronization teams: Efficiently reconcile multisets of records where items can repeat, using minimal storage and fast recovery.
Authors
Jonas Klausen, Rasmus Pagh, Stefan Walzer
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 \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$, $ε$, and for large enough $n$ and $u \geq n^{1+Ω(1)}$, the space usage of a Stuffed IBLT is within a factor $1+ε$ 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 $ε$. 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.