The Probabilistic Data Structure Family

In one line

Bloom, Counting Bloom, Cuckoo, Quotient and Xor filters answer membership; HyperLogLog estimates distinct counts; Count-Min Sketch estimates frequencies; Top-K finds heavy hitters. Choose by the question you need answered, then by deletion needs and memory.

0/3 · 0%

Think of it like this

Different tools for different questions about a crowd. A guest list answers "is this person invited?", a clicker at the door answers "how many different people came?", a tally sheet answers "how many times did each person come back?", and a leaderboard answers "who came most often?".

Key ideas

01
Membership ("is x in the set?"): Bloom filter (bit array, no deletes), Counting Bloom filter (counters, deletes, ~4× memory), Cuckoo filter (fingerprints in buckets, deletes, often smaller at low error rates), Quotient filter (fingerprints in a hash table, deletes, mergeable, resizable), Xor/Ribbon/binary fuse filters (static sets, smallest and fastest lookups).
02
Cardinality ("how many distinct?"): HyperLogLog, about 0.81% standard error in 12 KB in Redis's implementation, regardless of count. It can't answer membership.
03
Frequency ("how many times?"): Count-Min Sketch, a grid of counters that never under-counts and over-counts by a bounded amount.
04
Heavy hitters ("which items are most frequent?"): Top-K sketches (for example HeavyKeeper in Redis) or Count-Min plus a heap.
05
All of them trade exactness for fixed, small memory. None of them stores the original items, so none can list what's inside.

Code & diagrams

family.txttext

Structure            Question              Deletes  False +  False -  Notes
Bloom filter         is x a member?        no       yes      no       simplest, bit array
Counting Bloom       is x a member?        yes      yes      no*      ~4x memory (4-bit counters)
Cuckoo filter        is x a member?        yes      yes      no*      fingerprints, ~95% load
Quotient filter      is x a member?        yes      yes      no*      resizable, mergeable
Xor / binary fuse    is x a member?        no       yes      no       static sets only, smallest
HyperLogLog          how many distinct?    no       n/a      n/a      ~0.81% error in 12 KB
Count-Min Sketch     how many times x?     no**     over-count        never under-counts
Top-K (HeavyKeeper)  most frequent items?  no       approx            heavy hitters
* only if you delete items that were really inserted   ** conservative update variants exist

Explain it without notes

Why can't HyperLogLog answer "is user 42 in the set"?

Practice

Pick the right structure: (a) daily unique visitors, (b) has this email already been sent a promo, (c) top 10 searched terms this hour, (d) how many times did IP X hit the login endpoint.

Trade-offs

↔
Picking the wrong family (for example Bloom for counting) can't be fixed by tuning; start from the question.

Done when you can

I can match membership, cardinality, frequency and heavy-hitter questions to the right structure.