The Bloom Filter Idea

A Bloom filter answers one question, "have I seen this key before?", while storing a few bits per key instead of the key. After this lesson your program will hold a 64-bit array, record keys with ADD, answer CHECK, and print the array with BITS so you can see exactly what it remembers.

Two answers, and only one of them is certain

CHECK never says yes or no. It says NO or MAYBE.

• NO is exact. The key was never added. You can skip the disk read, the network call, the slow lookup.
• MAYBE is a hint. The key was probably added, but the filter cannot prove it.

A MAYBE for a key that was never added is a false positive. A NO for a key that was added would be a false negative. A Bloom filter has the first kind and never the second, and the rest of this lesson is why.

The mechanism

The filter is an array of m bits, all 0 at the start, plus k hash functions. Each hash function turns a key into a bit position from 0 to m-1.

1. ADD key: compute the k positions and set those bits to 1.
2. CHECK key: compute the same k positions. If every one of those bits is 1, answer MAYBE. If any is 0, answer NO.

The key itself is never stored. Only the bits it lit up are, which is why the filter is small and why you cannot read the keys back out.

Here m = 64 and k = 2, with two hashes simple enough to work by hand. Both treat the key as bytes, not characters:

• h1(key) is the sum of the key's bytes, mod 64.
• h2(key) is the sum of each byte times its 1-based index, mod 64.

(In UTF-8 the letter é is the two bytes 0xC3 0xA9, and both count.)

A worked trace

fig is the bytes 102, 105, 103.

h1 = 102 + 105 + 103 = 310;  310 mod 64 = 54
h2 = 102*1 + 105*2 + 103*3 = 621;  621 mod 64 = 45

So ADD fig sets bits 54 and 45. Adding lime sets 39 and 25, and date sets 30 and 22. The array now has these positions set: 22, 25, 30, 39, 45, 54. Printed with bit 0 on the left, BITS shows:

0000000000000000000000100100001000000001000001000000001000000000

Now ask about keys that were never added:

• CHECK plum hashes to bits 62 and 27. Bit 62 is 0, so the answer is NO, and that NO is certain.
• CHECK sun hashes to bits 22 and 39. Bit 22 was set by date and bit 39 was set by lime. Both are 1, so the answer is MAYBE, although sun was never added. That is a false positive: two different keys happened to light exactly the bits sun needs.

Why there are no false negatives

Bits only ever go from 0 to 1. ADD never clears anything, so once a key's k bits are set, nothing can unset them, and CHECK for that key keeps answering MAYBE forever. The cost is that as more keys are added more bits turn on, and false positives become more likely.

This also explains why a plain Bloom filter has no REMOVE. The bits you would clear for one key may be the same bits another key relies on, and clearing them would turn that other key's MAYBE into a wrong NO.

Why it is worth it

Real filters use far more than 64 bits, and the next lessons show that about 10 bits per key buys roughly a 1% false-positive rate. The usual job is as a gate in front of something expensive (pseudocode):

if filter.check(key) == NO:  return "not found"     # exact, no disk read
else:                        look the key up for real # MAYBE: confirm

A false positive costs one wasted lookup. A false negative would lose data, which is why the structure is built so that it cannot happen.

Common mistakes

• Answering MAYBE when only one of the two bits is set. CHECK needs all k bits, not any of them.
• Weighting h2 from 0 instead of 1, so the first byte contributes nothing. Check your h2 against the trace above.
• Hashing characters instead of bytes. ADD café must use 5 bytes, not 4 characters.
• Printing the array backwards. BITS prints bit 0 first.
• Splitting the line on every space. The key is everything after the first space, so ADD hello world adds the key hello world.

Your exercise

The starter reads commands and keeps a 64-entry bit array. You write the two hashes and the three commands. Watch h2: it is the hash that tells apart keys with the same letters in a different order.