Count-Min Sketch

From "How Many?" to "How Often?"

HyperLogLog answered "how many distinct things have I seen?" This lesson answers the next question, and it's one of the most useful in all of streaming: "how often does each thing occur?" How many times did each IP hit us this minute? How popular is each search term? Which product got the most views, which API endpoint the most calls? These are frequency questions, and the items you care about most are the heavy hitters — the top talkers, the trending queries, the hottest keys.

The exact way is a hash map: {item → count}, increment on each event. It's correct, and for a small number of distinct items it's the right tool. But the map grows with the number of distinct keys — count the hits per source IP across the internet and you're holding hundreds of millions of counters; do it per (IP, port, endpoint) and it explodes. When the keys don't fit, you need a structure whose size is fixed no matter how many distinct things stream through.

The Count-Min sketch (Cormode and Muthukrishnan, 2005) is that structure. It estimates the frequency of every key using a small, fixed grid of counters — a few kilobytes — regardless of how many distinct items or how many billions of events flow through it. Like every sketch in this section it accepts a little error to buy enormous space, but its error has a beautiful shape: it never undercounts, and it's sharpest exactly on the heavy hitters you actually care about.

How a Count-Min sketch estimates how often each item appears in a stream, using a small grid of counters. The structure is a grid of d rows and w columns of integer counters, all starting at zero, with one hash function per row. To record that an item occurred, each row hashes the item to one of its columns and adds to that single counter. The picture shows an item flowing through the d hashes into d cells, one per row, each being incremented. To read back the item's count, you look at those same d cells and take the minimum of them. The minimum is chosen because collisions from other items can only ever add to a counter, so every one of the d cells is an overestimate — and the smallest of them is the tightest. The headline, drawn as a badge: this gives the frequency of every key in a fixed grid of a few kilobytes, and it never underestimates. The grid's size never grows with the number of distinct items or the number of events.

A Grid of Counters, and the Min Trick

Here's the whole structure: a grid of counters, d rows by w columns, every cell starting at zero. Each row has its own hash function that maps any item to one of its w columns. Two operations:

To record an occurrence of x (add c to its count): for each of the d rows, hash x to a column and increment that one counter by c. One item touches exactly d cells, one per row.
To read x's count: hash x the same d ways to find its d cells, and return the minimum of them.

That minimum is the whole trick, and the reason the structure is called Count-Min. Think about what lives in one of x's counters. It holds x's true count — plus whatever other items happened to hash to that same cell in that row. Those collisions only ever add; nothing is ever subtracted. So every one of x's d counters is an overestimate of its true count. The one that got the fewest collisions is the closest to the truth — and since you can't know which that is, you take the minimum, the tightest overestimate available.

Notice the family resemblance to a Bloom filter: both hash an item to several cells across independent rows. A Bloom filter's cells are bits and it ANDs them; a Count-Min sketch's cells are counters and it takes their min. A Count-Min sketch is, more or less, a counting Bloom filter with a minimum and a formal error bound. Play with it below — add items with counts, then query them. Query a heavy hitter and watch the estimate land almost exactly on the truth; query a rare item and watch a collision inflate one of its cells while the min quietly steps around it.

A live Count-Min sketch — four rows of counters. Add an item with a count and watch each row hash it to one cell and bump it. Then query an item: its four cells light up, and the estimate is the minimum of them. Query a heavy hitter and it comes back nearly exact; query a rare item — or one you never added — and watch a collision inflate a cell while the min still refuses to go below the truth. Drag the width dial and watch the error bound εN shrink as the grid gets wider. The whole guarantee, in your hands: never too low, and tightest exactly where it matters.

Wrong in Only One Direction — Again

The Count-Min sketch has the same kind of one-sided honesty that made the Bloom filter safe, and it's worth stating exactly.

It never underestimates. Every occurrence of x incremented all d of its counters, and nothing is ever removed, so each of those counters is at least x's true count. The minimum of d values that are each ≥ the truth is itself ≥ the truth. There is no sequence of events that can make a Count-Min sketch report a count lower than reality. (This is why the counts must be non-negative — pure additions. If you also allowed decrements, the min trick breaks, and you'd need a different, two-sided variant.)

