Count-Min Sketch: Why the Minimum of Overestimates Is the Estimate

A stream of events arrives and, at arbitrary points, a query asks how many times a particular key has appeared. Storing every key is linear space and the answer is exact. The Count-Min sketch answers the same query in a fixed amount of memory, always errs in one direction, and bounds the error in terms of the total stream weight rather than the queried key’s own count. The design is a grid of counters with one hash per row, and the query is the smallest counter in the column the key hashes to. Both choices look arbitrary until the error analysis is laid out.

One row would be enough if hashes never collided

Consider a single row of $w$ counters. Each key $i$ hashes to a position $h(i)$, and an update of weight $\Delta$ adds $\Delta$ to that counter. The counter at position $j$ holds

$$ C[j] = f_j^{\ast} + \sum_{i \neq j^{\ast} : h(i) = j} f_i $$

where $j^{\ast}$ is the key being queried. The first term is the answer; the rest is the mass of all other keys that collide with it. Because updates are non-negative in the insert-only model, collisions can only add. The estimate is therefore never below the truth: $\hat{f} \geq f$.

That one-sided error is the useful property. If the estimate is $f + E$ for some non-negative $E$, then an application that can tolerate overcounts but not undercounts — rate limiting, quota enforcement, cache admission — can use the raw estimate without any probabilistic language. The question becomes how large $E$ can get, and the answer depends on how much mass lands in the queried key’s row position.

With $w$ positions and a hash that spreads mass uniformly, the expected collision mass in one position is at most $N/w$, where $N = \sum_i f_i$ is the total stream weight. Markov’s inequality then says the probability that the collision mass exceeds $\varepsilon N$ is at most $1/(\varepsilon w)$. Choosing $w = \lceil e/\varepsilon \rceil$ makes that probability at most $1/e$, about 0.368. One row therefore fails with substantial probability, and the failure is not a mild overshoot: it is the entire collision mass of the row.

Independence across rows turns one weak bound into a strong one

The sketch uses $d$ rows, each with its own hash function, and answers a query with

$$ \hat{f} = \min_{r=1}^{d} C_r[h_r(i)] $$

Each row’s estimate is an independent overestimate. The minimum is also an overestimate, and it is the closest of the $d$. A row produces an error above $\varepsilon N$ with probability at most $1/e$, independently across rows, so all $d$ rows fail simultaneously with probability at most $e^{-d}$. Setting $d = \lceil \ln(1/\delta) \rceil$ makes that at most $\delta$.

The combination is worth restating because it is the whole design: $w = \lceil e/\varepsilon \rceil$ controls the size of the error, and $d = \lceil \ln(1/\delta) \rceil$ controls the probability of exceeding it. The two dimensions are independent. Accuracy costs linear space in $1/\varepsilon$; confidence costs logarithmic space in $1/\delta$. This asymmetry is why Count-Min is cheap in practice: at $\varepsilon = 0.001$ and $\delta = 0.001$, the sketch is $2719 \times 7$ counters, which at four bytes each is about 76 kilobytes.

import math, hashlib

class CountMin:
    def __init__(self, epsilon, delta, seed=b'cms'):
        self.w = math.ceil(math.e / epsilon)
        self.d = math.ceil(math.log(1 / delta))
        self.seed = seed
        self.rows = [[0] * self.w for _ in range(self.d)]

    def _idx(self, key, row):
        h = hashlib.blake2b(key + row.to_bytes(2, 'big') + self.seed,
                            digest_size=8).digest()
        return int.from_bytes(h, 'big') % self.w

    def add(self, key, delta=1):
        for r in range(self.d):
            self.rows[r][self._idx(key, r)] += delta

    def estimate(self, key):
        return min(self.rows[r][self._idx(key, r)] for r in range(self.d))

Deriving the row hash from the row index is a shortcut that keeps the example short. A sketch that must hold up to an adversary uses a family of pairwise-independent hashes whose seeds are independent, so that the collision events across rows really are independent; a single base hash with a row suffix is close to independent in practice but has no proof attached.

Conservative update and the space it recovers

The standard update increments one counter per row. That is wasteful when the key’s true count is far below the counter’s current value: incrementing pushes the counter above every key that collides with it, including the queried key’s future estimates.

Conservative update changes the rule. On an increment of key $i$, first compute the current minimum $m = \min_r C_r[h_r(i)]$, then set each counter to $\max(C_r[h_r(i)], m + 1)$ rather than adding 1 to it. Counters already above the minimum are left alone, so the sketch tracks the largest frequencies more tightly and the minimum is not raised unnecessarily.

The effect is largest for low-frequency keys, which is exactly where the plain sketch’s relative error is worst. For a key seen once in a stream of a billion, the plain estimate can be the entire collision mass; the conservative estimate is close to 1, because the counters it touches only need to exceed the running minimum. The asymptotic guarantee is unchanged — the worst-case bound still applies — but the constant and the typical error improve markedly, and the update costs one extra read per row.

