Bloom filters: a sure no, or a maybe

A web crawler has fetched a billion pages, and each holds more links. Before following one it asks: have I been here already? A hash set of every URL would answer exactly, but it keeps every URL in full: at 60 characters each, 60 GB before any overhead.

A Bloom filter answers in about 10 bits per URL, 1.25 GB for the billion, and keeps no URLs at all. It pays in certainty, but only in one direction: "definitely not" is always true, while "probably present" is now and then wrong, which costs the crawler the odd page it never fetched.

bit array

m bits, numbered 0 to m − 1, all 0 at the start. They are everything the filter keeps: no items, no keys.

hash functions

k different functions that each turn an item into a bit position, hᵢ(x) mod m. The same item always gets the same k positions, and two of them can land on the same bit.

add

Switch on the item's k bits. A bit that is already 1 stays 1.

test

Look at the same k bits. Any 0 means "definitely not"; all 1s means "probably present".

false positive

"Probably present" for an item that was never added, because other items happened to switch on all of its bits. The opposite mistake, a false negative, can't happen.

This filter has m = 16 bits and k = 3 hash functions: the polynomial hash from the hash table lesson, with three different bases, 31, 37 and 41. Base 31 turns “cat” into 98262, the number the hash table used; bases 37 and 41 give 139236 and 170512. Mod 16, those pick bits 6, 4 and 0.

Words share bits, and nothing records which word switched a bit on. (The demo lists the words added only to flag mistakes; a real filter keeps no list.) A test looks at the same positions.

A 0 is proof: had “cow” been added, bit 11 would be 1, so the test stops at the first 0. All 1s proves much less: every added word looks like that, but so does a word whose bits others switched on.

The more a filter holds, the more bits are on, and the more often a word never added finds all of its bits on by chance.

That 46.9% comes from a short calculation. After n adds, a given bit is still 0 with a chance of about $e^{-kn/m}$, so a word that was never added finds all k of its bits on with a chance of about $(1 - e^{-kn/m})^k$: 8.0% for this filter with three words, 46.9% with eight. Real filters have millions of bits, but fill up the same way.

This filter holds “cat”, “dog” and “owl”, with bits 0, 2, 4, 6, 10 and 12 on. Test four words, one at a time: “fox”, “bee”, “owl” and “pig”. Before each answer, look at the three bits the word picks and predict what the filter will say: it sees only bits, never the words that set them.

Here is a whole Bloom filter: 10 bits and two hash functions. Real hashes mix every letter; to keep this one easy to follow, each reads one letter: positions returns the last digit of the first letter's code and the last digit of the last letter's code. Codes run from 97 for a to 122 for z, so c (99) picks bit 9, t (116) bit 6, d (100) bit 0, g (103) bit 3 and b (98) bit 8. The program adds “cat” and “dog”, then tests “cab” and “cog”.

def positions(word):
    return [ord(word[0]) % 10, ord(word[-1]) % 10]

def add(bits, word):
    for p in positions(word):
        bits[p] = 1

def test(bits, word):
    for p in positions(word):
        if bits[p] == 0:
            return 'definitely not'
    return 'probably present'

bits = [0] * 10
add(bits, 'cat')
add(bits, 'dog')
print(test(bits, 'cab'))
print(test(bits, 'cog'))

A Bloom filter earns its place in front of something slow: "definitely not" skips the slow step, and a wrong "probably" must be cheap, either because an exact check follows or because acting on it costs little.

• An LSM tree keeps a filter in memory for each table on disk and reads only the tables whose filter says "probably": a false positive wastes one read.
• A crawler skips links its filter has seen: a false positive skips one unfetched page.
• A cache can store an object only on its second request, with a filter remembering first requests, so one-off requests never push out popular ones.

The same design explains what a filter can't do. It can't list its items: it never kept them. It can't grow: hᵢ(x) mod m changes with m, and with no items there is nothing to rehash, so an overfull filter is rebuilt from the original data. And it can't delete, though the obvious way to try looks harmless.

Sizing a filter means choosing m/n, the bits per item, and k. The best k is about (m/n) ln 2, roughly 0.69 × m/n, which leaves half the bits on once the filter is full. Then 9.6 bits per item give 1% false positives (with 7 hash functions), and each further 4.8 bits per item divides the rate by ten. The items' size doesn't matter: a 2 KB document costs the same 9.6 bits as a three-letter word.

• A Bloom filter is m bits and k hash functions. Add switches on an item's k bits and test looks at them: both O(k), however many items it holds, and no items are stored.
• "Definitely not" is always true, because bits are never switched off. "Probably present" can be a false positive.
• The false-positive rate, about $(1 - e^{-kn/m})^k$, rises as the filter fills. With the best k, about 0.69 × m/n, 9.6 bits per item give 1%.
• It can't list, delete or grow: clearing bits erases parts of other items, and growing needs the items it never kept.
• Use it as a cheap check in front of something expensive, never alone where a wrong yes is unacceptable. A hash set is exact.
• Next: storage engines, where every table of an LSM tree sits behind a Bloom filter. Spot a Repeated Number and Longest Run of Consecutive Values need exact answers to "seen it?", so they call for a hash set, not a filter. Open the Bloom filter visualiser to test your own words.