It can overestimate, and the reason is collisions. When some other item hashes to the same cell as x in one of the rows, that item's count gets piled onto x's counter, inflating it. But here's why the min over d rows is so powerful: for the estimate to be badly inflated, x would have to collide with heavy items in every single row at once — and with independent hash functions, that's exponentially unlikely. It's very probable that at least one of x's d rows gives it a relatively clean cell, and the minimum seizes on that one. More rows (larger d) means the bad case — inflated in all rows — gets rarer, which is exactly how the sketch turns "probably close" into "almost certainly close."

So the guarantee mirrors the Bloom filter's, flipped onto counts. A Bloom filter is never wrong in the dangerous direction — it never calls an absent item present-and-missing. A Count-Min sketch is never wrong in the low direction — it never tells you something happened fewer times than it really did. Both errors point the same, safe way.

Why a Count-Min sketch can only ever be wrong in one direction — it never underestimates. Because every occurrence of an item increments its counters and nothing is ever subtracted, each of an item's d counters holds at least its true count. So the minimum of those counters is always greater than or equal to the truth: the estimate is never too low. The overestimate comes from collisions: a different item that happens to hash to the same cell in one row adds its own count to that counter, inflating it. The picture shows exactly this — one of a queried item's cells is inflated by a colliding item, but because the collision is unlikely to strike the same item in all d rows, at least one other cell stays clean, and the minimum dodges the inflated one. That is the whole point of taking the min across several rows. It echoes the Bloom filter's one-sided guarantee, flipped: a Bloom filter is never wrong by saying an absent item is present in the dangerous direction, and a Count-Min sketch is never wrong by reporting a count that is too low.

The Error Is Bounded: εN

How much can it overestimate? This is where the sketch stops being a nice heuristic and becomes a structure with a proof. Cormode and Muthukrishnan showed that if you size the two dimensions as w = ⌈e/ε⌉ (width, where e ≈ 2.718) and d = ⌈ln(1/δ)⌉ (depth), then for any item the estimate f̂ satisfies:

f̂ ≥ f (never under), and with probability at least 1 − δ, f̂ ≤ f + ε·N

where N is the total number of events (the sum of all counts). Two things are worth reading carefully. First, the error is additive, not multiplicative: the overestimate is bounded by a fixed εN, the same budget for every item, regardless of that item's own count. Second, it's probabilistic: the bound holds with high probability, and the depth d is the confidence dial — each extra row drives the failure probability δ down by another factor of e, so a handful of rows (d = 5 → δ ≈ 0.7%) makes a blowout vanishingly rare. The width w is the accuracy dial: wider grid → smaller ε → smaller overestimate.

And the numbers behave. On a real stream of about 1.4 million events, a five-row sketch's worst overestimate stayed comfortably under εN at every width — about 11,625 at width 256, 627 at width 2,720, and just 140 at width 8,000 — each well inside its promised bound. Because εN doesn't depend on the number of distinct items, a Count-Min sketch holds its accuracy while an exact map would blow its memory budget: the grid is a fixed d × w counters (a 2,720 × 5 sketch is about 54 KB), the same whether a thousand or a hundred million distinct keys stream through.

Heavy Hitters: the Point of It All

Now the payoff, and it's a beautiful piece of luck built into the math. Real streams are skewed — a few items are wildly frequent and a long tail is rare (Zipf's law: the most common query, the busiest IP, the viral post). The overestimate a Count-Min sketch adds is roughly a fixed amount — that εN budget — for every item. For a heavy hitter whose true count is in the millions, a fixed overestimate of a few thousand is a rounding error; its estimate comes back almost exactly right. In a measured run the heaviest item's true count of 60,000 was reported as 60,055 — an overestimate of just 0.09%. The rare items in the tail get the same absolute noise, which is large relative to their tiny counts — but those are precisely the items you rarely care about. The sketch is sharpest exactly where you want it: on the heavy hitters.

