A count that is never under

A stream of sixty thousand items over an alphabet of a few thousand keys. Afterwards, arbitrary questions of the form: how often did key 731 occur?

Exactly, that costs a hash map — 3,528 entries here, 162,288 bits. The sketch that answers it approximately is a rectangle of counters, four rows deep and sixty-four wide, and it holds 8,192 bits.

The rule is one line each way. To add a key, hash it once per row and increment the cell it lands in. To ask about a key, hash it once per row and return the smallest of the cells.

The one-sidedness is not probabilistic #

The estimate is never below the truth. Not usually, not with high probability — never, on any stream, for any key, under any hash functions.

The argument is immediate and worth stating because so much of what follows leans on it. Every increment for key $x$ lands in $x$’s cell in every row, and nothing ever decrements. So each of those $d$ cells holds $f_x$ plus a non-negative pile of other keys’ counts, and every one of them is at least $f_x$. The minimum of $d$ numbers each at least $f_x$ is at least $f_x$.

This is the strongest property the structure has, and it is the reason it is usable rather than merely accurate. An estimate known to be above the truth can be subtracted from, compared against a threshold with a known direction of failure, and used to rule out a key with certainty — “this sketch says at most 40” is a fact, not a probability. An estimate that could be on either side supports none of that.

It also fixes what the probabilistic part of the guarantee can possibly be about. With the sign settled, all that remains is the size, and the bound reads

$$\hat f_x \le f_x + \varepsilon N \quad \text{with probability at least } 1 - \delta,$$

where $N$ is the total number of items in the stream, $\varepsilon = e/w$ from the width, and $\delta = e^{-d}$ from the depth.

Why the depth gives an exponential #

The width and the depth do different jobs and the difference is the same one the estimate that is a median of means draws in general.

One row is a hash table of $w$ counters with everything colliding freely. The expected junk added to a given cell is the rest of the stream divided by $w$, so by Markov’s inequality the chance of a single row overshooting by more than $eN/w$ is at most $1/e$. That is a constant failure probability, and it is all one row can offer.

The rows then multiply. The estimate is the minimum, so it exceeds the bound only if every row does, and the rows use independently drawn hash functions, so the probability is $e^{-d}$. The minimum is doing the job a median does elsewhere — turning a constant failure probability into an exponential one — and it can do it only because the errors are one-sided. A structure with two-sided errors cannot take a minimum and get an unbiased answer, which is exactly why the median exists.

The exponential is checkable, and checking it is more interesting than it sounds:

Every measured rate is far below what the design permits, and the gap widens with depth — a factor of six at $d = 1$, thirty at $d = 2$, two hundred at $d = 3$. The bound is correct and loose, and how loose is not something the bound reports. The guarantee that is one query wide is where that gap gets its own essay; here it is enough to note that a design sized from $\delta = e^{-d}$ is buying considerably more confidence than it paid for on this stream, and would be buying less on an adversarial one.

Where the junk comes from #

It is worth being concrete about what fills the cells, because the picture people carry is usually of a few unlucky collisions and the reality is that everything collides with everything.

At $w = 64$ and 3,528 distinct keys, each row’s cell holds on average fifty-five distinct keys’ counts. There is no “collision-free” regime here and there was never meant to be: the structure is not a hash table that has been allowed to degrade, it is a projection of a 3,528-dimensional vector of counts onto sixty-four dimensions, repeated four times with different projections. Asking about a key means reading four coordinates of four different projections and taking the most conservative reading.

That framing explains two things at once. It explains why the error is proportional to the total — a coordinate of the projection is a sum over everything mapped to it, so the noise in it is a fixed share of the whole vector — and it explains why nothing about the structure improves when the stream has few distinct keys but many repeats. The count that lands in a cell is the same whether it arrived as one key repeated a thousand times or a thousand keys once each.

The hash has to be a family #

The analysis above uses the expected junk in a cell, and getting that expectation requires the two keys’ landing sites to be independent — pairwise independence, in the precise sense that $\Pr[h(x) = i \wedge h(y) = j] = 1/w^2$ for distinct $x$ and $y$.

That is a stronger requirement than the fast hash families this site has already measured supply. Multiply-shift gives a collision bound and not an independent joint distribution; the sketches here use Carter and Wegman’s $((ax + b) \bmod p) \bmod w$ with $p$ prime, which is exactly pairwise independent and costs one multiplication, one addition and two modulos.

