The Bloom filter page answers one narrow question in fixed memory: "have I seen this before?" A Count-Min Sketch answers a different narrow question, in the same fixed memory no matter how many items go in: "roughly how many times have I seen this?" Same trade — give up exactness, keep the memory flat — for a counting problem instead of a membership one.
Instead of a single bit array, a Count-Min Sketch keeps a small d × w grid of
counters — d rows, each an independent hash table of w buckets,
all starting at 0. Adding an item runs it through d hash functions, one per row,
and increments the counter each one points to — so a single add touches exactly one
cell in every row, not one cell total. Estimating an item's count runs the same d hash
functions and reads the same d cells, then reports the minimum of the d readings —
not the sum, not the average.
The minimum is the whole trick, and it's worth being precise about why. Any single row can be polluted: two different items can hash to the same bucket in that row, and whichever one is queried will read the combined count of both, an overestimate. But it's far less likely that every row happens to collide the same item with something else — the rows use independent hash functions, so a bucket crowded in row 2 is, most of the time, a different, less-crowded bucket in row 0. Taking the minimum across all d rows means picking the least-polluted reading available, which gives the tightest safe upper bound the sketch can offer.
"Safe" is the operative word, and it mirrors the Bloom filter's own guarantee in the opposite
direction. A Bloom filter can never wrongly say no — only wrongly say yes. A Count-Min
Sketch can never undercount — only overcount. Counters only ever go up, and every
add touches the same d cells a later query for that exact item will read, so those cells can never
read lower than the true count on any row — meaning the minimum of all d rows can't either.
The estimate is always a real lower bound on how wrong it can be: estimate(item) ≥
true_count(item), always, no matter how the collisions fall.
That one-sidedness is a deliberate trade, not a limitation to work around: it's what makes a hard "at most this many, guaranteed" bound possible at all. Count Sketch answers the identical per-item frequency question with the opposite trade — a random sign per row instead of a plain increment, a median instead of a minimum — giving up the never-undercounts guarantee for an estimate that's unbiased and centered on the truth instead of always leaning above it.
Nine words have already been added, in this order: cat, dog, cat, bird, cat, dog, fish,
cat, owl — true counts cat=4, dog=2, bird=1, fish=1, owl=1 (d = 3 rows,
w = 12 columns). Query dog first: all three rows read exactly 2, so
the estimate matches the true count exactly. Then query cat: the three rows read
5, 6, and 5 — every row is polluted by something, but the minimum (5) is only one more than the
true count of 4, not the six a single unlucky row would have reported alone. Then query
lion — a word never added at all — and watch it come back reporting a count of 1,
not 0. Add your own words (with an optional count greater than 1) and watch the grid fill in.
count to table[row][idx] at each one. O(d),
independent of how many distinct items or total additions have happened already.O(d).function fnv1a(s) {
let h = 0x811c9dc5;
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 0x01000193);
}
return h >>> 0;
}
function djb2(s) {
let h = 5381;
for (let i = 0; i < s.length; i++) {
h = (Math.imul(h, 33) + s.charCodeAt(i)) >>> 0;
}
return h >>> 0;
}
class CountMinSketch {
#table; // d rows, each a length-w counter array
#d;
#w;
constructor(d, w) {
this.#d = d;
this.#w = w;
this.#table = Array.from({ length: d }, () => new Uint32Array(w));
}
// same Kirsch-Mitzenmacher trick as the Bloom filter: two real hashes, d derived indices
#indices(item) {
const s = String(item);
const h1 = fnv1a(s);
const h2 = djb2(s);
const idxs = [];
for (let i = 0; i < this.#d; i++) {
idxs.push(((h1 + i * h2) >>> 0) % this.#w);
}
return idxs;
}
add(item, count = 1) {
this.#indices(item).forEach((idx, row) => { this.#table[row][idx] += count; });
}
estimate(item) {
return Math.min(...this.#indices(item).map((idx, row) => this.#table[row][idx]));
}
}Verified three ways, all in Node, self-tested before being trusted: (1) the never-undercounts
invariant, across 5,000 randomized trials varying d (2-5), w (6-45), and
the item stream (27,232 individual estimate checks total) — zero cases where the estimate came in
below the true count. Proved this check would actually catch a broken implementation first: a
deliberately sabotaged counter (one that silently drops an increment on every third add) produced 2
real undercounts on the same kind of randomized stream, confirming "zero undercounts" on the real
implementation means something rather than the check being toothless. (2) An empirical error-bound
measurement for the shipped demo's exact configuration (d=3, w=12): the standard
Count-Min bound says estimate(item) ≤ true_count(item) + ε·N with probability
≥ 1 - e^-d, where ε = e/w and N is the total count added so
far — for this configuration ε ≈ 0.227 and the failure probability is bounded by
e^-3 ≈ 5.0%. Across 2,000 randomized streams (18,598 individual checks) the bound was
actually exceeded only 0.57% of the time, comfortably under the 5% worst-case the theory allows
(the theory is a guarantee, not a tight prediction — it's supposed to hold up with room to spare).
(3) The exact shipped demo numbers, reproduced standalone from the same stream in the same
order — cat's three row-readings of 5, 6, 5 (estimate 5, true 4), dog/bird/fish/owl all landing
exactly on their true counts, and lion's reading of 1 despite never being added. See
/tmp/cms/selftest.js and /tmp/cms/detail.js, scratch, not committed.
Only ever overestimates, never underestimates — the mirror of the Bloom filter's guarantee, in the opposite direction. Every add to an item touches the exact same d cells that item's own later queries will read, and counters never decrease, so those cells can never read below what that item alone contributed. The minimum of the d readings inherits that floor. What it can't guarantee is a ceiling: other items sharing any of those cells only ever push the reading up. Same pigeonhole logic as the Bloom filter and Rabin-Karp's hash collisions before it — finitely many cells, unboundedly many possible items, so collisions are a certainty eventually, not a bug to eliminate.
Independent rows blunt collisions, they don't erase them. In the live demo,
querying cat (true count 4) reads 5, 6, and 5 across the three rows — every single
row is polluted by something, by a different amount each. Taking the minimum recovers 5, only one
over the truth; a sketch with d = 1 (a plain hash array of counters, no rows to
compare) would have had no choice but to report whichever single reading it happened to have — 6 in
this case, twice as far off. More rows narrow the gap between the estimate and the truth; they
don't close it to zero, and can't, without also growing w or accepting a wider error margin.
A full collision across every row is rare, but undetectable from the estimate alone. In this exact demo's configuration, lion — never added — hashes to the identical three cells, in all three rows, as fish — added once. Querying either one reads the same number, because by this configuration's hash arithmetic they are, for counting purposes, indistinguishable: the sketch has no way to tell "this cell's count came from fish" apart from "this cell's count came from lion," since it never stored which item set which counter. This is worse in one respect than the Bloom filter's false positive, which only ever answers a binary yes/no; here, two entirely different keys can silently share one one's count with the other, and nothing in the returned number reveals that it happened.
d and w have to be picked ahead of time, from how much
error is tolerable (ε, setting w = ⌈e/ε⌉) and how confident the bound
needs to be (δ, setting d = ⌈ln(1/δ)⌉) — both need at least a rough
estimate of the eventual total count N, since the bound scales with ε·N.
Same limitation the Bloom filter's own Pitfalls names for m and k: growing
the grid after the fact isn't possible without re-adding every item from scratch against the new
size, which needs keeping every item around somewhere, undercutting the reason to use a fixed-size
sketch in the first place.
CMS.INCRBY/CMS.QUERY commands (the
RedisBloom module) ship a Count-Min Sketch alongside the Bloom filter and
HyperLogLog — the same module bundling all
three because they solve three different approximate questions ("is it in," "how many," "how
many distinct") with the same fixed-memory trade.O(n) memory a real per-key counter map costs isn't
affordable.Time: both add and estimate are O(d),
flat — like the Bloom filter's O(k), the cost never grows with how many items are
already in the sketch or how many times any of them have been added. Space: a fixed
O(d·w) counters, chosen once up front from the tolerable error ε and
confidence δ — independent of the number of distinct items and, unlike a hash map of
counters, independent of the total count added (up to where the error bound stops being useful).
Same fixed footprint the Bloom filter trades for exactness, spent on "how many" instead of "is it
in."
This site's guide, Choosing a Probabilistic Structure, compares this entry against HyperLogLog, Reservoir Sampling, and the site's other fixed-memory unbounded-stream structures side by side.