The Count-Min Sketch page ends on a guarantee that only points one way: its frequency estimate can never fall below the true count, only above. That one-sidedness is the whole trick when the question is "how big could this be, at worst" — but it also means every estimate carries the same baked-in upward lean, no matter how many independent sketches get built or averaged. Count Sketch answers the identical question, "roughly how many times has this item appeared," with the opposite trade: an estimate that lands above the truth about as often as it lands below, centered on the real answer instead of pinned above it.
The structure is nearly identical — the same d × w grid of counters, the same
two hash-derived row indices Count-Min Sketch uses to spread each add across d independent rows.
What's new is a second hash per row producing a random sign, +1 or
−1. Adding an item multiplies its count by that row's sign before adding it to the
counter — so counters aren't running tallies of "how many things landed here," they're running
sums that can go negative. Querying an item recomputes the same signs, multiplies each row's raw
reading back by its own sign to undo the flip, and reports the median of the d
corrected readings — not the minimum.
The sign is the whole trick, and it's worth being precise about why it works. When two different items collide in the same cell, Count-Min Sketch's counter can only ever grow — the collision's damage is one-directional and permanent. A Count Sketch cell also mixes contributions from whatever else collided there, but each contributor's sign is an independent coin flip: on average, an equal number of colliding contributions push the cell up as push it down, and they partly cancel instead of stacking. The correction step (multiplying back by the queried item's own sign) recovers an estimate that's correct in expectation — the collision noise still shows up in any single query, but it's centered on zero rather than always positive, and taking the median of d independent readings suppresses whichever row's noise happened to swing hardest that time.
The same nine-word stream Count-Min
Sketch's own demo uses — cat, dog, cat, bird, cat, dog, fish, cat, owl — true
counts cat=4, dog=2, bird=1, fish=1, owl=1 — loaded here into a smaller d = 3,
w = 6 grid (small on purpose, so collisions are common enough to see the correction
actually working). Query bird or fish first: both land on 1, an
exact match. Then query cat (true count 4) and watch it come back
3 — an underestimate, something Count-Min Sketch's own guarantee
forbids outright. Then query owl (true count 1) and watch it read
2, an overestimate the opposite direction. Finally query lion —
never added at all — and watch it report −1: a negative count for an item that was
never seen, which is not a bug, just what "the noise happened to land below zero this time" looks
like for an estimator with no floor.
sign × count to table[row][idx] at each
one. O(d), same as Count-Min Sketch's add.O(d) (the sort is over a fixed, tiny d, not the data).function fnv1a(s, seed) {
let h = (0x811c9dc5 ^ seed) >>> 0;
for (let i = 0; i < s.length; i++) {
h ^= s.charCodeAt(i);
h = Math.imul(h, 0x01000193);
}
// same Murmur3-style finalizer xor-filter.html's own hash uses -- a raw FNV hash's low bit
// is linear (exactly the XOR of the input bytes' own low bits), so two hashes of the same
// string derived from the same raw hash family can share a parity that looks independent
// but isn't. See Pitfalls for what happens without this step.
h ^= h >>> 16;
h = Math.imul(h, 0x85ebca6b);
h ^= h >>> 13;
return h >>> 0;
}
const SEED_INDEX = 0x1b873593; // seed family for bucket indices
const SEED_SIGN = 0x9e3779b1; // a separate seed family for the +1 / -1 sign
class CountSketch {
#table; // d rows, each a length-w *signed* counter array
#d;
#w;
constructor(d, w) {
this.#d = d;
this.#w = w;
this.#table = Array.from({ length: d }, () => new Int32Array(w));
}
#indices(item) {
const idxs = [];
for (let i = 0; i < this.#d; i++) idxs.push(fnv1a(item, (SEED_INDEX + i) >>> 0) % this.#w);
return idxs;
}
#signs(item) {
const signs = [];
for (let i = 0; i < this.#d; i++) {
signs.push((fnv1a(item, (SEED_SIGN + i) >>> 0) & 1) === 0 ? 1 : -1);
}
return signs;
}
add(item, count = 1) {
const idxs = this.#indices(item);
const signs = this.#signs(item);
idxs.forEach((idx, row) => { this.#table[row][idx] += signs[row] * count; });
}
estimate(item) {
const idxs = this.#indices(item);
const signs = this.#signs(item);
const corrected = idxs.map((idx, row) => signs[row] * this.#table[row][idx]);
corrected.sort((a, b) => a - b);
return corrected[(this.#d - 1) >> 1]; // d is odd -> the true middle element
}
}Verified in Node, self-tested before being trusted, all against a 40-of-441-item skewed stream
(one heavy item added 40 times among 400 distinct one-off fillers, d = 3,
w = 64), run across 5,000 independently seeded sketches so the same theoretical claim
being checked — unbiasedness over the random choice of hash functions — is what's actually
being measured, not just "one lucky stream." (1) Two-sided, centered error: the
heavy item's estimate came in above the true count 37.3% of the time, below it 37.7%, and exactly
right the rest — mean error 0.003 (essentially zero) versus a parallel Count-Min Sketch built from
the identical stream and indices, which overestimated on 99.4% of the same 5,000 trials with a mean
error of +4.198 and never once underestimated. Mean absolute error came out lower for
Count Sketch too (1.272 vs. 4.198) on this specific skewed configuration — not a universal
ranking (see Complexity below for when Count-Min Sketch's guarantee is worth more than a smaller
average error), just what this stream measured. (2) The self-test that makes (1)
meaningful: deliberately breaking the sign hash (Pitfall 3 below) on the same stream and
trial count flips the 37/38/25 split to 100% overestimates — confirming the unbiasedness check
above would actually catch a broken implementation, not just pass by construction. (3) The exact
shipped demo numbers, reproduced standalone from the same 9-word stream in the same order:
cat → 3 (true 4), dog → 1 (true 2), bird → 1, fish → 1 (both exact), owl → 2 (true 1), and lion →
−1 despite never being added. See /tmp/csk/*.js, scratch, not committed.
Taking the minimum instead of the median throws away the whole point. The
instinct, having just built something that looks almost exactly like a Count-Min Sketch, is to
reuse its query rule — take the smallest (or, seeing negative numbers, the most extreme) reading.
Tested directly on the same skewed stream (5,000 trials): using min() over the signed,
corrected readings instead of the median produced a mean error of −2.108, understating the true
count on 80.5% of trials. It isn't just worse, it's biased in the opposite direction from
what a reader primed by Count-Min Sketch would expect — there's no "safe side" to lean on here,
because unlike Count-Min Sketch's raw counters, these readings can be negative, and the minimum of
a mix of positive and negative numbers isn't a bound on anything.
Forgetting to multiply back by the item's own sign before taking the median. The raw counter at a row's index already reflects that row's sign convention baked in when the item was added; querying without re-applying it treats every row's raw value as if it directly represented the item's count. Tested on the same stream: median of the raw, uncorrected readings produced a mean error of −40.3 against a true count of 40 — essentially reporting the negative of the right answer whenever the queried item's own sign in most rows happened to be −1, since the raw cell already has that flip applied and the query never undoes it. 50.4% of trials were off by more than 10.
Deriving the sign from the index instead of an independent hash. The index and
the sign are supposed to be unrelated, but it's tempting to save a hash call and reuse the bucket
index's own parity as the sign — idx % 2 === 0 ? 1 : -1. This looks harmless (it's
still "randomly" +1 or −1 depending on the item) but it's fatal: two items land in the same bucket
exactly when they share an index, and this scheme makes the sign a direct function of the
index — so any two colliding items are now guaranteed the same sign, never a
mix. Collisions stop partially cancelling and start stacking every time, exactly like an unsigned
counter. Measured on the same 5,000-trial stream: 100% of trials overestimated (versus the 37/38/25
split above) with a mean error of +6.196 — the two-sided guarantee doesn't degrade gracefully here,
it collapses completely, because the flaw is structural rather than a matter of degree.
Σ count(item)²)
of a stream, something a one-sided sketch like Count-Min Sketch can't do as cleanly, since
squaring an overestimate-biased value compounds the bias.Time: both add and estimate are O(d),
identical to Count-Min Sketch — the sort inside estimate is over the fixed, tiny d,
not over any growing quantity. Space: the same fixed O(d·w)
counters, sized the same way from a tolerable error and confidence budget, and subject to the same
"can't grow the grid after the fact" limitation Count-Min Sketch's own Pitfalls section names —
except each counter here needs a sign bit's worth of extra range (a real implementation uses a
signed integer type, not an unsigned one).
Choosing between the two comes down to what "wrong" is allowed to look like: Count-Min Sketch when a hard, one-directional bound matters more than the average case (rate limiting, catching heavy hitters where "we said more than there really were" is the safe failure mode); Count Sketch when the estimate needs to be right on average, sketches need to be combined or averaged across shards without compounding a shared bias, or a squared/moment-style quantity is being estimated and a one-sided bias would distort it further. This site's guide, Choosing a Probabilistic Structure, compares both against HyperLogLog, Reservoir Sampling, and the site's other fixed-memory unbounded-stream structures side by side.