One caveat worth naming: a Count-Min sketch tells you the count of an item you ask about — it doesn't, by itself, tell you which items are the heavy hitters, because it stores no keys. To actually find the top-k, you pair it with a small heap of candidate keys: as events stream in, you keep the sketch updated and maintain a heap of the highest-estimated keys seen so far. And if you need even tighter counts, there's the conservative update optimization: on each increment, only raise the counters that are currently at the minimum. On the same stream that cut total overestimation by about 46% — though it gives up mergeability (which we're about to rely on), so it's a trade.

Why the Count-Min sketch is so good at exactly the job you usually want: finding heavy hitters. In a typical stream a few items are enormously frequent and a long tail of items are rare. The overestimate added by collisions is roughly the same small amount for every item — bounded by epsilon times N, the total number of events. For a heavy hitter whose true count is in the millions, that fixed overestimate is negligible, so its estimate is almost exact. The chart shows a measured run: the heaviest item's true count of 60,000 came back as 60,055, an overestimate of just 0.09 percent, while rare items in the tail are noisier. And the error is tunable: the additive bound epsilon-N shrinks as the grid gets wider — with a five-row sketch the measured maximum overestimate was about 11,625 at width 256, 627 at width 2,720, and 140 at width 8,000. Wider grid, smaller error, and the heavy hitters — the top talkers, the trending queries, the hottest keys — are exactly where the sketch is sharpest.

Where It Runs, and the Family Portrait

Count-Min sketches run wherever per-key frequencies matter over data too big or too fast to store exactly. Redis ships one in the RedisBloom module: CMS.INITBYDIM (or CMS.INITBYPROB to size by error and confidence), CMS.INCRBY to add counts, CMS.QUERY to estimate, and CMS.MERGE to combine. A real session shows the behavior cleanly — after CMS.INCRBY traffic 8.8.8.8 5000, CMS.QUERY traffic 8.8.8.8 returns exactly 5000 (no collision in a lightly-loaded sketch), and — the distributed superpower — because two sketches with the same dimensions merge by adding their grids cell-by-cell, a CMS.MERGE of a Monday sketch (4000) and a Tuesday sketch (6000) answers the two-day count as 10000 with no re-scan. Apache Spark exposes a CountMinSketch, Flink and Druid use them for streaming aggregates, and network gear uses them for line-rate heavy-hitter and DDoS detection.

Step back, and the whole sketch family snaps into one picture — because all three of §8's probabilistic sketches are the same idea with a single part swapped. Each hashes an item into a small array of cells and keeps a tiny summary; what differs is the cell and the combine:

Bloom filter — cells are bits; add sets them to 1, query ANDs them → membership (is x in the set?).
HyperLogLog — cells are rank registers; add takes the max, query harmonic-means them → cardinality (how many distinct?).
Count-Min — cells are counters; add increments, query takes the min → frequency (how often?).

AND, MAX, and MIN over a grid of hashed cells. Once you see that, you don't have three tricks to memorize — you have one instinct pointed at three questions. Reach for Count-Min when you need per-key frequencies at scale and a small, one-sided overestimate is fine — and reach for an exact map when you need precise counts or the keys themselves.

The family portrait of the three probabilistic sketches, showing they are all the same idea with one part swapped. Each hashes an item into a small array of cells and keeps a tiny summary; the difference is what a cell holds and how you combine cells. The Bloom filter's cells are bits: to add you set bits to 1, and to query you check that all the item's bits are 1 — it answers membership, is this item in the set. HyperLogLog's cells are rank registers: to add you take the maximum of the register and the item's leading-zero rank, and to query you combine the registers with a harmonic mean — it answers cardinality, how many distinct items. The Count-Min sketch's cells are counters: to add you increment, and to query you take the minimum — it answers frequency, how often each item occurs. Set-or-AND, max, and min over a grid of hashed cells: the same instinct, three different questions.

The Sketches, Assembled

That's the frequency sketch, and with it the counting half of §8 is nearly complete. Trace the arc: membership (is x in the set?) — Bloom and Cuckoo filters; cardinality (how many distinct?) — HyperLogLog; frequency (how often is each?) — the Count-Min sketch. Four of the five sketches, each the same bargain — hash it, keep a tiny summary, accept a bounded and one-directional error — pointed at a different question, and each one fits a firehose of data into a few kilobytes.

One question remains, and it's a different flavor: not about a single set, but about two. "How similar are these two sets?" — how much do two users' watch histories overlap, are these two documents near-duplicates, is this the same fingerprint as that one — is answered by MinHash, and it's the last of the sketches. It reuses the same instinct you've now built five times, aimed at similarity instead of counting.