hesela.devLearned Bloom filter
A learned Bloom filter combines a membership classifier with a backup filter containing stored keys that the classifier rejects.
The classifier's positive answer is a candidate, not an exact lookup. Every stored key rejected at the chosen threshold must enter the backup filter; this supplies the no-false-negative property for the represented set, not classifier accuracy alone. The original SIGMOD design evaluates absent queries from a held-out workload. [1]
Let a be the classifier-positive fraction of absent queries and b the backup-positive fraction conditional on classifier rejection. Total FPR is a + (1-a)b. The denominator contains absent queries only. A changed query distribution can change a without changing the stored keys. [2]
A sandwiched design first checks a Bloom filter holding all stored keys, then the classifier and backup. Its exact probability decomposition is p0 times [a0 + (1-a0)b0], where a0 and b0 are conditional on reaching their stages. Using unconditioned rates instead needs a justified model of the hash construction and query selection. [3]
Memory comparisons include the learned model and every filter. Replacing a model or threshold can change which stored keys need backup coverage; revalidate that coverage before publishing the replacement. [1] The sandwiched design trades extra hash work for early rejection; its theoretical space optimum is not a universal throughput result. [2]
Relations
Limitations
- A held-out false-positive rate is not a distribution-free guarantee for later queries. [2]
Citations
- Kraska, Beutel, Chi, Dean and Polyzotis. The Case for Learned Index Structures. SIGMOD 2018, section 5.1. DOI: 10.1145/3183713.3196909.
- Mitzenmacher. A Model for Learned Bloom Filters and Optimizing by Sandwiching. NeurIPS 2018, sections 3-5.
- Hesela: exact hypothetical learned-filter probabilities and conditional-stage counterexample; not a trained-model benchmark.
Sources & caveats
- Primary-source synthesis and an exact rational probability example; no model training, device measurement or paper benchmark replication.