PaperlayerView exact revision on arXiv

Source-linked AI summary

Stuffed IBLTs: Optimal Linear Multiset Sketches

Jonas Klausen, Rasmus Pagh, Stefan Walzer

arXiv:2609.17487v1cs.DS

TL;DR

The paper asks how to recover sparse signed multisets from compact linear sketches while supporting efficient updates, bounded multiplicities, and strong error guarantees. It combines spatial coupling, purity heuristics, and backyarding in a Stuffed IBLT. The resulting sketch approaches the information-theoretic space optimum with fast updates and decoding, while a lower bound identifies an optimal dependence on c for peeling-based approaches.

  • Problem

    Existing linear multiset sketches must balance exact sparse recovery, unrestricted updates, space efficiency, decoding time, and failure probability.

  • Method

    The Stuffed IBLT combines spatial coupling, a purity heuristic, and backyarding within a linear signed-multiset sketch.

  • Results

    The sketch recovers valid inputs with probability 1 − O(n^-c), uses O(c) update time and O(cn) expected decoding time, and can use (1 + O(ε))opt bits under a universe-size condition.

  • Takeaways & Limitations

    The construction approaches information-theoretic storage limits while retaining efficient recovery for sparse signed multisets and supporting applications such as set reconciliation.

  • Takeaways & Limitations

    The lower-bound claim applies to peeling-based sketches under reasonable assumptions, and the authors do not claim optimal dependence on ε.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces linear signed-multiset sketches that exactly recover sparse vectors with bounded multiplicities, while supporting fast unrestricted updates. Its Stuffed IBLT approaches the information-theoretic space bound and establishes a lower-bound barrier for peeling-based designs.

  • Main result: Theorem 1 provides recovery with probability 1 − O(n^-c) for vectors having at most n nonzeros and multiplicities bounded by L.The guarantee applies when the prime p satisfies max{2L + 1, n} ≤ p and n is sufficiently large for c.
  • Main result: The sketch achieves O(c) update time and O(cn) expected decoding time.These bounds are stated for the main construction and scale linearly with the quality parameter c.
  • Main result: When n ≤ |U|^(1−Ω(1)), space can be reduced to (1 + O(ε))opt bits, with update and decoding times increasing by a factor O(1/ε^3).Here opt is the information-theoretic minimum, and ε is any fixed value below 1.
  • Construction: The construction combines spatial coupling, a purity heuristic, and backyarding to approach information-theoretic storage barriers while retaining efficient recovery.The purity heuristic uses hash-based evidence to identify likely pure cells without the overhead of explicit checksums.
  • Lower bound: Theorem 2 indicates that peeling-based multiset sketches require (1 + e^-O(c))n cells under reasonable assumptions, suggesting a barrier for improving dependence on c.The authors caution that the formal lower bound is not robust to approaches that are mostly peeling-based but bypass its definition.
  • Applications: Linear sketches support applications such as straggler identification, set reconciliation, and comparison of similar genomic k-mer multisets.Linearity lets parties combine sketches to recover differences with communication proportional to the number of discrepancies rather than |U|.

2 Overview of our Construction

The construction transforms an idealized peeling sketch into the Stuffed IBLT through four modifications that address purity detection, failure probability, hash-function space, and leftover keys.

  • Overview of our Construction: The final architecture combines spatial coupling, a purity heuristic, layered partitioning, hash-function sharing, quotienting, and a backyard sketch.These steps produce a sequence of auxiliary sketches culminating in the Stuffed IBLT.
  • Starting Point: Spatial Coupling: Spatial coupling reduces the cell count needed for peeling to (1 + e^-Θ(c))n, but the Oracle-Sketch requires a purity oracle, has O(1/n) failure probability, and uses excessive hash-function space.The Oracle-Sketch stores keys in cells corresponding to hypergraph vertices and recovers them when the associated hypergraph is peelable.
  • Step 1: Detecting Purity: The Heuristic-Sketch replaces the purity oracle with a candidate-key test and partitions cells so anomalies corrupt only individual substructures.The heuristic can produce false positives through anomalies, so partitioning limits their damage and leaves only a small number of leftover keys to recover later.
  • Step 2: Reducing the Error Probability: A second partitioning layer reduces failure probability to O(n^-c), while keeping the slower partitioning hash function out of the purity tests.Too many sub-sketches failing simultaneously is bounded by O(n^-c) using Chernoff-like arguments.
  • Steps 3–4: Space Reduction and Backyarding: Quotienting and shared hash functions reduce space, but overloaded substructures leave O(n^(1−ε)) keys unrecoverable; backyarding recovers those leftovers within the memory budget.The backyard uses O(c) more cells than its capacity and fully random hashing on the small leftover key set.

