Bloom filters

A set of a million long strings takes a lot of memory. A Bloom filter answers “have I seen this?” using about 10 bits per item, whatever the size of the items. The cost is that it is sometimes wrong, but only in one direction, and you can choose how often.

Bits instead of keys

A Bloom filter (named after Burton Bloom, 1970) is an array of m bits, all 0 at the start, together with k different hash functions. Each hash function maps an item to a position from 0 to m − 1.

• Add an item: compute its k positions and set those bits to 1.
• Ask about an item: compute its k positions. If any of those bits is 0, say “no”. If all are 1, say “maybe”.

The filter never stores the items. It cannot list them, and it does not care how long they are. Step through three adds and three questions:

The k hash functions do not need to be truly different functions. A trick called double hashing makes all k positions from two hash values a and b: the positions are a, a + b, a + 2b, …, each taken % m. This is what the figure and practice HASH-P6 use.

def positions(word, m, k):
    a, b = h1(word), h2(word)            # two hash values
    return [(a + i * b) % m for i in range(k)]

No is sure, yes is maybe

When an item is added, its bits become 1, and nothing ever sets a bit back to 0. So if any of an item’s bits is 0, the item was surely never added. A “no” is always right.

A “maybe” can be wrong. Other items may have set all k bits between them, as owl and dog did for bee in the figure. A wrong “maybe” is called a false positive. The opposite mistake, a wrong “no”, is called a false negative, and a Bloom filter never makes it.

You cannot remove an item. Clearing its bits might clear a bit that another item needs, and that would create a false negative. A counting Bloom filter keeps a small counter instead of each bit: add raises the counters, remove lowers them, and a position counts as set while its counter is above 0.

How often it is wrong

Assume each hash position is a random bit, as in lesson 2. One position misses a particular bit with chance 1 − 1/m. Adding n items makes k·n positions, so the bit is still 0 with chance (1 − 1/m)^k·n. That means k·n copies of 1 − 1/m multiplied together.

There is a simpler form. The number e, about 2.718, has this property: when m is large, (1 − 1/m)^m is very close to 1/e. So the chance that a bit is still 0 is close to e^−k·n/m, which means 1 divided by e raised to the power k·n/m. In Python this is math.exp(-k * n / m).

An item that was never added gets a false “maybe” when all k of its bits are 1. Treating the bits as independent, that happens with chance

rate = (1 - math.exp(-k * n / m)) ** k     # about the false positive rate

Here ** k raises the result to the power k: it multiplies the result by itself k times. Too few hash functions, and each question checks too few bits. Too many, and the array fills with 1s. The best number turns out to be k = (m/n) · ln 2, about 0.69 · m/n, where ln 2 ≈ 0.693 is the power you raise e to in order to get 2. With that k, about half the bits end up as 1. The table shows the rate for a few sizes:

About 9.6 bits per item give a 1% rate, and every extra 4.8 bits per item divide the rate by 10. Compare a Python set of short strings, which needs roughly 100 bytes, or 800 bits, per item. Both add and the question take O(k) time, whatever the number of items.

Where they are used

A Bloom filter is useful when a “no” saves slow work, and an occasional wrong “maybe” only costs a little time:

• Databases such as LevelDB, RocksDB and Cassandra keep a filter for each file on disk. Before reading a file to look for a key, they ask its filter. A “no” skips the slow disk read.
• Web caches use a filter to avoid storing pages that are asked for only once: a page is stored on its second request, when the filter already says “maybe”.
• Spell checkers and blocklists keep a large list of words or bad addresses in little memory. A “maybe” is then checked against the full list, which is rarely needed.

In each case a false positive leads to a check that was not needed, never to a wrong final answer. That is the rule for using a Bloom filter: let it rule things out, and confirm what it lets through.