Bloom filters and count-min sketches

Bloom filters answer “is this key in the set?” using a few bits per key, with an error that only goes one way: the answer is either “definitely absent” or “probably present”. Count-min sketches answer “how often has this item appeared?” from a small, fixed table of counters, and their estimates can be too high but never too low. Both give up exact answers to save memory, and both let you choose the error in advance: a Bloom filter with 10 bits per key is wrong for about 1 % of absent keys, whatever the keys look like. They are used where an exact set or exact counts would not fit in memory, or would cost a slow lookup: skipping disk reads for keys that are not there, or tracking the most frequent search terms in a stream too large to store.

How a Bloom filter works

A Bloom filter, described by Burton Bloom in 1970, is an array of m bits, all 0 at the start, and k hash functions. Adding a key sets the k bits that its hashes point to. Querying a key checks the same k bits: if any of them is 0, the key was never added; if all are 1, it probably was, because those bits may also have been set by other keys.

"""A Bloom filter of 16 bits with 2 hash functions, small enough to print every bit.

The two bit positions of a name come from 64-bit FNV-1a hashes of the name, combined as h1 + i * h2 (mod 16).
"""
M, K = 16, 2


def fnv1a_64(text, seed=0xCBF29CE484222325):
    h = seed
    for byte in text.encode("utf-8"):
        h ^= byte
        h = (h * 0x100000001B3) & 0xFFFFFFFFFFFFFFFF
    return h


def positions(name):
    h1, h2 = fnv1a_64(name), fnv1a_64(name, seed=0x84222325CBF29CE4) | 1
    return [(h1 + i * h2) % M for i in range(K)]


bits = [0] * M
for name in ("asha", "ravi", "meera"):
    for p in positions(name):
        bits[p] = 1
    print(f"add {name!r:8} -> bits {positions(name)}")
print("bit array:", "".join(map(str, bits)), f"({sum(bits)} of {M} bits set)")

for name in ("ravi", "john", "kiran", "farah", "neel", "tara"):
    ps = positions(name)
    if all(bits[p] for p in ps):
        verdict = "probably present" + ("" if name in ("asha", "ravi", "meera") else " (a false positive)")
    else:
        verdict = "definitely absent"
    print(f"query {name!r:8} -> bits {ps}: {verdict}")

add 'asha'   -> bits [10, 9]
add 'ravi'   -> bits [5, 2]
add 'meera'  -> bits [7, 12]
bit array: 0010010101101000 (6 of 16 bits set)
query 'ravi'   -> bits [5, 2]: probably present
query 'john'   -> bits [12, 13]: definitely absent
query 'kiran'  -> bits [10, 7]: probably present (a false positive)
query 'farah'  -> bits [15, 12]: definitely absent
query 'neel'   -> bits [5, 6]: definitely absent
query 'tara'   -> bits [7, 14]: definitely absent

After three names, 6 of the 16 bits were set. “john” hit bit 13, which is 0, so it is certainly absent. “kiran” was never added, yet both of its bits, 10 and 7, had been set by “asha” and “meera”: a false positive. False negatives are impossible, because adding a key sets all of its bits and nothing in a plain Bloom filter ever clears a bit. That is also why a plain filter cannot delete: clearing a key’s bits could clear bits that other keys share.

Two variants come up again below. A counting Bloom filter keeps a small counter instead of a bit in each cell, so that keys can be removed. Double hashing builds all k positions from two hashes, as h1 + i·h2, which Kirsch and Mitzenmacher showed keeps the same false-positive rate in the limit.

How a count-min sketch works

A count-min sketch, introduced by Cormode and Muthukrishnan in 2005, is a table of d rows of w counters, with one hash function per row. Adding an item adds 1 to one counter in every row, the one its row’s hash picks. The estimate for an item is the smallest of its d counters.

"""A count-min sketch of 2 rows by 8 counters, counting a short stream of search terms.

Each row hashes a term to one counter and adds 1 to it; the estimate of a term is the smallest of its counters, so it
can only be too high, never too low.
"""
from collections import Counter

D, W = 2, 8


def fnv1a_64(text, seed):
    h = seed
    for byte in text.encode("utf-8"):
        h ^= byte
        h = (h * 0x100000001B3) & 0xFFFFFFFFFFFFFFFF
    return h


SEEDS = (0xCBF29CE484222325, 0x84222325CBF29CE4)
table = [[0] * W for _ in range(D)]


def add(term):
    for row in range(D):
        table[row][fnv1a_64(term, SEEDS[row]) % W] += 1


def estimate(term):
    return min(table[row][fnv1a_64(term, SEEDS[row]) % W] for row in range(D))


stream = ["cricket", "rain", "cricket", "train", "rain", "cricket", "exam", "cricket", "gold", "rain", "train", "cricket"]
for term in stream:
    add(term)
for row in range(D):
    print(f"row {row}: {table[row]}")
exact = Counter(stream)
for term in sorted(exact, key=lambda t: (-exact[t], t)):
    print(f"{term:>7}: exact {exact[term]}, estimate {estimate(term)}")
print(f"never seen 'chess': estimate {estimate('chess')}")

row 0: [5, 2, 1, 4, 0, 0, 0, 0]
row 1: [0, 0, 4, 5, 0, 0, 2, 1]
cricket: exact 5, estimate 5
   rain: exact 3, estimate 4
  train: exact 2, estimate 2
   exam: exact 1, estimate 1
   gold: exact 1, estimate 4
never seen 'chess': estimate 0

Every counter an item touches includes all of that item’s own arrivals, so no estimate can be below the true count. Other items that land in the same counter only add to it, which is why “rain” was estimated at 4 instead of 3 and “gold” at 4 instead of 1. Taking the smallest counter keeps the error down, because an item would need to collide in every row to be badly overestimated. Count-min sketches estimate counts; they cannot list the items they have seen, because the table keeps no keys.

The formulas, and one worked number

For a Bloom filter with m bits, k hash functions and n keys, the chance that a key never added looks present is about

and it is smallest when k is about (m / n) ln 2. With 10 bits per key, the best k is 7 and p is about 0.82 %, so a filter for a million keys needs about 1.2 MB, against the tens of megabytes an exact set of the same keys would take.

For a count-min sketch over a stream of N items, choosing w = ⌈e / ε⌉ and d = ⌈ln(1 / δ)⌉ means that no estimate falls below the true count, and that each one exceeds it by more than εN with probability at most δ. With ε = 0.001 and δ = 0.01, that is 5 rows of 2,719 counters, whatever the number of distinct items.

Bloom filter, count-min sketch or a hash set?

Storage engines show the trade-off well. LevelDB, an open-source storage library, can keep a Bloom filter for each of its files, and its documentation says that with 10 bits per key the filter cuts the unnecessary disk reads of a lookup by a factor of about 100. A read for a key that a filter rules out never touches that file.

Check yourself

Bloom filters measured: false positives, sizing and deletion Pro: opens with a Pro, Premium or Ultimate pass

Count-min sketches measured: error bounds and heavy hitters Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Bloom filters store set membership in a few bits per key and answer “definitely absent” or “probably present”.
• A plain Bloom filter has no false negatives and cannot delete; counting Bloom filters can, at about four times the memory.
• About 10 bits per key with 7 hash functions gives a false-positive rate near 0.82 %.
• Count-min sketches estimate frequencies from d rows of w counters; estimates are never too low, and too high by more than εN only with probability δ.