retrieval-data-structure · research · also static retrieval, static function data structure

Retrieval data structure

A retrieval data structure compactly represents values for a fixed key set without having to recognize queries for keys outside that set.

For a fixed set S with r-bit values, a stored key must return its assigned value. A key outside S may return any r-bit value, including one assigned to a stored key. The structure therefore does not provide the missing-key response of an exact dictionary. [1]

Filter reduction: Store independent, uniform r-bit key fingerprints as values, then compare the retrieved value with the query fingerprint. Stored keys match; a fixed absent key matches with probability 2^-r under the random-function model. For r=8, 1/256 = 0.390625%; this is model arithmetic, not a measured implementation error rate. [1]

BuRR exposes QueryRetrieval and QueryFilter as separate operations. Its retrieval example constructs assigned values, performs back-substitution, and queries those values. Using retrieval output alone as proof of key membership is invalid. [2] [3]

Relations

related: Ribbon filter, XOR filter, Binary fuse filter, Bloom filter, Minimal perfect hash function

Citations

Dillinger and Walzer. Ribbon filter: practically smaller than Bloom and Xor. arXiv:2103.02515v2, section 2. (accessed 2026-11-10)
BuRR: retrieval contract and usage example, commit 2ba071ab728f77d1cebbd14d1f0b9381575730ab. (accessed 2026-11-10)
BuRR ribbon.hpp: QueryRetrieval and QueryFilter, commit 2ba071ab728f77d1cebbd14d1f0b9381575730ab. (accessed 2026-11-10)

Sources & caveats

Source synthesis from the full 2021 paper and pinned BuRR code, not a new implementation or benchmark.
The absent-key probability assumes the stated random fingerprint model; it is not a guarantee for adaptively selected queries. [1]

JSON: /data/terms/retrieval-data-structure.json