Count-Min Sketches and the Bias of Always Rounding Up

A membership question has a yes-or-no answer, so an error can be pushed to one side and forgotten. A frequency question has a magnitude, and any error is visible in the number returned. Storing exact counts for every key in a stream requires space proportional to the number of distinct keys, which for network traffic or query logs is the quantity being measured. A Count-Min sketch stores a fixed grid of counters instead, updates a handful of them per item, and answers “how many times has this key appeared” with an error that is always in one direction: the estimate is never below the truth, and it exceeds it by at most a quantity that depends on the total stream length and the grid’s width.

The grid and the minimum

The state is a two-dimensional array of $d$ rows and $w$ counters per row, all initialised to zero, plus $d$ hash functions that each map a key into $[0, w)$. Insertion of a key increments the counter at position $(\text{row } i, h_i(\text{key}))$ in every row. A query returns

$$ \hat{c}(x) = \min_{1 \le i \le d} \text{count}\big[i, h_i(x)\big] $$

The minimum is what makes the error one-sided. A counter at position $(i, h_i(x))$ is incremented by every item that hashes there, including items other than $x$, so it holds the true count of $x$ plus the counts of all colliding keys. That excess is never negative, so each row’s counter overestimates, and the minimum of $d$ overestimates is at least as close as the best row.

The bound follows from the collision mass. Let $N$ be the total number of insertions and let $c(x)$ be the true count. If the hash functions are uniform and pairwise independent, the expected excess in one row is $N/w$, and the probability that the excess exceeds $eN/w$ is at most $1/e$. Taking the minimum over $d$ independent rows raises the failure probability to $e^{-d}$. Choosing

$$ w = \left\lceil \frac{e}{\varepsilon} \right\rceil, \qquad d = \left\lceil \ln \frac{1}{\delta} \right\rceil $$

gives $\hat{c}(x) \le c(x) + \varepsilon N$ with probability at least $1 - \delta$. A 1% relative error against a stream of ten million items therefore needs $w \approx 272$ counters per row and, for a 1% failure probability, $d \approx 5$ rows — about 1,360 counters, or a few kilobytes. The same accuracy over ten million distinct keys would need tens of megabytes of exact counts.

The error is additive in the stream length, not relative to the key’s own count. That distinction is the one most often missed. A key seen 100 times in a stream of ten million is estimated with an absolute slack of about 100,000 at $\varepsilon = 0.01$ — the estimate may be off by a factor of a thousand, and it will be off on the high side. The structure is useful for finding frequent items, not for counting rare ones.

Width, depth, and what each buys

Width controls accuracy; depth controls confidence. Doubling $w$ halves the additive error. Adding a row multiplies the failure probability by $1/e$ — roughly 0.37 — so depth is cheap in space and expensive in update work, because every insertion touches all $d$ rows.

The standard shapes reflect that asymmetry. A common configuration is $d = 4$ to $d = 7$ rows with $w$ in the thousands, giving failure probabilities from 1.8% down to 0.09% at a cost of four to seven counter increments per item. Because the counters are small — often 32-bit, sometimes 16-bit with saturation — a grid of seven rows by 8,192 counters occupies 224 KB at 32 bits. The additive error follows from the width: with $w = 8192$ the bound is $\varepsilon = e/w \approx 3.3 \times 10^{-4}$ of the stream length, so against a stream of a million items no estimate is wrong by more than a few hundred counts, and against a stream of ten million by a few thousand. The failure probability is $e^{-d} \approx 0.09%$ at seven rows.

Counter width is a real decision. A 32-bit counter saturates after four billion increments, which is reachable for a hot key in a long-running stream; saturation makes the counter a constant and destroys the guarantee for every key that shares the cell. Sixteen-bit counters saturate far sooner. The alternatives are to use saturating arithmetic and accept a bounded underestimate for the hottest keys — which breaks the one-sided guarantee — or to widen the counters and pay the memory. Implementations that report heavy hitters usually widen.

Conservative update

The plain update increments every row’s cell, including cells whose value is already much larger than the true count. Those increments add noise to cells that other keys depend on. Conservative update avoids most of it: compute the current minimum, then increment only those cells that equal that minimum.

