Count-Min sketch

Why it matters

"Which hashtags are trending right now", "which IPs are hammering the API", "which products were viewed most this hour": each needs a count per key over a stream with millions of distinct keys. An exact hash map of counters grows with the number of keys and must be sharded, synchronised and eventually spilled to disk. A Count-Min sketch gives every key's count within a small error using a fixed few kilobytes, updates in constant time, and sums across machines by adding arrays. It is the structure that makes streaming analytics cheap.

The idea

A Count-Min sketch is a two-dimensional array of counters with d rows and w columns, plus d independent hash functions, one per row. To add a key (with count 1 or any amount), hash it with each row's function and increment the counter at that column in that row. To estimate a key's count, hash it the same way and take the minimum of the d counters. Collisions only ever add to a counter, so every row overestimates; taking the minimum picks the row where this key collided least. The estimate is never below the true count and rarely far above it.

Sizing from the error you accept

Two parameters set the guarantee. Width w controls the error: with probability at least 1 minus delta, the estimate exceeds the true count by at most epsilon times the total count N, where epsilon is about e divided by w. Depth d controls the confidence: delta is about 1 divided by e to the power d. So w of 2,000 gives epsilon around 0.14 percent of N, and d of 5 gives delta under 1 percent. A sketch of 5 rows by 2,000 columns is 10,000 counters, 40 KB with 32-bit counters, regardless of how many distinct keys flow through it.

Want	Set	Cost
Error within 0.1% of total count	w ≈ 2,718	More columns
Error within 1% of total count	w ≈ 272	Few columns
99% confidence	d ≈ 5	5 hashes per update
99.99% confidence	d ≈ 9	9 hashes per update

The error is relative to the total stream volume, not to the key's own count, so rare keys are estimated poorly in relative terms and frequent keys very well. That is exactly the right shape for finding heavy hitters.

Heavy hitters and top-k

The sketch alone cannot list keys; it only answers "how many for this key". To find the most frequent items, pair it with a small min-heap of candidate keys: on each arrival, update the sketch, estimate the key's count, and if it exceeds the heap's minimum, insert or update it in the heap (bounded to k entries). The heap holds the current top-k with sketch-estimated counts. For "trending", keep one sketch per time window (sliding or tumbling) and compare recent windows to older ones.

Merging across machines

Two sketches with the same dimensions and hash functions merge by adding their counters element-wise, and the result is exactly the sketch of the combined stream. So each server keeps a local sketch and ships it to an aggregator every few seconds; the aggregator sums. No coordination, no per-key shuffling, fixed bandwidth. The same property lets you keep per-minute sketches and sum them into hourly ones.

Variants and relatives

Conservative update increments only the counters equal to the current minimum, tightening estimates at the cost of losing mergeability. Count sketch uses signed updates to give unbiased estimates with both over and under counts. For "how many distinct keys" rather than "how many of this key", HyperLogLog, next lesson, is the tool; for "is this key present", Bloom and cuckoo filters.