How often has each item appeared in a stream of billions? Storing an exact counter per distinct item can blow your memory. The Count–Min Sketch answers approximately in a fixed grid: d rows of w counters. Each item bumps one counter per row (chosen by d hashes), and you estimate its count by taking the minimum across its d cells. Collisions can only inflate a cell, so the min can over-count — but it can never under-count. Feed the stream and query.
d rows × w counters. Fixed size, no matter how many distinct items.
d hashes
One hash per row maps an item to one counter in that row.
update
On each event, increment the item’s one counter in every row.
estimate
The minimum of the item’s d counters — collisions inflate, min limits the damage.
cms.js — d rows, w counters, take the min
Ready
A grid of d=3 rows × w=8 counters, all zero. Each event bumps one counter per row (chosen by that row’s hash). Add event to feed the stream; Query to estimate a count.
0
events
–
true count
–
estimate (min)
How it works
The estimate is a minimum, and that choice is the whole design. Every one of an item’s d counters holds its true count plus whatever other items happened to hash to the same cell — so every counter is an over-estimate. Taking the smallest of the d counters keeps the one least polluted by collisions. It’s still ≥ the true count (over-count possible), but it can never drop below it (no under-count), because the item’s own increments are in every one of those cells.
1
Update: bump one cell per row
On each event for item x, use row 0’s hash to pick a column and increment it; same for row 1, row 2. x contributes to exactly d cells.
2
Cells collect collisions
Other items may hash to the same cells and bump them too. So each of x’s counters holds x’s count plus some noise — always an over-estimate, never an under-estimate.
3
Estimate: take the minimum
Read x’s d counters and return the smallest. That’s the counter least inflated by other items — the tightest available upper bound on x’s true count.
✓
Tune the error
More columns w shrinks collisions (tighter estimates); more rows d shrinks the chance all d cells are unlucky. Together they bound the over-count with high probability — in fixed space, independent of stream length.
Update / query
O(d)
Space
d × w counters
Under-count
Never
Over-count
Bounded
The code
# d rows, w counters each. Fixed space, one hash per row.class CountMinSketch:
def __init__(self, d, w):
self.w = w
self.grid = [[0]*w for _ in range(d)]
def add(self, x, c=1):
for r, row in enumerate(self.grid):
row[hash_r(x, r) % self.w] += c # bump one cell per rowdef estimate(self, x):
return min(row[hash_r(x, r) % self.w] # the least-polluted cellfor r, row in enumerate(self.grid))
Quick check
1. Why does the Count–Min Sketch take the minimum across rows?
Each of the item’s d counters holds its true count plus collision noise, so each is ≥ the truth. The minimum picks the counter least polluted by other items — still an over-estimate, but the tightest one available.
2. Can a Count–Min Sketch ever return LESS than the true count?
Never. Each event increments all d of the item’s cells, so every one of them is at least the true count. Collisions can only add extra, so the minimum is ≥ truth — over-counts possible, under-counts impossible.
3. What grows the space of a Count–Min Sketch as the stream gets longer?
The grid is a fixed d×w chosen up front. It uses the same memory whether the stream has a thousand or a trillion events — that fixed footprint is the whole point.
FAQ
What is a Count–Min Sketch?
A probabilistic structure that estimates item frequencies in a stream using a fixed grid of d rows × w counters and d hashes. Each event bumps one counter per row; the estimate is the minimum of an item’s d counters. It over-counts but never under-counts.
A Bloom filter answers membership (is x present?) with bits; a Count–Min Sketch answers frequency (how often is x?) with counters. Both use several hashes and have one-sided error — a Bloom filter never false-negatives, a sketch never under-counts.
Where is the Count–Min Sketch used?
Streaming analytics and network monitoring: finding heavy hitters, tracking trending topics or IPs, anomaly detection, and query optimizers estimating value frequencies — anywhere you need per-item counts over a huge stream in bounded memory.
How do you choose d and w?
They set the error bound: columns w control the additive error (≈ e/w × total count), rows d control the confidence it stays within bound (failure prob ≈ e⁻ᵈ). Pick w for tightness, d for confidence — trading memory for accuracy.