3 Preliminaries

This section defines the sketch parameters, error tolerance, and hash-function requirements used to analyze the construction. It also specifies the resource trade-offs and quotient-hashing interface.

  • Parameters: Capacity n bounds the distinct keys recoverable at decoding, quality c roughly controls locations per key, and stretch ε controls space overhead versus update speed.More hash functions can make sketches more compact and reduce failure probability, while smaller ε lowers space consumption at the cost of slower updates.
  • Notation: The notation ˜O hides polylogarithmic factors in n and factors depending only on c, but running-time bounds retain explicit linear dependence on c.The section uses S for the set of up to n keys present at decoding.
  • Error Tolerance and Failure Probability: Error tolerance t permits at most t wrongly reported keys with failure probability p, while the final sketch has zero error tolerance when it does not fail.A sketch is decoded correctly whenever the wrongful-key set has size at most t.
  • 3.1 Hash Functions: The hash-function family uses capacity m, independence k, and a space parameter ε, providing limited-independence guarantees for fixed and iteratively defined key sets.Its space usage is O(km^ε ε^-3 log m + log |U|) bits, with independence guarantees holding with probability 1 − O(ℓ²/m³).
  • 3.1 Hash Functions: The quotient hash function maps keys invertibly to [b] × [|U|/b], with evaluation and inversion in O(c′) time and O(m^3/4 log |U|) bits of space.For sets of m keys, it also provides a high-probability load-balancing guarantee over buckets.

4 The Data Structure

The data structure builds from a spatially coupled Oracle-Sketch, replaces its purity oracle with a heuristic, and adds partitioning and auxiliary structures to control anomalies and failure probability.

  • 4.1 A Sketch with a Purity Oracle: The cell stores keySum in Fp and count in {−L,…,L}; for a known pure cell, these values identify a key and its nonzero multiplicity.Updates add f to count and f·x to keySum for f copies of key x.
  • 4.1 A Sketch with a Purity Oracle: The Oracle-Sketch uses (1 + e^-Ω(c))n cells, O(c) updates, O(cn) decoding, and recovers the key set with probability 1 − ˜O(n^-1).Its decoding requires O(cn) purity-oracle queries, and its hash functions use ˜O(n^1.1 + log |U|) space.
  • 4.2 The Heuristic-Sketch: The purity heuristic always recognizes pure cells but can mistake several colliding keys for one key when their aggregate keySum and count are consistent with a candidate.Such anomaly structures are defined by nonzero aggregate count and shared cell placement among the contributing keys.
  • 4.2 The Heuristic-Sketch: The Heuristic-Sketch partitions keys across √n Coupled-Sketches, so anomalies affect separate substructures; it achieves ˜O(√n) error tolerance and ˜O(1/n) failure probability.Updates take O(c) time and decoding takes O(cn) expected time.
  • 4.2 The Heuristic-Sketch: When keys are hashed independently and a substructure is not overfull, anomaly probability is ˜O(n^-1/2), yielding Coupled-Sketch failure probability ˜O(n^-1/2).The number of bad Coupled-Sketches exceeds Θ(log n) with probability at most O(1/n).

4.3 A Sketch using Partitioning to Reduce Failure Probability

The construction combines partitioning, quotienting, shared hashing, and a backyard to obtain tunable failure probability, near-optimal space, and efficient operations.

  • Split-Sketch: The Split-Sketch partitions keys across n^(1/3) Heuristic-Sketches, yielding O(n^−c) failure probability, O(c) updates, and O(cn) expected decoding.Its aggregate error tolerance is ˜O(n^(2/3)).
  • Quotient-Sketch: The Quotient-Sketch reduces per-cell key space through quotienting and shared hash functions, while retaining O(n^−c) failure probability and O(c/ε) updates.Its space is (1 + e^−Ω(c/ε))n(log2(2L + 1) + log2(|U|/n^(1−ε))) bits.
  • Backyard: The backyard retrieves residual keys with probability 1 − O(n^−c), supporting O(cε^−3) updates and O(cnε^−3) decoding.
  • The Stuffed IBLT: The Stuffed IBLT recovers vectors with probability 1 − O(n^−c) under ||v||_0 ≤ n and ||v||_∞ ≤ L, with O(c) updates and O(cn) expected decoding.
  • The Stuffed IBLT: (1 + O(ε))opt bits of space are achieved when n ≤ |U|^(1−Ω(1)), with update time O(c/ε^3) and expected decoding time O(cn/ε^3).Here opt is the information-theoretic minimum.

