bloom-filter · shipping · also Bloom membership filter

Bloom filter

A compact approximate-membership structure that can reject absent keys but may report a false positive, without false negatives for correctly inserted keys in an intact standard filter.

A positive answer requires checking the underlying data. The false-positive denominator is queries for keys absent from the represented set, not all queries. This is not an integrity checksum.

Relations

related

lsm-tree, sstable

Citations

1. Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13(7), 422-426 (1970), method 2. DOI: 10.1145/362686.362692. (accessed 2026-10-12)
2. RocksDB project. RocksDB Bloom Filter: statistics, full filters and implementation trade-offs. Documentation reviewed 12 October 2026. (accessed 2026-10-12)
3. Hesela: Bloom filters and the cost of an absent LSM lookup (accessed 2026-10-12)

JSON: /data/terms/bloom-filter.json