A detail from writing the library is worth recording because it is the kind that leaves no trace. Computing $(a x + b) \bmod p$ with $p = 2^{31}-1$ and 32-bit keys means multiplying two numbers whose product runs to sixty-two bits, and JavaScript’s numbers carry fifty-three. The obvious expression returns a rounded product; the modulus of a rounded product is uniform-looking garbage; and a sketch built on it distributes keys perfectly well and has no independence at all. The multiplication is split so it stays inside a double, and the family is checked by measuring the collision rate of two fixed keys over four thousand draws of $(a, b)$ against $1/w$.

What the additive term actually says #

$\varepsilon N$ is a fraction of the whole stream. Not of the key’s own count, not of the largest count, not of anything about the key being asked about.

At $w = 64$ on a stream of sixty thousand that is $eN/w = 2{,}548$ counts of slack. For the heaviest key, which occurred 9,579 times, that is a possible 27% and a measured 4.1%. For a key that occurred once, the same 2,548 is a possible over-estimate of 254,700%, and the measured figure is 34,100%.

This is not a defect and it is not a subtlety hidden in the proof — it is written on the face of the bound. It is nonetheless the single most common way the structure is misread, because “accurate to within 4%” is what the heavy keys deliver and it is what the sketch gets described as. The guarantee that is one query wide is the essay about that sentence.

The practical consequence is that Count-Min is a heavy-hitter structure. Ask it about keys carrying an appreciable share of the stream and it is excellent; ask it about the tail and it returns numbers with no information in them. Sizing it means deciding what fraction of the stream counts as interesting and setting $w$ from that, rather than deciding what relative accuracy is wanted.

Conservative update, and what it costs #

There is an improvement that costs nothing at query time and is used widely. On an increment, instead of raising all $d$ cells, raise only those currently at the minimum. The estimate is unchanged in principle — it is still the minimum of the same cells — and in practice the cells accumulate less junk.

It works. On the stream above the mean over-count falls from 359 to 213 and the worst from 1,363 to 855, and the one-sided guarantee survives: nothing goes below the truth, because nothing was ever decremented.

There is also an improvement that does not work, and it is instructive because it is published, it measurably lowers the average error, and it destroys the property the structure exists for. Count-Mean-Min subtracts an estimate of the collision noise from each cell — the rest of that row, spread over its other $w-1$ cells — and takes the median of the corrected values. The average error improves. The estimate can now land below the truth, and does: on the stream here it puts a key that occurred 9,579 times at 9,248.

That trade may well be the right one for some caller. What it cannot be is silent, because everything downstream that treated the estimate as an upper bound is now wrong. The site’s gate carries it as a rejection: the one-sidedness assertion is fed Count-Mean-Min and required to refuse it, so that if the check ever stops refusing, the guarantee has quietly stopped being enforced.

Sizing one, in numbers #

The arithmetic is short and worth doing once, because it is where the two parameters stop being letters.

Suppose the requirement is that no estimate is more than half a per cent of the stream above the truth, and that a query fails to meet that no more than one time in fifty. Then $\varepsilon = 0.005$ gives $w = \lceil e/\varepsilon \rceil = 544$, and $\delta = 0.02$ gives $d = \lceil \ln(1/\delta) \rceil = 4$. The table is $4 \times 544$ counters, which at 32 bits each is 69,632 bits — 8.5 kilobytes, for a stream of any length whatsoever.

Two features of that calculation are worth naming. The stream length appears nowhere: the table is the same size for sixty thousand items and sixty billion. And the universe appears nowhere either, so the same table answers about a thousand distinct keys or a billion — with the same absolute slack, which for a billion keys means the slack is larger than nearly all of their counts.

The per-item cost is four hashes and four increments, whatever the parameters, because it is $d$ and $d$ is $\ln(1/\delta)$. Confidence is what makes a Count-Min sketch slow, and accuracy is what makes it big.

And two of them add #

One more property falls out of the design and is the reason the structure is in as many distributed systems as it is. Two sketches of the same shape, built from the same hash functions over two different streams, add cellwise to give exactly the sketch the concatenated stream would have produced. Not approximately — cell for cell.

Decrements, and where the one-sidedness goes #

Everything above assumes counts only go up. That model has a name — the cash-register model — and there is a more general one in which items can be removed as well as added, which the literature calls the turnstile model.

