Diva range filter
Diva is a dynamic approximate range-emptiness filter that represents variable-length keys using sampled trie keys and compressed infixes.
Its error guarantee depends on a defined class of input distributions; dynamic support alone does not promise an unchanged bound after growth. [1]
The reference API takes an infix-size parameter, a seed and a load factor, not an epsilon argument. The example includes unary-counter space in infix_size and sorts keys before bulk loading. Explicit-length overloads accept binary keys containing zero bytes. [2] [3]
Relations
Citations
- Eslami, Bercea and Dayan. Diva. PVLDB 18(11), 3923-3936 (2025), sections 3-5. DOI: 10.14778/3749646.3749664.
- Diva author implementation: constructors, RangeQuery and ShrinkInfixSize. Commit d0f85b25a90e00e3aeff4391e2f280d11cacb2af.
- Diva author example: sorted bulk loading, infix-size parameter and explicit-length binary keys. Commit d0f85b25a9.
Sources & caveats
- Source review and published-bound arithmetic; no Diva runtime, FPR measurement or benchmark reproduction. Scope: the 2025 design and pinned code, not Diva++.