What it is
At scale, exact answers cost too much memory: counting every distinct user, every key’s frequency, or “have I seen this item” needs state proportional to the data. Probabilistic data structures trade a small, bounded, predictable error for memory that does not grow with the data. Four are worth knowing, each answering a different question:
| Structure | Question it answers | Error | Memory |
|---|---|---|---|
| Count-Min Sketch | ”About how many times has key X occurred?” | Over-estimates, never under | Fixed by the error you want, not by key count |
| Space-Saving (heavy hitters) | “Which keys are the most frequent?” | Bounded over-estimate for the tracked keys | A fixed number of candidate keys |
| HyperLogLog | ”About how many distinct items have I seen?” | A small standard error, typically under 1% | A few kilobytes |
| Bloom filter | ”Have I definitely not seen X?” | False positives, no false negatives | About 10 bits per item for 1% false positives |
Important
Key takeaway: Pick the structure for the question, not the tool you know. A Count-Min Sketch alone cannot list the top-K keys (it stores no keys); a Bloom filter cannot count; HyperLogLog cannot say which items were seen. State the error you accept and the memory it buys.
When you care
Top-K trending, unique visitors, deduplication, and “does this key exist” checks in front of a database all use these. The standard trap is naming Count-Min Sketch for top-K and stopping.
Note
Interview signal: Saying “Count-Min Sketch alone is not enough for top-K, because it cannot enumerate its keys; pair it with a heap, or use Space-Saving” is the senior answer to the top-K question. Adding the memory arithmetic is what makes it concrete.
Count-Min Sketch
Intuition. Count frequencies without a slot per key: use a grid of counters, d rows by w columns, with one hash function per
row. Incrementing a key ticks one cell per row. To estimate a key, read its cell in every row and take the minimum: collisions only
ever inflate a cell, never deflate it, so the minimum is the tightest upper bound.
| col 0 | col 1 | col 2 | col 3 | col 4 | |
|---|---|---|---|---|---|
| row 0 (h₁) | 3 | 1 | 5 | 2 | 0 |
| row 1 (h₂) | 0 | 4 | 1 | 3 | 2 |
| row 2 (h₃) | 2 | 0 | 3 | 1 | 4 |
Estimating #superbowl: the three cells it hashes to hold 5, 4, and 4, so the estimate is min(5, 4, 4) = 4.
Error bounds. With w = ⌈e ÷ ε⌉ columns and d = ⌈ln(1 ÷ δ)⌉ rows, the estimate is within ε × N of the true count (N is the total
number of events) with probability 1 − δ.
Worked example. Take ε = 0.001 and δ = 0.01. Then w ≈ 2,718 and d ≈ 5, so the sketch holds 5 × 2,718 × 4 bytes ≈ 54 KB, however many distinct keys there are. At 1 million events a second for an hour, N is 3.6 billion, so the per-key error is at most about 3.6 million. Keys whose true count is far above that are resolved well; keys below it are indistinguishable. For trending hashtags with counts in the tens of millions, that is plenty. The size depends only on the error you choose, not on the key count.
Space-Saving (heavy hitters)
Keep a fixed-size map of m candidate keys with counts, where m is larger than K (about 10 K for a top-100). On each event:
- If the key is in the map, increment it.
- Else if the map has room, add it with count 1.
- Else evict the minimum-count entry and insert the new key with count
min + 1. The new key inherits the evicted count, which is the “saving”.
Trace with m = 4 over the stream A A B A C D D D E:
| Event | Map after | Action |
|---|---|---|
| A, A | A:2 | insert, then increment |
| B | A:2, B:1 | insert |
| A | A:3, B:1 | increment |
| C | A:3, B:1, C:1 | insert |
| D | A:3, B:1, C:1, D:1 | insert (map full) |
| D, D | A:3, B:1, C:1, D:3 | increment twice |
| E | A:3, C:1, D:3, E:2 | minimum is B (1); evict B; E enters with 1 + 1 = 2 |
A and D are correctly the top two. E is tracked at 2, an over-estimate (its true count is 1), and B is gone. The eviction rule lets a genuinely trending new key surface quickly.
Why not just a Count-Min Sketch with a heap? A heap of candidates fed by the sketch has a latency problem: a new trending key must accumulate enough estimated count to beat the current Kth element before it enters. If 100th place has 150,000, a viral new hashtag must reach that before it appears, possibly minutes behind reality. Space-Saving admits it right away. Keep a Count-Min Sketch alongside for the other question, “how often did key X occur?”, for keys outside the tracked list.
HyperLogLog
Counts distinct items. The idea: hash each item to a bit string and track, per bucket, the longest run of leading zeros seen. A long run is a rare event, so seeing one implies many distinct items were hashed. Averaging across many buckets cuts the variance.
Worked example. With 16,384 registers, a standard HyperLogLog uses about 12 KB and has a standard error of about 0.8%, whether it has seen a thousand items or a billion. Sketches can be merged (take the per-register maximum), so per-day sketches combine into a weekly distinct count without reprocessing. It cannot say which items were seen or remove one.
Bloom filter
A bit array of m bits and k hash functions. To add an item, set k bits. To test, check those k bits: if any is 0, the item is
definitely not present; if all are 1, it is probably present (other items may have set those bits). There are no false negatives
and a tunable false-positive rate of about (1 − e^(−kn/m))^k.
Worked example. At about 10 bits per item with 7 hash functions the false-positive rate is about 1%. A billion items need roughly 10⁹ × 10 bits ≈ 1.25 GB. In front of a database, a Bloom filter of valid keys rejects the 99% of impossible lookups cheaply; LSM storage engines use one per file to skip files that cannot hold the key. It cannot delete an item (a counting variant can, at the cost of more memory) and it cannot count.
When to pick what
| Need | Choose | Why |
|---|---|---|
| Frequency of a given key | Count-Min Sketch | Fixed memory, over-estimate only |
| The top-K most frequent keys, freshness matters | Space-Saving (plus a sketch for point counts) | Admits new keys fast |
| Distinct count (unique visitors) | HyperLogLog | Kilobytes, mergeable |
| ”Is this key possibly in the set?” before an expensive lookup | Bloom filter | No false negatives |
| Exact counts, billing | Not these: exact aggregation, perhaps with a sketch for monitoring | Approximation is unacceptable |
Caution
Common mistake: Using an approximate structure where the numbers become money or a legal claim. These errors are bounded but real: bill from exact aggregates, and use sketches for dashboards, anomaly detection, and capacity decisions.
Related
- Walkthrough: Designing a Top K System — heavy hitters over a firehose, where Count-Min Sketch alone is not enough.
- Reference: Storage Engines — B-Tree, LSM-Tree, and Bitcask — a Bloom filter per file is the LSM-tree’s standard read optimization.
- Reference: Cache Access and Invalidation Patterns — a Bloom filter in front of the database stops cache penetration.