import hashlib

def row_hash(key, seed, w):
    """One 64-bit value per (key, row); seed distinguishes the rows."""
    d = hashlib.blake2b(key, digest_size=8, salt=seed.to_bytes(8, 'little')).digest()
    return int.from_bytes(d, 'little') % w

class CountMin:
    def __init__(self, w, d, seeds):
        self.w, self.d, self.seeds = w, d, seeds
        self.grid = [[0] * w for _ in range(d)]

    def _cells(self, key):
        return [(i, row_hash(key, s, self.w)) for i, s in enumerate(self.seeds)]

    def add(self, key, n=1):
        cells = self._cells(key)
        floor = min(self.grid[i][j] for i, j in cells)
        for i, j in cells:
            if self.grid[i][j] == floor:      # only raise cells that set the minimum
                self.grid[i][j] += n

    def estimate(self, key):
        return min(self.grid[i][j] for i, j in self._cells(key))

The result is never below the true count, because the minimum cell is incremented by at least the inserted amount, and it is usually much closer than the plain scheme. The published analysis shows conservative update can reduce the error by a large factor on skewed streams, where a few hot keys dominate and the plain scheme wastes increments on cells already polluted by them. It does not improve the worst-case bound — an adversary who arranges collisions can still force the full excess — so the guarantee is unchanged and only the typical case improves.

The cost is that the update is no longer independent per cell: it must read all $d$ cells before writing any, which doubles the memory traffic per insertion and turns a set of independent increments into a read-then-write sequence. For a sketch updated by many threads, that also removes the option of atomic per-cell increments without a lock, since the decision to increment depends on a value another thread may be changing.

Deletion and the sign problem

Counters can be decremented, which is what makes the structure usable for sliding windows and for streams with retractions. The hazard is that a counter can go negative, and a negative counter makes the minimum meaningless: a cell that is negative because it was decremented more often than incremented will pull the estimate below the true count, converting the one-sided error into a two-sided one.

The safe pattern is to decrement only keys that were genuinely inserted, and to accept that collisions mean a decrement may drive a cell negative even when every removal is legitimate. A stream in which each key is removed exactly as often as it was added can still produce negative cells, because the cell is shared. In practice, sketches used for windows are either rebuilt per window or kept with saturating non-negative counters and a documented bias.

The structure has no way to enumerate keys, so it cannot answer “which keys are frequent” on its own. Heavy-hitter tracking layers a candidate list on top: each update checks whether the estimate exceeds a threshold, and candidates above it are kept in a small exact table. The sketch supplies the estimates; the table supplies the identities. The space is the sketch plus the table, and the table must be small — a few hundred entries — or the point of the sketch is lost.

Where the bias becomes a feature

The one-sided error is exploitable. Because every estimate is an upper bound, a query that returns a small number is trustworthy: a key whose estimate is below a threshold is certainly below it. That makes the structure suitable for admission decisions where a false rejection is unacceptable and a false acceptance is merely wasteful, the same asymmetry a Bloom filter provides for membership. The two structures are often paired: the filter decides whether a key has been seen at all, and the sketch estimates how often.

The complementary construction, the count sketch, replaces the minimum with a median and uses signed counters, which removes the bias at the cost of a weaker tail bound and a requirement that the hash functions include a random sign. The comparison is instructive: the Count-Min sketch is biased upward with a tight bound, the count sketch is unbiased with a looser one, and the choice depends on whether the application can tolerate systematic overestimation. Workloads that compare estimates against each other — ranking heavy hitters — prefer the unbiased form, because a shared bias cancels in the comparison while a random one does not. Workloads that compare an estimate against a fixed threshold prefer the Count-Min form, because the bias is bounded and known.

The sketch’s other limitation is that its parameters are fixed at construction. A grid sized for a stream of a million items degrades as the stream grows, since the additive error is proportional to $N$. There is no resize path that preserves the contents: the counters cannot be rehashed into a wider grid without the original keys. Long-lived sketches are therefore either rebuilt periodically or chained, which is the problem resizing and aging takes up.