What Is a Count-Min Sketch?

A Count-Min Sketch is a probabilistic data structure that estimates how many times an item has appeared in a stream, using a fixed, small amount of memory regardless of how many distinct items pass through it. It never undercounts — the estimate it returns is always greater than or equal to the true count — but it can overcount when unrelated items collide in its internal structure.

Why not just use a hash table

A hash table (see what a hash table is) can track exact counts for every distinct key, but its memory grows with the number of distinct keys. For a high-volume stream — network packets by source IP, words in a massive corpus, product views by SKU — the set of distinct keys can be enormous, and holding an exact counter per key may not fit in memory at all. A Count-Min Sketch fixes the memory budget up front and accepts approximate answers in exchange.

The structure

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. All counters start at zero.

To add an item:

For each row i, hash the item with that row’s hash function to get a column index, and increment the counter at (row i, that column) by one. One item touches exactly d counters, one per row.

To estimate an item’s count:

For each row i, hash the item the same way and read the counter at that position. The estimate is the minimum of those d values — hence “count-min.”

Why the minimum, and why it never undercounts

Every increment for an item always lands in the same d cells (the hashes are deterministic), so each of those cells’ counts is at least as large as the item’s true count — other items may also hash into the same cell and add to it, but nothing ever removes from it. That means every one of the d readings is greater than or equal to the truth, so their minimum is too: the estimate is always an upper bound on the real count.

Collisions are the only source of error. If a heavy item collides in every row with other items that also hash to those same columns, its estimate is inflated. Using multiple independent hash functions and taking the minimum sharply reduces the odds of that happening in every row simultaneously — a collision inflating a count in one row is unlikely to be echoed in all d rows for the same item.

Tuning width and depth

The two dimensions trade memory for accuracy in predictable ways:

• Width (w) controls how much any single collision can distort a count. More columns means fewer collisions per row, tightening the error bound.
• Depth (d) controls the probability that an item’s estimate is inflated by collisions in every row. More rows make that increasingly unlikely.

Both parameters are chosen independently of how many distinct items you expect to see — that’s the entire point of the structure. A sketch sized for a given error tolerance and confidence level uses the same fixed memory whether the stream contains a thousand distinct keys or a billion.

Count-Min Sketch vs Bloom filter

Both structures trade a controlled error rate for constant memory, and both use multiple hash functions over a fixed-size array. But they answer different questions. See what a Bloom filter is for the full picture — the short comparison:

	Bloom filter	Count-Min Sketch
Answers	”Have I seen this item?"	"How many times have I seen this item?”
Storage	Bit array	Array of integer counters
Error direction	False positives possible; never false negatives	Overcounts possible; never undercounts
Typical use	Set membership, deduplication	Frequency estimation, heavy-hitter detection

A Bloom filter is effectively a Count-Min Sketch’s simpler cousin — swap counters for single bits and you lose the ability to count, but you gain membership testing in less space.

Where it’s used

Count-Min Sketches show up wherever a system needs approximate frequency counts over a stream too large to track exactly: finding the most-requested keys in a cache to decide what to evict, estimating query frequency in a database’s optimizer statistics, tracking trending items in a recommendation pipeline, or spotting the heaviest talkers in network traffic for anomaly detection. In every case, the workload cares more about relative ranking or a “good enough” estimate than about a perfectly exact count, and the fixed memory budget matters more than perfect accuracy — see what Big O notation is for how that space-versus-accuracy tradeoff gets expressed formally.

The collision behavior it relies on is the same idea covered in how hash collisions get resolved in ordinary hash tables — a Count-Min Sketch just treats every collision as data to combine (via addition) rather than a conflict to resolve.

The takeaway

A Count-Min Sketch is a grid of counters updated through several independent hash functions, and it estimates an item’s count as the minimum value across the row it hashes into. That construction guarantees the estimate never falls below the true count, only above it, and lets you bound the error with two tunable parameters — width and depth — independent of how many distinct items the stream actually contains. It’s the right tool whenever exact frequency counts don’t fit in memory but an approximate, always-safe-direction estimate does the job.