Count-Min Sketch & top-K

A music service shows a "trending now" chart for each of 200 countries, refreshed every minute. In a busy country, 5 million plays an hour are spread over about a million different tracks. To rank them, the service needs a play count per track, per country, per minute, and the hour's chart is built from the last 60 minutes.

An exact counter per track costs about 16 bytes, an 8-byte track ID and an 8-byte count, before any hash-map overhead:

Most of it is wasted. Play counts are extremely skewed: a few hit songs take a large share of plays, and most tracks are played once or twice an hour (Hot partitions & skew). The chart only needs the counts of the few leaders, but nobody knows in advance which tracks those are. Two kinds of structure solve this: a Count-Min Sketch estimates any track's count in fixed memory, and a top-K structure keeps just the leaders.

A Count-Min Sketch is a grid of counters, d rows of w counters each, all starting at zero, with a different hash function per row. Each play of a track adds 1 to one counter in every row, the one its hash picks. To read a track's count, look at the same d counters and take the minimum:

Why the minimum? Every counter "Night Drive" touches includes all of its plays, plus the plays of any other tracks that hashed to the same counter. Collisions can only add, so every one of the d counters is at least the true count, and the smallest is the closest. That gives the sketch its defining property: it never underestimates. A track estimated at 3,000 plays was played at most 3,000 times.

It also can't list anything. The sketch answers "how many times was this track played?" for a track you name, but it holds no track IDs, so it can't say which tracks are on top. That needs the top-K structures later on this page.

The sketch is sized from two numbers: an error ε as a fraction of all updates, and a failure probability δ:

• Width w = ⌈e ÷ ε⌉, where e ≈ 2.718.
• Depth d = ⌈ln(1 ÷ δ)⌉.
• Guarantee: the estimate is never below the true count, and with probability at least 1 − δ it is at most the true count + ε × N, where N is the total of all updates.

For the chart, ε = 0.001 and δ = 1% give w = ⌈2,718.3⌉ = 2,719 and d = ⌈ln 100⌉ = ⌈4.61⌉ = 5: 13,595 counters, about 54 KB at 4 bytes each, whether there are a thousand tracks or a billion. With N = 5 million plays, each estimate is at most 0.001 × 5,000,000 = 5,000 too high, with 99% confidence.

The bound is the same 5,000 for every track, and that is the key to using a Count-Min Sketch well. A simulated hour of 5 million plays over a million tracks, with a skewed popularity curve, shows the effect:

The top track is counted almost exactly; a track played 36 times reads as 648. Every error stayed under the 5,000 bound, the largest was 2,774, and they averaged 787. So treat estimates below a threshold around ε × N as noise. That suits a trending chart perfectly: it only cares about the head of the curve, where the error is a tiny share of the count.

When counts only ever increase, a small change helps further. A conservative update raises only the counters that hold the current minimum, and only as far as the new minimum, instead of adding 1 to all d counters. The estimate still never falls below the truth, but other tracks' plays pile up less:

The chart needs the 50 most played tracks, and a sketch can't list them. There are two classic ways to keep a list of leaders:

• Sketch plus heap. On each play, update the Count-Min Sketch, read the track's estimate, and keep a min-heap of the K tracks with the highest estimates. If the new estimate beats the smallest in the heap, it replaces it.
• A fixed set of counters. Keep m counters with track IDs, and nothing else. Space-Saving is the best-known algorithm of this kind.

Space-Saving's rule is short. If the track already has a counter, add 1. If not, and a counter is free, start it at 1. If all m counters are taken, give the newcomer the benefit of the doubt: it takes over the smallest counter and adds 1 to it, recording the old value as its possible overcount. With three counters:

Two guarantees follow. Every count is at most the smallest counter too high, and the smallest counter is at most N ÷ m. And any track played more times than the smallest counter is certain to be in the list. In the same simulation, 1,000 counters gave:

A thousand counters, a few tens of kilobytes, reproduced the exact top 100 of a million tracks. The skew that makes exact counting wasteful is exactly what makes these structures accurate: the leaders are far ahead, so the small tracks that cycle through the bottom counters never displace them.

Plays arrive at dozens of servers, and the chart covers a sliding hour. Count-Min Sketches handle both, because counting is addition: if two sketches use the same width, depth and hash functions, adding them counter by counter gives exactly the sketch of both streams together.

Redis's CMS.MERGE does the addition, and requires all sketches to have identical width and depth.

Top-K lists combine less neatly, because each list has already forgotten the tracks it dropped. Two common answers: send each server's candidates to the aggregator and look their counts up in the merged sketch, or use a structure that forgets on purpose. HeavyKeeper, behind Redis's Top-K, makes counters of small items decay away probabilistically as other items collide with them, while large items are barely affected, so the leaders stay and the noise fades. For windows in general, see Stream processing.

Typical uses share one shape: a skewed stream where the big items matter. Trending songs, searches and hashtags; the IP addresses sending the most requests, to spot abuse early (Rate limiting algorithms); the hottest cache or database keys (Hot partitions & skew); network flows. Redis provides both structures, CMS.INITBYPROB to size a sketch from an error and a probability, and TOPK.RESERVE for HeavyKeeper. BigQuery's APPROX_TOP_COUNT returns approximate top elements in a query.

For the music service, the checklist:

• Size from ε and δ: w = ⌈e ÷ ε⌉, d = ⌈ln(1 ÷ δ)⌉, and remember the error is ε × the whole stream.
• Ignore estimates below about ε × N; they are mostly collisions.
• Keep leaders in a top-K structure, and use the sketch to check their counts.
• One sketch per server per minute, same dimensions and hashes, added into windows.
• Use conservative updates where counts only grow.
• Never use estimates where exactness matters, such as royalties paid per play.