hesela.devMemento Filter
Memento Filter is a dynamic approximate range-emptiness structure that combines hashed key prefixes with ordered key suffixes.
The suffixes, called mementos, locate keys inside fixed-width partitions. Insertions, deletions and expansion distinguish the design from static SuRF. Choosing r = ceil(log2(R)) suffix bits bounds an inclusive range of at most R integer positions (R >= 2) to two partitions. Longer queries are supported with additional probes, not the same two-partition cost. [1]
The pinned C API returns 0 for a negative query and 1 or 2 for a positive query; 2 additionally indicates possible fingerprint rejuvenation. A positive result still requires an exact backing-store check. [2]
The later Diva evaluation uses a modified Memento baseline with Aleph-style expansion; its measurements must not be attributed to the unmodified original artifact. [3]
Relations
Limitations
- The author header warns that its concurrency features have not been thoroughly tested; API declarations are not an independent concurrency validation. [2]
Citations
- Eslami and Dayan. Memento Filter. PACMMOD 2(6), article 244 (2024). DOI: 10.1145/3698820; sections 4-7, arXiv v3.
- Memento Filter public API: query results, resizing and concurrency disclaimer; commit ded520cebdabfb3f3d640d838c0aee44636453e2.
- Eslami, Bercea and Dayan. Diva: Dynamic Range Filter for Var-Length Keys and Queries. PVLDB 18(11), 2025; sections 2, 5.2. DOI: 10.14778/3749646.3749664.
Further reading
Sources & caveats
- Primary-paper and pinned-source review only; no Memento execution, benchmark reproduction or concurrency experiment. Distinct from the PLDI 2023 Memento persistent-memory framework.