Invertible Bloom Lookup Tables With Less Memory And Randomness

Fleischhacker Nils, Larsen Kasper Green, Obremski Maciej, Simkin Mark. Arxiv 2023

[Paper]    
ARXIV Graph Independent

In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1-\delta$, existing IBLT constructions require $\Omega (n(\frac{log(1/\delta )}{log(n)}+1))$ space and they crucially rely on fully random hash functions. We present new constructions of IBLTs that are simultaneously more space efficient and require less randomness. For storing $n$ elements with a failure probability of at most $\delta$, our data structure only requires $\mathcal{O}(n+log(1/\delta )loglog(1/\delta ))$ space and $\mathcal{O}(log(log(n)/\delta ))$-wise independent hash functions. As a key technical ingredient we show that hashing $n$ keys with any $k$-wise independent hash function $h:U\to [Cn]$ for some sufficiently large constant $C$ guarantees with probability $1-2^{-\Omega (k)}$ that at least $n/2$ keys will have a unique hash value. Proving this is highly non-trivial as $k$ approaches $n$. We believe that the techniques used to prove this statement may be of independent interest.

Similar Work

• A Hash Table Without Hash Functions And How To Get The Most Out Of Your Random Bits
• Derandomized Balanced Allocation
• Cuckoo Hashing In Cryptography Optimal Parameters Robustness And Applications
• Approximate Nearest Neighbors In Limited Space