Ask a database or a network switch “how many times have I seen this?” at a volume of millions of events per second, and storing a running count for every distinct key becomes its own scaling problem — the moment the number of distinct keys stops fitting in memory, exact per-key counters stop being an option. Count-Min Sketch solves this the same way Bloom filters and HyperLogLog solve adjacent problems: trade a small, bounded, one-directional error for a fixed, sublinear amount of memory. Introduced by Graham Cormode and S. Muthu Muthukrishnan in a 2003/2005 paper, it now ships as a first-class probabilistic data type in Redis Stack and underlies frequency-estimation and heavy-hitter detection in streaming systems well beyond it.
At a Glance
| Attribute | Detail |
|---|---|
| What it is | A probabilistic structure that estimates how many times each distinct item has occurred in a stream |
| What it guarantees | Estimates are never below the true count; error is one-directional (over-counting only), bounded and tunable |
| Core structure | A w-column, d-row array of counters, each row paired with its own independent hash function |
| Error bound | Width w = ⌈e/ε⌉, depth d = ⌈ln(1/δ)⌉ gives additive error at most ε × (total count), with probability at least 1 − δ |
| Typical use cases | Heavy-hitter / top-K detection, per-item frequency estimation over high-volume streams, network traffic measurement |
| Origin | Graham Cormode & S. Muthu Muthukrishnan, “An Improved Data Stream Summary: The Count-Min Sketch and its Applications,” Journal of Algorithms, 2005 (first presented 2003) |
Short Verdict
Count-Min Sketch is the right tool when you need “roughly how many times has X happened” over a stream too large to hold one exact counter per distinct key, and you specifically care most about the high-frequency items — it is a poor fit for counting rare, long-tail items precisely, since its error is large relative to small true counts. Redis ships it as a production data type with O(1) updates and queries, and its own documentation is explicit that counts below a configurable error-based threshold should be treated as noise, not signal. In exchange for that limitation, the whole structure’s memory stays fixed regardless of how many distinct items flow through it, and separate sketches merge by simple cell-wise addition.
The Problem: Counting Everything in a High-Cardinality Stream
A hash map from item to count answers “how many times has this occurred?” exactly, but its memory grows linearly with the number of distinct items — tracking per-second request counts for every distinct client IP, every distinct product SKU sold, or every distinct URL requested at a CDN edge node means the map itself can dwarf the data you actually care about, which is usually just the handful of items occurring far more often than the rest. Cormode and Muthukrishnan’s 2005 paper frames this as a “data stream summary” problem: you see a long stream of items once, can’t afford to store it all, and need a compact structure that still answers frequency and “point” queries afterward with a provable error bound rather than a hopeful approximation.
How It Works: A Grid of Counters and d Independent Hashes
The structure is a two-dimensional array of counters with w columns and d rows, where each row has its own independent hash function mapping any item to one of the w columns.
- Update (increment): when item i arrives, for every row j compute column k = h_j(i), and increment that single cell by one. An item touches exactly d cells — one per row — regardless of how many distinct items exist.
- Query (estimate): to estimate the count of item i, compute the same d cells again and return the minimum value across all of them — the “min” in Count-Min.
Taking the minimum is what makes the structure’s error one-directional. Hash collisions can only ever make a cell’s count too high — never too low — because every other item that happens to hash into the same column in a given row only adds to that cell, never subtracts. So any individual cell for item i is at least as large as i’s true count, and the minimum across d independently-hashed rows is the tightest such overestimate the structure can produce. That is also why Count-Min Sketch never underestimates: the reported value is always ≥ the true count, and the only question is by how much.
Cormode and Muthukrishnan’s paper gives the sizing that controls how much: setting w = ⌈e/ε⌉ (e is Euler’s number, ≈2.718) and d = ⌈ln(1/δ)⌉ guarantees the estimate exceeds the true count by at most ε times the sum of all counts added so far (the total stream size), with probability at least 1 − δ. Concretely, more columns (larger w) tighten the error bound ε; more rows (larger d, more independent hash functions) tighten the failure probability δ. Both dials cost memory directly — the structure is exactly w × d counters — which is the same precision-for-space trade that runs through every probabilistic structure in this family.
A Minimal Implementation in Python
This mirrors the update/query mechanism directly — it is not a production implementation, which would use faster hashing and careful overflow handling for the counters.
import hashlib
class CountMinSketch:
def __init__(self, width=2000, depth=7):
self.width = width
self.depth = depth
self.table = [[0] * width for _ in range(depth)]
def _hash(self, item, row):
# one independent hash per row, salted by the row index
key = f"{row}:{item}".encode("utf-8")
digest = hashlib.sha256(key).digest()
return int.from_bytes(digest[:8], "big") % self.width
def add(self, item, count=1):
for row in range(self.depth):
col = self._hash(item, row)
self.table[row][col] += count
def estimate(self, item):
return min(
self.table[row][self._hash(item, row)]
for row in range(self.depth)
)
cms = CountMinSketch(width=2000, depth=7)
for _ in range(10_000):
cms.add("checkout_api")
for _ in range(12):
cms.add("rare_debug_endpoint")
print(cms.estimate("checkout_api")) # at least 10,000, close to it
print(cms.estimate("rare_debug_endpoint")) # a poor, noisy estimate — too few true occurrences
The key properties to notice: memory is fixed at width × depth counters no matter how many distinct items flow through, both add and estimate are O(depth) per call rather than scaling with the number of distinct items seen, and two sketches built with the same width and depth merge by simply summing their tables cell-by-cell — no need to touch either original stream.
Real-World Use: Redis’s Count-Min Sketch
Redis ships Count-Min Sketch as a first-class probabilistic data type with six commands documented on redis.io. CMS.INITBYDIM creates a sketch with explicit width and depth; CMS.INITBYPROB creates one from a target error rate and error probability instead, computing width as w = 2/error internally; CMS.INCRBY increments one or more items’ counts (by an amount that can be negative); CMS.QUERY returns the current estimate for one or more items; CMS.MERGE combines several sketches into one; and CMS.INFO reports a sketch’s width, depth, and total count. Redis’s own documentation is explicit about the trade-off’s practical shape: counts can only be over-estimated, never under-estimated, and it recommends computing a threshold (error rate × total count so far) below which returned counts should be treated as unreliable noise rather than a real signal — its own worked example shows that a uniform distribution of similarly-sized counts is a poor fit for the structure, while a skewed distribution with a smaller number of genuinely “heavy” items works well, which is exactly the shape of most real traffic and sales data.
That skewed-distribution fit is also why Count-Min Sketch’s best-known applications are heavy-hitter and top-K detection problems: identifying which handful of network flows, API keys, or URLs account for a disproportionate share of traffic, without keeping an exact counter for every long-tail item that only shows up once or twice. Cormode and Muthukrishnan’s original paper frames this class of problem — frequent items over a data stream — as a central motivating application, alongside point queries and range queries, and later work (cited on the structure’s reference pages) has applied the same sketch to tasks like NLP frequency estimation and detecting repeated password-guessing attempts without storing every attempt.
Count-Min Sketch vs. Bloom Filter vs. HyperLogLog
These three sit in the same family of fixed-memory probabilistic structures, but they answer three genuinely different questions, and picking the wrong one for your question is the most common mistake.
| Structure | Question it answers | Error direction | Supports deletion? |
|---|---|---|---|
| Bloom filter | “Have I seen this exact item before?” (membership) | False positives only, never false negatives | No (Counting Bloom Filter variant adds it) |
| HyperLogLog | “How many distinct items have I seen in total?” (cardinality) | Statistical error in either direction around the true count | Not applicable — no per-item concept |
| Count-Min Sketch | “How many times has this specific item occurred?” (frequency) | Over-estimates only, never under-estimates | No in the standard form; some variants allow controlled decrements |
Wikipedia’s own treatment notes that a Count-Min Sketch can be viewed as a kind of counting Bloom filter, but the two are sized on different principles: a counting Bloom filter is typically sized to the number of elements actually inserted, while Count-Min Sketch’s width and depth are sized directly from the target error rate ε and failure probability δ, independent of how many distinct items you expect — which is exactly why it tolerates an unknown or unbounded number of distinct keys more gracefully.
Trade-offs
- One-directional error only: every estimate is greater than or equal to the true count, never less — useful when a false “zero” would be worse than an inflated number, but it means you can never fully trust a reported count without knowing the error bound.
- Bad for uniform, low-frequency distributions: Redis’s own documentation shows that when most items have similar, modest counts, the error-based noise threshold ends up higher than the real counts themselves, making every estimate useless.
- Excellent for skewed, heavy-hitter distributions: when a small number of items dominate the volume (the common case for real traffic, sales, and request data), the sketch stays accurate for exactly the items you’re most likely to care about.
- Mergeable and O(1): constant-time updates and queries per operation, and merging two same-shaped sketches is a simple cell-wise sum — a major advantage for sharded or distributed counting pipelines.
Bottom Line
Count-Min Sketch fills a specific gap that Bloom filters and HyperLogLog don’t: fast, fixed-memory frequency estimation per distinct item, with a mathematically guaranteed, one-directional error. Cormode and Muthukrishnan’s original analysis gives exact formulas for sizing the structure to a target error rate and confidence, and Redis’s production implementation turns that into six commands any application can call directly. If your data is dominated by a long tail of rare, similarly-sized items, this is the wrong structure — the noise threshold will swallow everything. If you need to know which handful of items are hammering your system the hardest, out of a stream too large to count exactly, it’s close to the standard answer.
FAQ
Can Count-Min Sketch ever underestimate a count?
No. By construction, every cell an item maps to can only be incremented by that item or by a colliding item — never decremented in the standard form — so the minimum across all of an item’s cells is always greater than or equal to its true count.
How do I know whether to trust a given estimate?
Redis’s documentation recommends computing a threshold equal to your configured error rate multiplied by the sketch’s total count so far (available via CMS.INFO), and treating any estimate below that threshold as unreliable noise rather than a real count.
Is this the same as a counting Bloom filter?
They’re closely related — a Count-Min Sketch can be viewed as a form of counting Bloom filter — but they’re sized differently: a counting Bloom filter is typically sized to the expected number of distinct elements, while Count-Min Sketch’s dimensions come directly from the target error rate and confidence level, independent of cardinality.
Can two Count-Min Sketches be merged without re-processing the original streams?
Yes, as long as they share the same width and depth (and hash functions). Redis’s CMS.MERGE command combines multiple sketches by summing corresponding cells, producing a mathematically valid sketch of the combined stream.
Sources
- Cormode & Muthukrishnan, “An Improved Data Stream Summary: The Count-Min Sketch and its Applications,” Journal of Algorithms, 2005
- Wikipedia — Count–min sketch
- Redis Documentation — Count-Min Sketch
- Related reading on this site: Bloom Filters Explained
- Related reading on this site: HyperLogLog Explained
Discover more from Software Online Review
Subscribe to get the latest posts sent to your email.