5 Lower Bounds for Peeling-Based Multiset Sketches

The paper formalizes idealized peeling-based multiset sketches and proves trade-offs among update time, failure probability, space, and cell count, while identifying limits of the lower-bound model.

  • Model: The lower bounds apply to IPMSs equipped with a purity oracle, whose configurations decode successfully exactly when the underlying peeling process succeeds.
  • Scope: The barrier is not robust to sketches that combine peeling with other mechanisms or use decoding procedures that differ from the modeled algorithm.The paper nevertheless argues that surpassing the barrier decisively would require fundamentally new ideas.
  • Lower bounds: For an idealized peeling-based sketch, expected update time is Θ(c), failure probability is n^−O(c) when m ≤ n^2, and space is at least m log2(|U| · 2L) bits.
  • Lower bounds: Such sketches require at least m ≥ (1 + e^−2c)n cells, establishing a cell-count overhead that matches the construction up to constants in the exponent.
  • Can the lower bound be beaten?: A faster expected decoder can undercut the modeled decoding-time lower bound by trying a fast sketch first and invoking a slower sketch only after failure.Checking first-stage success may require O(cn log n) checksum bit complexity and word size w ≥ c log n for O(n)-time verification.

6 Conclusion

The paper concludes that its sketches approach information-theoretic storage barriers, while identifying several efficiency, multiplicity, practicality, scaling, error, and implementation questions for future work.

  • The sketches approach information-theoretic barriers for storing multisets with sparse, linear sketches and efficient recovery.
  • The construction supports only limited multiplicity L < p/2 when keys come from Fp, leaving higher-multiplicity applications open.
  • The multilayer structures are currently impractical, with likely very large hidden constants when n is sufficiently large.
  • Open questions include the regime n ≈ U, boosting error probability beyond poly(n) without sacrificing space, and avoiding constant-time finite-field-division assumptions.

A Adapting a Result Regarding Peeling at High Densities

This appendix adapts a spatial-coupling peeling result to obtain explicit overhead and O(1/n) non-peelability error, using bounded differences and a union bound.

  • A hypergraph with n hyperedges sampled from D is peelable with probability 1 − O(1/n).The result supplies the high-density peeling guarantee used by the construction.
  • The theorem’s structured distribution uses a uniformly shifted base position plus independently sampled offsets, with each hyperedge containing at most c positions.
  • The adapted result makes explicit that the overhead m/n − 1 depends on c through an e−Θ(c) term.
  • The first failure event, a small edge obstruction to peelability, occurs with probability at most O(1/n).
  • The second failure event is controlled by applying McDiarmid’s inequality to the bounded-difference function counting vertices remaining after parallel peeling.Changing one hyperedge changes the count by at most D = cR; the resulting probability is bounded by O(1/n).
  • A union bound over the two failure types establishes the overall O(1/n) probability of non-peelability.

B Constructing Small Constant Time Hash Functions

The paper constructs small constant-time hash functions by combining highly independent hashing on a reduced universe with universe reduction, while retaining probabilistic independence guarantees.

  • The resulting hash family uses O(km^ε ε^-3 log m + log |U|) bits of space.
  • For fixed sets of at most m keys, the hash family is k-independent with probability 1 − O(ℓ^2/m^3).
  • For iteratively defined sets of at most k keys, the same independence guarantee holds with probability 1 − O(ℓ^2/m^3).
  • The construction combines highly independent hash functions with universe reduction to support larger universes without the slower execution of direct hashing.
  • The construction starts from a hash function on [n^3] with k-independence and combines it with a random linear map for universe reduction.The cited lemma provides the base hash function, while the reduction handles the larger universe.

B.1 Construction of the Function

