Start here: the problem it solves#
TL;DRthe 30-second version
- A Count-Min Sketch estimates how often each item appears in a stream using a fixed, tiny amount of memory — instead of the one-counter-per-item memory an exact hash map needs.
- It keeps a grid of counters, d rows by w columns, and one hash function per row. To add an item, it increments one cell in every row. To estimate an item's count, it reads those same d cells and returns the smallest.
- Taking the minimum works because collisions only ever push a counter up, never down. Every cell is therefore at least the true count, so the smallest is the tightest honest bound — an overestimate that can never fall below the truth.
- The error is one-sided and bounded: with probability at least 1 − e^−d, the overcount is at most (e/w)·N, where N is the total of all increments. You widen the grid to tighten the bound and deepen it to raise the confidence.
- Real systems: Redis CMS.INCRBY / CMS.QUERY, Apache Spark's countMinSketch, network flow measurement, and heavy-hitter detection when paired with a small top-k heap.
Imagine a stream of events where you want the frequency of each item: how many times each search term was queried today, how many packets each source IP sent through a router, how many times each product was viewed. The exact way is a hash map from item to a running count. You look up the item, add one, and the map holds the truth.
That map works until the number of distinct items gets large. Suppose a router sees one billion distinct source-and-destination flows in an hour. An exact counter for each is a key plus an integer, say 24 bytes, so the map is about 24 GB. A switch forwarding at line rate has a few megabytes of fast memory, not gigabytes, and it has nanoseconds per packet. You simply cannot keep a counter per flow.
Here is the observation that saves us. You rarely need every count to be exact. For finding the busiest flows, the trending search terms, or the products worth caching, an answer that is close and occasionally a little high is fine. If you can tolerate a small, one-sided error, you can replace that 24 GB map with a few kilobytes that never grow.
The idea that almost works: one row of counters#
Start with the simplest shrink. Instead of a counter per item, keep one array of w counters. Hash the item to a column, and increment that one counter. To read a count, hash the item again and return that counter's value. This is tiny and fast, and for an item nobody else collides with, it is exact.
The problem is collisions. With w = 1,000 counters and a million distinct items, roughly a thousand items share each counter. When you read the counter for a rare word like 'aardvark', you get the sum of every item that hashed to the same column — which might include a common word like 'the'. The rare item now looks enormous, and you have no way to tell how much of that counter belongs to it.
Notice the direction of the error, though. A shared counter is always at least the true count of any item that maps to it, because every one of those items only ever added to it. The single-row estimate is never too low. It is only ever too high, and only because of collisions. That one-sidedness is the crack we are going to pry open.
The mechanism: d rows, and take the minimum#
A Count-Min Sketch is a grid of counters with d rows and w columns, all starting at zero. Each row has its own independent hash function, so the same item lands in a different column in each row. The two operations are short.
- Add an item: for each of the d rows, hash the item to a column in that row and increment that one counter. One item touches exactly d cells, one per row.
- Estimate an item's count: hash the item the same way to find its one cell in each row, read all d of those cells, and return the smallest value among them.
The whole design rests on why the minimum is the right answer. Every cell an item maps to was incremented on every add of that item, so each of those d cells is at least the item's true count. Collisions can only add more on top. So each cell is the true count plus whatever other items happened to collide there. The cell with the least collision damage is the smallest one, and it is still an upper bound. Taking the minimum picks the tightest honest estimate available.
d = 3 rows, w = 8 columns · the marked cells are where item 'the' lands
For an estimate to be badly wrong, the item would have to collide with heavy items in every single row at once. Because each row uses an independent hash, the chance of that drops off fast as you add rows. This is the same trick a Bloom filter uses with its k hash functions: many independent chances make an unlucky pattern rare. Here the payoff is not membership but a frequency you can put a bound on.
Go deeperThe error bound, exactly
Let N be the total of every increment, the size of the stream. Set the width to w = ⌈e/ε⌉ and the depth to d = ⌈ln(1/δ)⌉, where e is Euler's number. Then for any item, the estimate is at least its true count with certainty, and with probability at least 1 − δ the overcount is at most ε·N.
The two dials are independent. Width w controls how tight the bound is: a single row overcounts an item by about N/w on average, because the N other increments spread across w columns and only a fraction 1/w of them land on the item's column. The published bound ε·N is a factor of e larger than that average (ε = e/w); that extra e is the slack in a Markov bound — it makes ε·N a ceiling a row stays under with high probability, not the typical overcount. Depth d controls how confident you are: each extra row is another independent chance for one row to be nearly collision-free, and the minimum only needs one good row.
A concrete size: ε = 0.001 and δ = 0.01 give w = ⌈e/0.001⌉ = 2,719 columns and d = ⌈ln(100)⌉ = 5 rows, about 13,595 counters. At four bytes each that is roughly 54 KB — fixed, whether the stream has a thousand distinct items or a billion.
A worked example#
Take a small sketch with d = 3 rows and w = 8 columns, all counters at zero, and feed it a short word stream. Say 'the' is added three times, and a second word, 'cat', is added a few times as well. Suppose 'cat' happens to hash to the same column as 'the' in row 2, but to different columns in rows 1 and 3.
- Add 'the' three times. Its three cells — one per row — each climb to 3. With nothing else touching them yet, all three read 3.
- Add 'cat' three times. Two of its cells are its own, but in row 2 it shares 'the's cell, so that cell now reads 3 + 3 = 6.
- Estimate 'the'. Read its three cells: row 1 reads 3, row 2 reads 6, row 3 reads 3. The minimum is 3, which is exactly the true count. Row 2's inflated 6 is thrown away.
That is the entire point of the structure in one run. A collision made one row overcount 'the' to double its real value, but because a different row stayed clean, the minimum still returned the honest 3. Add a fourth row and the odds of every row being polluted at once fall further. Widen the columns and collisions get rarer to begin with.
PredictYou estimate a word that was never added to the sketch. What can the answer be, and why can it never be negative?
Hint: Every counter starts at zero and only ever goes up.
The estimate is some value at or above 0 — it is the minimum of d counters, each of which is the sum of the items that collided into it. If no other item hashed to all d of this word's cells, every cell is still 0 and the estimate is 0, correctly. If other items did collide across all d cells, the estimate is a positive overcount. It can never read below the true count of 0, because counters never decrease. This is why the sketch is said to have no false 'undercounts': the error is entirely one-sided.
Finding the heavy hitters
The most common use is not to query one item but to find the busiest ones: the top search terms, the noisiest IPs, the hottest keys. The sketch pairs naturally with a small heap of candidates. As each item streams in, you increment its cells, then read back its estimate, and if that estimate is large enough you keep the item in a fixed-size top-k heap.
This works well precisely because the sketch's error is proportional to N, the stream size, not to the item's own count. A heavy hitter has a count that is a large fraction of N, so an overcount of ε·N barely moves its ranking. The structure is accurate exactly where you care — on the frequent items — and sloppy only on the rare ones, whose exact counts you were not going to trust anyway.
Memory and speed#
The headline property is that memory is O(d·w) and completely independent of the number of distinct items. Adding an item is O(d): d hashes, d increments. Estimating a count is also O(d): d hashes, d reads, and a minimum over d values. With d around 5, both operations are a handful of memory touches, which is why the structure keeps up with line-rate streams.
- Memory is d·w counters, fixed at creation. You size it from your target error, not from the data: w ≈ e/ε columns and d ≈ ln(1/δ) rows. A common ~54 KB sketch (w ≈ 2,719, d = 5) tracks any number of items within 0.1% of N with 99% confidence.
- Add and estimate are both O(d), independent of how many items you have counted or how large the counts are. There is no resize, no rehash, and no scan.
- The estimate is never below the true count. With probability at least 1 − e^−d the overcount is at most (e/w)·N. Widen w to tighten the bound; deepen d to raise the confidence.
- Two sketches with the same dimensions and hashes merge by adding them cell by cell. The merged sketch equals the one you would get by feeding both streams into a single sketch, which makes distributed counting straightforward.
Variants and a sharp edge
- Conservative update (Estan–Varghese): when adding an item, instead of incrementing all d cells, only raise the cells that equal the current minimum. This keeps every cell a valid upper bound but slows the growth of over-counted cells, cutting the error in practice — at the cost that the sketch can no longer be decremented or merged as simply.
- Count-Mean-Min: subtract an estimate of the average collision noise from each cell before taking the minimum. This reduces the bias for low-frequency items, trading the strict 'never undercount' guarantee for a smaller typical error.
- Count-Min with signed updates: if you allow decrements (negative counts, as in a turnstile stream), the minimum is no longer a valid bound — a decrement elsewhere can pull a shared cell below an item's true count. For signed streams you take the median of the d cells instead, which costs more rows for the same confidence.
Strengths, limits, and when to reach for it
A Count-Min Sketch makes one clear bargain: give up exact counts to gain memory that does not grow with the data. Whether that is a good deal depends on what you do with the numbers.
- Fixed, tiny memory — the grid is d·w counters set at creation and never resizes, so it fits in the fast memory of a switch or a single Redis key while an exact map would need gigabytes. This is the whole reason to use it.
- One-sided, bounded error — the estimate is never below the true count, and the overcount is at most ε·N with confidence 1 − e^−d. You know the direction and the size of the error up front, which is rare and valuable.
- Accurate where it matters — the error is proportional to N, not to the item's own count, so heavy hitters are reported faithfully and only the rare items are loose. For trending, hot-key, and abuse problems that is exactly the right bias.
- Mergeable — sketches with the same dimensions add cell by cell, so you can shard the stream across machines and roll the counts back up without shipping the raw events.
- The limits — it cannot list the items, cannot give an exact count, is unreliable for low-frequency items, and its never-undercount guarantee holds only for non-negative streams. If you need any of those, reach for an exact map (small data), a top-k heap alongside the sketch (heavy hitters), or the median-based variant (signed streams).
Count-Min vs the neighbours
| Exact hash map | Bloom filter | HyperLogLog | Count-Min Sketch | |
|---|---|---|---|---|
| Answers | count per item | is it present? | how many distinct? | count per item |
| Memory | O(distinct items) | O(m) bits, fixed | O(m) registers, fixed | O(d·w), fixed |
| Error | none | false positives only | ~1.04/√m relative | overcount ≤ ε·N, one-sided |
| Can undercount? | no | no false negatives | two-sided | no (non-negative streams) |
| Mergeable? | yes, expensive | yes (bitwise OR) | yes (element-wise max) | yes (cell-wise add) |
The three sketches answer different questions. A Bloom filter tells you whether an item was seen at all, but not how often. A HyperLogLog tells you how many distinct items there were, but not which or how often. A Count-Min Sketch tells you how often a given item was seen. They share the same bargain — a fixed, tiny footprint in exchange for a bounded error — and they are often used side by side in the same system.
Against the exact hash map, the sketch wins only when the distinct-item count is too large to store. For a few thousand items, keep the exact map; it is smaller and exact. The sketch earns its place when 'a counter per item' is the thing you cannot afford, which is precisely the web-scale and line-rate regime.
Where Count-Min Sketch runs in the wild
- Redis — the Count-Min Sketch data type (CMS.INITBYDIM / CMS.INCRBY / CMS.QUERY / CMS.MERGE) estimates item frequencies in sub-linear space; CMS.QUERY returns the minimum across the rows, exactly as described here.
- Apache Spark — DataFrame.stat.countMinSketch builds a sketch over a column so you can estimate value frequencies across a huge dataset without a full group-by, and merge sketches computed on different partitions.
- Network measurement — switches and routers keep per-flow packet and byte counts in a Count-Min Sketch in fast on-chip memory, where a counter per flow would never fit, to drive traffic engineering and detect heavy flows.
- Trending and abuse detection — search, ads, and social systems use the sketch (often with a top-k heap) to find trending queries, hot keys worth caching, and IPs or accounts sending abnormally many requests.
Common misconceptions & gotchas
Can the estimate ever be too low?
Not for a non-negative stream. Every one of an item's cells was incremented on every add of that item, so each cell is at least the true count, and the minimum of them is too. The error is entirely one-sided — the sketch overcounts or is exact, never undercounts. This breaks only if you allow decrements, where you should switch to the median-based variant.
Why the minimum and not the average of the rows?
Because every cell is an upper bound, and averaging upper bounds gives a looser upper bound. The cell with the fewest collisions is the smallest one, and it is still valid, so the minimum is the tightest honest estimate. The Count-Mean-Min variant does subtract estimated noise before taking the min, which helps low-frequency items but gives up the strict never-undercount guarantee.
Can I list the items or get the total distinct count from it?
No. The sketch stores only sums in a grid; it never stores the items, so you cannot enumerate them, and it does not track distinct cardinality. Query it with items you already have. To find the heavy hitters you pair it with a separate top-k heap of candidate items; to count distinct items you use a HyperLogLog instead.
How do I choose the width and depth?
Pick the largest overcount you can tolerate as a fraction ε of the stream size N, and the confidence 1 − δ you want that bound to hold with. Then set w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉. Width buys a tighter bound; depth buys confidence. Both are independent of how many items you end up counting.
QuizYou run one Count-Min Sketch per shard and merge them nightly by adding the grids cell by cell. An item that appeared 40 times on shard A and 60 on shard B reads what in the merged sketch?
- At least 100 — the merged cells hold at least the summed true counts, plus any collisions
- Exactly 50 — merging averages the two sketches
- At most 100 — merging can only lose counts
- Undefined — sketches from different shards cannot be merged
Show answer
At least 100 — the merged cells hold at least the summed true counts, plus any collisions — Cell-wise addition makes the merged grid identical to one built by feeding both shards' streams into a single sketch. The item's true count there is 40 + 60 = 100, so each of its cells is at least 100, and the minimum — the estimate — is at least 100, possibly a little more from collisions. Merging never undercounts. It requires both sketches to share the same dimensions and hash functions.
In an interview
Lead with the problem and the shape of the answer. Counting how often each item appears in a huge stream would need a counter per distinct item, which is gigabytes; a Count-Min Sketch replaces that with a fixed grid of counters, a few kilobytes, at the cost of a small overcount. Name where it runs: Redis CMS commands, Spark's countMinSketch, and per-flow counting in network switches.
Then explain the mechanism in two moves. First, hash each item to one column per row and increment those d cells. Second, to estimate, read the same d cells and take the minimum. Be ready to say why the minimum: collisions only ever add, so every cell is an upper bound, and the smallest is the tightest. Mention the guarantee — never below the true count, and with probability 1 − e^−d the overcount is at most (e/w)·N — and that width tightens the bound while depth raises the confidence.
If pushed, mention the heavy-hitter pairing with a top-k heap, that the error is proportional to N so it lands on the rare items and spares the frequent ones, and that sketches merge by adding grids for distributed counting. Then open the simulator: add an item a few times and watch its cells climb together, add a colliding item to inflate one row, and estimate to watch the minimum ignore the inflated row and return the honest count.
References & further reading
- Cormode & Muthukrishnan — An Improved Data Stream Summary: The Count-Min Sketch and its Applications (2005) — the original paper; defines the sketch, the minimum estimator, and the ε/δ error bound
- Cormode — Count-Min Sketch (reference site and survey) — the author's hub: intuition, variants (conservative update, count-mean-min), and applications
- Redis — Count-Min Sketch data type (CMS.INCRBY / CMS.QUERY / CMS.MERGE) — a production implementation; CMS.QUERY returns the minimum across the rows
- Apache Spark — DataFrameStatFunctions.countMinSketch — builds and merges Count-Min sketches over a DataFrame column
- Estan & Varghese — New Directions in Traffic Measurement and Accounting (2002) — the conservative-update idea and the network-measurement setting the sketch was built for
Ready to try it?
The simulator is a real, deterministic implementation — pick a scenario and step through it, scrubbing the timeline forward and backward through every change.