A second variant, Count-Mean-Min, subtracts an estimate of each row’s noise floor before taking the minimum, which reduces the positive bias for keys with small true counts. The estimate becomes $\text{median}_r \big(C_r[h_r(i)] - (N - C_r[h_r(i)])/(w-1)\big)$. The median rather than the minimum is used because the correction can push a row’s value below the truth, and the minimum would then systematically underestimate.

Queries beyond a single key

The same grid answers several other questions, each with its own error expression.

Range queries. A range sum over a contiguous key interval is not a fixed set of coordinates, so a plain sketch has nothing to read. The standard treatment maintains one sketch per level of a binary trie over the key space, and the sketch at level $\ell$ has one bucket per node at that level plus a slack bucket holding the mass of keys at the previous level that are not covered by a node at this one. The slack bucket is what keeps the total error at the single-sketch level: an interval sum is assembled from $O(\log m)$ node estimates, and without the slack accounting those errors would compound to $\varepsilon N \log m$.

Inner products. Two sketches built with the same hashes can estimate $\sum_i f_i g_i$ by taking, for each row, the dot product of the two counter arrays and then the minimum or median across rows. The error scales with $\varepsilon |f|_2 |g|_2$ in the standard analysis, not with $\varepsilon N$, so the estimate is useful precisely when the vectors are sparse. The same-hash requirement is strict: sketches with different seeds cannot be combined this way.

Heavy hitters. Every estimate is at least the true frequency and at most $\varepsilon N$ above it, so thresholding the estimates at $\varepsilon N$ reports every key whose true frequency exceeds $2\varepsilon N$. Keys below that may or may not appear. This makes Count-Min a heavy-hitter finder with a false-positive rate that depends on the data, and it is the basis for the more economical counters in Misra-Gries and Space-Saving.

Mergeability. Adding two Count-Min sketches with identical dimensions and hashes gives the sketch of the concatenated stream, counter by counter. This is the linear-sketch property described in the streaming model, and it holds for Count-Min without qualification because the update is an addition.

When the guarantee does not apply

The proof depends on four things, and each has a failure mode that appears in real deployments.

Signed updates break the minimum. If a stream contains deletions or negative weights, a counter can be dragged below the true frequency by a colliding key with negative mass. The minimum then becomes an underestimate, and the one-sided guarantee is gone. The fix is to keep two counter arrays, one for positive and one for negative updates, and estimate with their difference; the error bound doubles. Applying the plain sketch to a turnstile stream silently produces estimates that can be arbitrarily wrong in either direction.

The error is relative to the total, not the key. A 0.1 percent error bound on a stream of a billion events is an absolute error of a million. For a key that occurs ten times, the estimate is useless regardless of $\varepsilon$. Applications that care about rare keys need either a much smaller $\varepsilon$ — which means much more memory — or a different structure entirely, such as an exact table for the head and a sketch for the tail.

Hash quality is load-bearing. The bound assumes each hash behaves like a uniform random function over the key space. A sketch seeded with a fixed constant and exposed to adversarial keys can be made to collide every queried key with one hot key, at which point every row reports the same inflated value. Randomising the seed per sketch instance, and keeping it secret from the input producer, restores the argument.

Width must be integral and large. Rounding $w$ down rather than up loses the $e$ factor in the width and weakens the bound by a constant. Rounding $d$ down from a value like 2.3 loses an entire row of independence. Implementations that compute $w$ and $d$ with floating point and truncate introduce a small, systematic optimism into the guarantee.

The family of counter-based sketches

Count-Min is one member of a family that trades the shape of the error for the shape of the update.

Structure	Error model	Update cost	Handles deletions
Count-Min	additive, $\varepsilon N$	$d$ increments	with paired arrays
Count Sketch	$\ell_2$-bounded, median of signed counters	$d$ increments or decrements	yes, natively
Misra-Gries	per-key, $N/k$	$k$ decrements worst case	no
Space-Saving	per-key, $N/k$	one bucket update	no

Count Sketch replaces the minimum with a median and stores signed counters, which makes the error proportional to the $\ell_2$ norm of the frequency vector rather than the $\ell_1$ norm. For skewed streams — the usual case — the $\ell_2$ norm is far smaller than $N$, so the effective error is much lower. The cost is that the estimate can be negative or zero for a key with a small true count, and the median is conventionally taken over an odd number of rows so that the middle value is unambiguous.

The choice between these structures is decided by three questions: whether updates can be negative, whether the error should be relative to the total or to the key’s own count, and whether the structure must merge with another instance. Count-Min answers insert-only, total-relative, mergeable; Misra-Gries answers insert-only, key-relative, and merges only with extra error; Count Sketch answers signed, norm-relative, mergeable. No single structure answers all three favourably, and the frequency moment sketch covers the case where the question is a global statistic rather than a per-key count.