The sketch survives the generalisation and its guarantee does not survive it intact. With decrements allowed, a cell can hold $f_x$ plus a pile of other keys’ counts that may now be negative, so a cell can sit below $f_x$ and the minimum is no longer an upper bound. The bound becomes two-sided — $|\hat f_x - f_x| \le \varepsilon \|f\|_1$ with the same probability, where $\|f\|_1$ is the sum of the absolute counts — and the recommended estimator changes from the minimum to the median, for exactly the reason the estimate that is a median of means gives: a minimum is only the right summary of a set of one-sided errors.

That is a large change dressed as a small one. A structure described as “a Count-Min sketch” may or may not be returning an upper bound, and which it is depends on a property of the stream rather than of the sketch. Everything in this field is in the cash-register model and every plate says so.

The counters are wider than they need to be #

Every size in this essay charges 32 bits a counter, and that is a convention rather than a requirement. A cell holds at most the whole stream, so $\lceil \log_2 N \rceil$ bits suffice — seventeen for the sixty thousand items here, and thirty for a stream of a billion.

At seventeen bits the 8,192-bit table above is 4,352 bits, and every comparison in this field that weighs a sketch against a hash map is quoting a number that is nearly twice what the structure needs. The convention is defensible — a counter that is a machine word is what an implementation holds — and it is worth saying which of the two numbers a bound would be stated in.

There is a further reduction available and it is a composition this collection already has both halves of. The cells do not need to be exact: a cell’s contents are already noise plus an answer, and the noise is a fixed share of the stream. So each cell can be a Morris counter — an approximate counter costing about $\log\log N$ bits — and the sketch’s state falls from $dw\log N$ to $dw\log\log N$.

The price is that two error sources compound. The sketch’s additive error is $\varepsilon N$ and each counter now carries a relative error of its own, so the estimate is $(1 + \eta)(f_x + \text{junk})$ rather than $f_x + \text{junk}$. Whether that is acceptable depends on which term dominates, and on a heavy-hitter query the junk is usually the larger of the two — which is exactly the case where a cheaper counter costs least.

A structure whose cells are already approximate can afford approximate cells, and the reason the composition is not the default is that it makes the guarantee a product of two bounds rather than one, which is harder to state and no harder to hold.

The error is fixed per key, so differences beat levels #

One property of the sketch is easy to miss because it is a non-property: the estimate for a given key does not vary from query to query. The hashes are fixed at construction, so the same key reads the same cells and gets the same junk every time. There is no noise to average away by asking twice, and a system that queries a key repeatedly is reading the same offset again and again.

That sounds like bad news and it is the opposite, for the use these structures are most often put to.

Read a single row’s cell for key $x$ at two times. The cell holds $f_x$ plus the counts of everything that collided with $x$, and the same keys collide at both times. So the difference between the two readings is

$$\bigl(f_x(t_2) - f_x(t_1)\bigr) \;+\; \bigl(\text{colliding mass arriving between } t_1 \text{ and } t_2\bigr)$$

and the junk that accumulated over the whole stream before $t_1$ has cancelled exactly. The error on a difference is a share of the traffic in the interval, not of the traffic since the beginning — so on a long-running stream a rate computed from two readings is enormously more accurate than either reading.

There is a catch and it decides the implementation. The minimum over rows can switch which row it comes from between the two times, and then the cancellation does not happen. To get the exact cancellation the two readings must come from the same cell, which means recording which row the minimum came from — or, more simply, computing differences from a fixed row and using the minimum only for levels.

So a Count-Min sketch is a better rate meter than it is a counter, and the standard interface hides it: an implementation that exposes only estimate(key) cannot express the difference between “how many” and “how many since”, and it is the second question a monitoring system almost always wants.

The shape of the table, at a fixed budget #

The table has two dimensions and only their product is bits, so the same budget can be spent three ways and the estimate is different every time.

And the universe the keys are drawn from is a third quantity the bound does not mention. It sets how many keys share every cell, which is the collision mass the estimate carries, and it does so without appearing anywhere in $\varepsilon n$ — the additive term is written in the length of the stream and not in how many distinct things were in it.

What it does not do #

The sketch answers about keys it is handed. It cannot produce them.

There is nothing in a Count-Min table that can be read back out as a key — the cells hold sums and the hashes are one-way for this purpose — so “which keys were frequent” is a different question requiring either a separate structure alongside, usually a heap of candidates updated as the stream goes past, or a different design entirely. The items that survive k counters is the different design, it is deterministic, and at equal state it is the more accurate of the two on exactly this question.