The constructed hash function composes a random linear universe reduction with a highly independent hash function, preserving independence on fixed sets unless reduction collisions occur.

  • The construction defines h = g ◦ p, where p maps U to [m^3] and g maps [m^3] to [r].
  • The universe-reduction map p uses O(log |U|) bits and is evaluated in constant time, while g has the stated compact implementation and evaluation bounds.
  • For any fixed set S of at most m keys, h is k-independent with probability at least 1 − ℓ^2/m^3 because collisions under p are the remaining obstruction.
  • Iteratively defined sets observe only final hash values; k-independence of g therefore helps obscure p and prevent adversarial collision construction.

B.2 Independent Hashing of Iteratively Defined Sets

The proof analyzes an adaptive adversary that observes hash outputs and tries to force collisions in the underlying quotient hash. Until a collision occurs, the observed hashes behave as independent random values unrelated to the hidden function p.

  • The adversary wins when some adaptively chosen key collides under p with an earlier key.Conditioning on k-independence of g occurs with probability 1−O(m^-3).
  • Before winning, observed values h(x1), ..., h(xk) are fully random and independent of p.Thus the adversary’s observations do not provide useful information for selecting future keys.

C Quotient Hash Functions

This section presents an invertible quotient hash function that maps each key to two bucket coordinates and makes its efficiency and overflow guarantees explicit. It also supplies the running-time, space, and error-probability details omitted from the earlier presentation.

  • The theorem constructs an invertible hash h: U → [b] × [|U|/b] for m31/32 < b < m.The function maps each key x to (h1(x), h2(x)), enabling inversion.
  • Evaluating h and h−1 takes O(c′) time, while their space usage is O(m3/4 log |U|) bits.
  • For any m-key set S and δ < 1, the theorem gives a probability-1−O(n−c′) guarantee for the bucket-load bound.Buckets are defined by the first hash coordinate, and overflowing buckets contain more than (1 + δ)m/b keys.
  • The construction fills in the earlier work’s unspecified dependence between running time and error probability, as well as its space and overflow bounds.The proof closely follows the earlier construction while making these quantities explicit.

C.1 Construction of the Function

The quotient hash is constructed through several reversible grid transformations: row shifting, within-column permutations, column grouping, and row-group permutations. The final pair h(x) encodes enough transformed coordinates to recover the original key efficiently.

  • The universe is arranged as a grid, then rows are shifted by a compact hash function to obtain column2(x).Given column2(x) and row(x), the original column and key can be recovered in O(c′) time.
  • Independent 2-independent permutations reorder rows within each column, producing row2(x) while preserving recoverability.Each permutation is a linear map, uses O(log |U|) bits, and is invertible in constant time.
  • The construction groups consecutive columns and rows, defining cGroup(x), rGroup(x), and rowIndex(x) so transformed coordinates remain decodable.The number of row groups is G=min{√m,R}, with g=⌈R/G⌉ rows per group.
  • A second permutation independently reorders row groups within each column group before splitting rGroup2(x) between h1(x) and h2(x).This arrangement is designed so the two hash components retain the transformed coordinates needed for inversion.
  • The resulting components satisfy h1(x)∈[b] and h2(x)∈[|U|/b], and all functions use O(m3/4 log |U|) bits and O(c′) evaluation time.The prime-size assumption for the row domain introduces only negligible error terms.

C.2 Bounding the Number of Overflowing Keys

The overflow analysis isolates a small set of abnormal keys, bounds their size, and then analyzes normal keys using concentration inequalities. Combining these bounds yields a high-probability control on total overflowing keys.

  • The first abnormal set removes up to m3/16 keys from each transformed column, leaving at most m1/4 normal keys per column and at most m15/16 keys overall.
  • The second abnormal set contains keys sharing both a transformed column and row group, and has size at most 2m3/4 with probability 1−O(m^-c′).Independence across columns follows from using separate row-shuffling permutations.
  • For a fixed key pair, collision in the row group occurs with probability at most m^-1/2, implying expected second-set size at most m3/4.
  • For normal keys, the number of overflowing keys is at most m exp(−δ2m/(3b)) + m15/16 with probability 1−O(m^-c′).This follows from the bucket-collision bound and concentration across column groups.
  • Normal-key bucket overflow has probability at most exp(−δ2m/(3b)) because each bucket receives a dominated sum of independent variables with mean m/b.
  • Adding abnormal keys contributes at most 6m31/16/b additional overflowing keys, giving the final overflow bound.There are at most 3m15/16 abnormal keys under the preceding events.
Loading 2609.17487v1…