What you're seeing
The grid has d rows (one per hash function) and w columns. To add an item, each hash sends it to one column in its row, and that single cell is incremented — so every item touches exactly d cells (the blue outline). Different items can land in the same cell (a collision), which is why a cell's count can exceed the true count of any one item. To query an item, look at its d cells (white outline) and take the minimum (green). Because collisions only ever add, every one of those cells is an over-estimate — and the smallest of them is the closest to the truth.
The rule
init: count[d][w] = 0; pick d independent hashes h_1..h_d add(x): for r in 1..d: count[r][ h_r(x) ] += 1 query(x): return min over r of count[r][ h_r(x) ]
Updates are O(d) and the whole structure is d·w counters — fixed, no matter how many distinct items the stream contains.
The guarantee
Two parts. First a hard, one-sided invariant: the estimate is never less than the true count. Each occurrence of x increments every one of its d cells, and other items can only push those cells higher — so each cell ≥ true count of x, and therefore so is their minimum. There are no false negatives, ever. Second, a probabilistic bound on the overcount: with width w = ⌈e/ε⌉ and depth d = ⌈ln(1/δ)⌉, the estimate exceeds the truth by more than εn (where n is the total stream length) with probability at most δ. The intuition: in one row the expected collision mass in x's cell is n/w, so by Markov the overcount tops εn with probability ≤ 1/(εw) = 1/e; taking the min across d independent rows fails only if all of them are unlucky — probability (1/e)^d = δ. More columns shrink the error; more rows shrink the failure probability. This entry's test checks the invariant on every query and the bound statistically across hundreds of seeded streams.
The cost
An exact frequency table grows with the number of distinct items — unbounded for a stream of URLs, IPs, or search terms. The sketch's footprint is fixed at d·w counters regardless. The trade is the overcount, which hurts rare items most (their true count is dwarfed by collision noise) and heavy hitters least — which is exactly why Count–Min is the standard tool for the heavy-hitters problem. Widen the grid and watch the tracked item's overcount fall toward zero.
In the wild
Count–Min (Cormode & Muthukrishnan, 2005) is a workhorse of large-scale data systems. It powers approximate GROUP BY … COUNT and top-k queries in stream processors and databases; network routers use it to spot heavy-flow IPs without per-flow tables; it backs frequency features in NLP and recommendation pipelines (Spark, Redis modules, and many telemetry systems ship it). Its relatives — Count-Sketch (unbiased, signed), and the Space-Saving / Misra–Gries counters — make different trade-offs, but Count–Min's "min of a few hashed counters" is the one most people reach for. It is, in spirit, a Bloom filter that counts.
Try this
Shrink Width to its minimum and watch collisions inflate the tracked item's estimate above its true count — the overcount made visible. Now raise Depth: each extra row is another chance for an uncollided cell, and the green minimum drops back toward the truth. You're trading memory for accuracy in real time.
References
- Cormode, G. & Muthukrishnan, S. "An improved data stream summary: the count-min sketch and its applications." Journal of Algorithms 55(1):58–75, 2005. The original.
- Cormode, G. & Muthukrishnan, S. "Approximating Data with the Count-Min Sketch." IEEE Software 29(1), 2012 — a practitioner-oriented overview.
- Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), Lecture 5 (Heavy Hitters). course materials.
- Charikar, Chen & Farach-Colton. "Finding frequent items in data streams." ICALP, 2002 — the related Count-Sketch.