Chapter II: Databases & Data Modeling
Bloom Filters
A probabilistic structure that tests set membership with no false negatives.
In short
A Bloom filter is a space-efficient probabilistic structure that answers "is this item in the set?" with no false negatives.
Loading diagram…
Key takeaways
- No false negatives, but possible false positives.
- Great as a cheap pre-check before an expensive lookup.
- Standard Bloom filters support insert and query, not delete.