invertible-bloom-lookup-table · research · also IBLT

Invertible Bloom lookup table

An invertible Bloom lookup table is a randomized data structure that supports updates and can list encoded entries with high probability under its sizing assumptions.

Related Observatory article: Invertible Bloom lookup table on hesela.com

Unlike a membership-only filter, an IBLT can recover entries by repeatedly removing decodable cells. Listing can stop with an incomplete result; the configured threshold is not an unconditional guarantee. [1] Different constructions trade memory, randomness and decoding cost differently. [2]

Relations

related

bloom-filter, set-reconciliation, rateless-iblt

Limitations

• An incomplete decode is not evidence that two sets are equal. [1]

Citations

1. Michael T. Goodrich and Michael Mitzenmacher. Invertible Bloom Lookup Tables. arXiv:1101.2245v3 (2015 revision; first submitted 2011), sections 1.3 and 2. (accessed 2026-10-16)
2. Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski and Mark Simkin. Invertible Bloom Lookup Tables with Less Memory and Randomness. ESA 2024. DOI: 10.4230/LIPIcs.ESA.2024.54. (accessed 2026-10-16)
3. Hesela: Replica repair, set reconciliation and record identity (accessed 2026-10-16)

JSON: /data/terms/invertible-bloom-lookup-table.json