LESSON 23.3
Count-min sketch and top-K
Estimate how often each item appears in a stream, find the heavy hitters, and build trending lists without storing a counter for everything.
7 min read
"Which songs are played most right now?" "Which IPs are sending the most requests?" "Which hashtags are trending?" These heavy hitter and frequency questions come up constantly. Keeping an exact counter per distinct item can need billions of counters. A count-min sketch gives frequency estimates in fixed memory, and with a small heap it finds the top K.
How a count-min sketch works
The sketch is a table of counters with d rows and w columns, and one hash function per row.
- Add an item: for each row, hash the item to a column and increment that counter.
- Estimate an item's count: look up its counter in every row and take the minimum.
- Collisions only ever add to a counter, so every row overestimates. The minimum is the least polluted.
- Widtherror at most ε × total count
- w = ⌈e / ε⌉
- Depthholds with probability 1 − δ
- d = ⌈ln(1/δ)⌉
- Example: ε = 0.1%, δ = 1%~13,600 counters, ~54 KB at 4 bytes
- w ≈ 2,719, d = 5
The error is relative to the total stream size, so the sketch is accurate for frequent items and nearly useless for rare ones. That's exactly what heavy hitter problems need.
Finding the top K
- For each event, add it to the sketch and read back its estimated count.
- If the item is already in the heap, update its count. Otherwise, if its estimate exceeds the heap's minimum (or the heap has fewer than K items), insert it and evict the minimum.
- Read the heap whenever you need the current top K.
Alternatives such as the Space-Saving algorithm (keep K counters; when a new item arrives and all are taken, replace the smallest and inherit its count) give similar results and are common in stream processors.
At scale
Exact counts in a stream processor
- Exact
- State grows with distinct items
Pick it when: Moderate cardinality, or results used for money.
Sketch + heap per partition, then merge
- Fixed memory
- Parallel
- Approximate
Pick it when: Trending, monitoring, abuse detection at huge volume.
Batch job over the event log
- Exact and reprocessable
- Minutes to hours of delay
Pick it when: Daily charts; also to correct the fast path.
Sketches with the same dimensions and hash functions merge by adding their tables cell by cell, so each partition can count its share and a final stage combines them. Combine a fast approximate path with an exact batch path when the numbers matter later, the lambda-style split from the stream processing lesson.
Time windows
Trending needs recency. Options:
- Tumbling windows: one sketch per minute, combine the last 60 for the hour.
- Exponential decay: periodically multiply all counters by a factor below 1, so old counts fade smoothly.
- Compare with a baseline: trending is about acceleration, so rank by the ratio of this hour to the usual rate, not raw count.
Try it
Real-time Leaderboard HLD
Rank players or items by score in real time.