Cormode & Muthukrishnan's Count-Min Sketch (2003) estimates the frequency of any item in a stream using only d×w counters — sub-linear memory, constant-time update and query. Each of the d rows uses an independent hash to pick a column; a query takes the minimum across the row estimates. The estimate is never below the true count; the additive over-estimate is bounded by ε N with probability 1−δ where w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉.
ε = e/w ≈ — · confidence 1−δ = 1−e−d ≈ —.
Memory: — counters (32-bit each).
d row estimates. The outlined cell is their minimum — the sketch's answer. If the true count is known, the additive gap is the collision overhead from other items hashing into the same bucket.
Sorted by exact count. Green = sketch matched ground truth. Yellow = over-estimate (Count-Min is one-sided; it never under-counts). The gap should shrink as w grows, and it can only reach zero if no other item happens to collide in every row.
Graham Cormode and S. Muthukrishnan introduced Count-Min in An Improved Data Stream Summary: The Count-Min Sketch and its Applications (LATIN 2004). The insight is stark: instead of a single hash table that mixes counts, keep d independent hash tables and take the minimum at query time — because every collision only pushes counts up, the smallest row estimate is also the tightest upper bound. Compared to its cousin the Count Sketch (Charikar, Chen, Farach-Colton 2002), Count-Min uses non-negative counters and gives a one-sided additive guarantee |f̂ − f| ≤ εN. It underlies:
CMS.* family and Apache Spark's DataFrameStatFunctions.countMinSketch
The sketch does not tell you what the item was — only how many times it was seen — and it only bounds error for the highest-frequency items well (heavy hitters). For rare items, the additive εN can dominate the true count, so it's usually paired with a conservative-update rule or a Count-Min-Log variant when tracking the long tail matters.