Why it matters

Bloom filters enable cheap approximate lookups. Understanding shapes cache and dedup design.

Advertisement

The architecture

Bit array of m bits, k hash functions.

Insert: hash element with all k; set those bits.

Query: hash element; if any bit unset, absent; else 'maybe present'.

Bloom filter operationBit array minitially all 0k hash functionsfor each elementQueryall bits set → maybeFalse positive rate ~= (1 - e^(-kn/m))^k; tune m, k for target rate
Bloom filter mechanics.
Advertisement

How it works end to end

Sizing: m bits for n elements at fpr p. m = -n ln(p) / (ln 2)². k = m/n × ln 2.

Counting Bloom filter: counts instead of bits; supports deletion.

Applications: Cassandra reads, Google Chrome malware URL, BigTable, Ceph.