Finding the Heavy Hitters (Top-K)
Finding the most frequent items in a massive data stream (e.g., "Trending Hashtags", "Top 10 IP addresses DDOSing us", "Most viewed videos today") is a classic system design problem known as the Top-K or Heavy Hitters problem.
The Exact Approach
The exact way is to maintain a HashMap of frequencies, and a Min-Heap (Priority Queue) of size K. For every event, update the hash map, then update the heap. If the stream is infinite and the cardinality is high, the HashMap will exhaust memory.
The Probabilistic Approach (Count-Min Sketch + Heap)
A Count-Min Sketch can estimate a supplied key's frequency, but it does not remember every key and therefore cannot discover candidates by itself. Pair it with a bounded candidate algorithm such as Space-Saving, or maintain an explicitly evaluated candidate set. A heap entry also needs updates when its estimate changes; simply inserting every estimate above the current minimum can retain stale entries and duplicates.
Distributed Top-K
Merging only each worker's local K is approximate and can miss the global winner: one key can rank just below K on every shard yet have the largest combined count. Use a mergeable heavy-hitters sketch with a stated error bound, send an oversampled candidate set and obtain global estimates for its union, or compute exact counts when correctness requires it. Partitioning by key makes exact merging easier but can create a hot owner.
Worked example: why local top-K merging fails
Three shards each report their local top 2.
| Key | Shard 1 | Shard 2 | Shard 3 | Global total |
|---|---|---|---|---|
| A | 1,000 | 10 | 10 | 1,020 |
| B | 10 | 1,000 | 10 | 1,020 |
| C | 10 | 10 | 1,000 | 1,020 |
| X | 900, ranked 2nd | 900, ranked 2nd | 900, ranked 2nd | 2,700 |
Here X happens to be second on every shard, so it survives, but with local top 1 it would vanish entirely, even though it is the global winner by a wide margin. The fixes: send an oversampled candidate list, for example top 10 times K from each shard, then ask every shard for the exact counts of the union of candidates; or partition the stream by key so each key's total lives on one node.
Worked example: Space-Saving guarantee
An hour contains N = 1 billion hashtag uses. With k = 10,000 counters, every counter's overestimate is at most N divided by k = 100,000. Any hashtag used more than 100,000 times is guaranteed to be in the summary. Memory: 10,000 entries of key plus two integers, well under 1 MB.
Approaches compared
| Approach | Memory | Accuracy | Notes |
|---|---|---|---|
| Exact hash map plus min-heap | Grows with distinct keys | Exact | Fine when cardinality is millions, not billions |
| Count-Min plus heap of K candidates | Sketch plus K entries | Overestimates by at most epsilon x N | Candidate discovery happens as items stream past |
| Space-Saving, Misra-Gries | k counters | Deterministic bound N divided by k | Mergeable with additive error |
| Batch MapReduce or SQL | Distributed | Exact | Minutes to hours late; used to correct the fast path |
Time windows: keep one summary per minute and merge the last 60 for an hourly view, or use exponential decay, multiplying all counts by a factor such as 0.99 per minute, so trending reflects recent activity. Twitter and similar platforms also normalise against a baseline, because a hashtag that is always popular is not trending.