Bloom filter

Burton Howard Bloom conceived it in 1970 ¹. An empty filter is a bit array of m bits, all 0, with k hash functions that each map an element to one position ²³. Adding an element sets its k bits. Testing reads them: any 0 means definitely not in the set ⁴; all 1 means it is in the set or other insertions set those bits by chance, a false positive ⁵. Elements can be added but not removed ⁶.

False positives fall as the array grows and rise as more items go in ¹. Fewer than 10 bits per element give a 1% false positive rate, however many elements there are ², and about 4.8 more bits per element cut that rate tenfold ³. For a given m and n, the k that minimizes false positives is (m/n)·ln 2 ⁴. Google's Guava library defaults to 3% ⁵; in Cassandra a 1% setting takes about three times the memory of 10% ⁶.

Cassandra keeps one per data file so a read can skip files where the row definitely does not exist ¹²; Google Bigtable, HBase and PostgreSQL use them to avoid disk lookups for rows that are not there ³. Akamai's servers use one to keep "one-hit-wonders", objects requested only once, out of their disk caches ⁴. Google Chrome previously used one for malicious URLs: each URL was checked against a local filter first, and only a positive triggered a full check ⁵⁶.