Storage & Databases

Bloom filter

Probabilistic set: "definitely not" or "probably yes" in tiny space.

In plain terms

Burton H. Bloom, 1970. Can give false positives but never false negatives. About 10 bits per item gives a 1% false-positive rate. LevelDB, RocksDB and Cassandra keep one per data file to skip disk reads.

Origin

Burton H. Bloom described it in Communications of the ACM in 1970. His example was a hyphenation program: a small filter of the words that break the usual rules was kept in memory, so the dictionary on disk was read only for words that were probably exceptions. Databases use the same idea today to avoid disk reads.

Where it shows up in production

Cassandra & RocksDB A per-SSTable Bloom filter answers "could this key be here?" without touching disk.
Chrome Safe Browsing (early versions) A Bloom filter of malicious URL prefixes was kept in the browser, with a server check only on a match. It was later replaced by a different compact structure.
Bitcoin (BIP 37) Light wallets sent a Bloom filter of their addresses to full nodes. It leaked more about the wallet than intended and was later replaced (BIP 157 and 158).

On Semicolony

Simulator: bloom filter Simulator: bloom filter Data structures: data structures Data structures: data structures

Sources & further reading

Found this useful?