hesela.devGrafite range filter
Grafite is an approximate integer-range emptiness filter that stores locality-preserving hash codes in an Elias-Fano representation.
The author's implementation exposes either a target error with a range length or a bits-per-key budget; its separate bucket class is a heuristic filter, not the same guarantee. The size method includes object and encoded-container storage. [2]
For leading budget B, the paper bounds false-positive probability by min(1, ell/2^(B-2)); ell counts possible integer positions, not stored keys. Query time is O(B), hence constant when B is fixed. Lower-order metadata is excluded from that leading budget. [1]
An exact sizing example gives minimum integer leading budgets of 9, 14 and 19 bits per key for lengths 1, 32 and 1024 at a 1% target. This evaluates a bound, not observed FPR or allocated memory. [3]
Relations
Limitations
- A positive answer still needs data verification; a bound of one provides no useful filtering guarantee. [1]
Citations
- Costa, Ferragina and Vinciguerra. Grafite. PACMMOD 2(1), 2024; theorem 3.4, corollary 3.5 and section 6.1. DOI: 10.1145/3639258.
- Grafite author implementation: filter constructors, query and size; pinned commit 6838e9c6f757b300c410e79bc9c608ece2c5f23f.
- Hesela: exact Grafite bound arithmetic and regression tests (CC0)