Count-Min Sketch
When to Use Count-Min Sketch
In Practice
How Count-Min Sketch Comes Up in Interviews
Scenario
Cloudflare needs to find which source IPs are flooding the edge right now, on a stream of millions of packets per second, without keeping an exact counter per IP. Which sketch fits?
Count-Min Sketch estimates per-key frequencies in sublinear memory and never underestimates, ideal for heavy-hitter / top-K detection on unbounded streams. HyperLogLog (HLL) counts distincts, not frequencies.
Count-Min Sketch is a 2D array of counters (d rows × w columns), with d hash functions mapping each key to one counter per row; you increment all d on insert and take the minimum on query. The 'min' is the key trick: collisions only inflate counts, never deflate, so the sketch never underestimates. Cloudflare uses CMS variants for real-time heavy-hitter detection on packet streams; Twitter's old heavy-hitter pipeline did the same. The space is independent of the universe size, a few MB handles billions of distinct keys with ~0.1% error, but it can't enumerate the heavy hitters by itself, so you usually pair it with a 'top-K' min-heap that gets updated when a sketched count crosses a threshold.