A sketch that is allowed to be under

A Count-Min sketch is a table of counters, $d$ rows by $w$ columns, with one hash per row. Every arrival adds one to a cell in each row; a query takes the minimum of its $d$ cells. Because every cell is a sum of non-negative counts, the estimate is never below the truth — an unconditional property with no probability attached, and the reason six essays of this field lean on it.

Change one thing. Give every row a second hash, $s_j$, which returns $\pm 1$; on arrival of key $x$ add $s_j(x)$ rather than $1$ to cell $h_j(x)$ of row $j$; on query, take $s_j(x)$ times the cell, and report the median over rows rather than the minimum.

That is Count-Sketch, and this essay is what the change costs and what it buys.

What the sign does #

In a Count-Min cell, every key that hashes there contributes its own count, positively. The cell holds $f_x$ plus a pile of other keys’ counts, so the error is one-sided and its size is the mass of the colliding keys — on average $(F_1 - f_x)/w$, and the minimum over $d$ rows picks the luckiest of $d$ such piles.

In a Count-Sketch cell, each colliding key contributes $\pm f_y$ with the sign its own hash drew. Multiplying back by $s_j(x)$ at query time leaves $f_x$ plus a signed sum of other keys’ counts, and that sum has mean zero. The estimate is unbiased: too high as often as too low, by an amount whose size is the standard deviation of a signed sum rather than the total of an unsigned one.

That is the same cancellation the tug-of-war estimator runs on, applied one cell at a time. Count-Sketch is a table of tug-of-war registers with a hash deciding which register each key lands in, and the family relationship is exact rather than an analogy: the sum of the squares of a Count-Sketch row is itself an estimate of $F_2$.

The error changes currency #

The two error bounds are in different units and that is the whole story.

Count-Min’s additive error is proportional to $\lVert f \rVert_1$, the sum of all the counts — the length of the stream. Count-Sketch’s is proportional to $\lVert f \rVert_2$, the square root of the sum of the squares. On this essay’s stream those are 60,000 and 12,409: the second is 4.84 times smaller than the first, and on a more skewed stream the gap is wider still.

The reason a signed sum is smaller than an unsigned one is that random signs make errors add in quadrature rather than linearly. A thousand keys of count ten sum to 10,000 with plus signs and to about $10\sqrt{1000} = 316$ with random ones.

Measured, at equal bits #

Eight seeds each, $d = 4$, $w = 64$, 8,192 bits apiece, over 60,000 items on 2,004 distinct keys.

The signed sketch is 2.69 times more accurate on the keys anybody asks about, at identical state, and it is worse in exactly one respect: its tail. The largest error over sixteen thousand queries was 6,001 against Count-Min’s 1,971, because a median of four can be dragged by two unlucky rows while a minimum of four is protected by one lucky one.

This is the same shape as the result the previous phase found for Misra-Gries — the structure with the reputation for sophistication is not automatically the accurate one, and the comparison has to be made at equal bits on the question both are built for. Here the sophisticated one does win, and it wins by changing which norm the error is measured against rather than by being cleverer with the same one.

Where the two bounds actually bite #

Both structures come with a published guarantee and both guarantees are far above what happens.

Count-Min’s is $\varepsilon \lVert f \rVert_1$ with $\varepsilon = e/w$, holding with probability $1 - e^{-d}$. At $w = 64$ and $d = 4$ that is an error of at most 2,548 with probability 98.2%. The measured mean absolute error is 325 and the worst of sixteen thousand queries is 1,971 — inside the bound, at an eighth of it typically, and with no breach at all where 1.8% were permitted. That is the same loose-and-correct bound the previous phase measured, and it is loose for the same reason: the bound is about the worst arrangement of colliding mass and the arrangement at hand is not the worst.

Count-Sketch’s is stated against $\lVert f \rVert_2$, and which $\lVert f \rVert_2$ matters enormously. The whole vector gives 12,409, so a per-row standard deviation of $12{,}409/\sqrt{64} = 1{,}551$; but the norm is dominated by a handful of keys, and a query only suffers from a heavy key when that key lands in the same column, which happens one time in $w$.

The measured mean absolute error is 181, which sits between the fourth row and the third. That is the right reading: a typical query collides with none of the head, so its error is governed by the residual after the head has been removed, and the head only appears in the rare rows where it lands on top of the query. The bound quotes the first row of that table and the behaviour lives in the last two, and the gap between them is not a defect in the bound — it is the difference between a statement about every query and a statement about most of them.

More rows is worse, at a fixed budget #

A second measurement, and it is the one most likely to change what somebody does.

Holding the bits fixed at about 8,160 and dividing them between rows and columns:

Both structures get worse as rows are added. The reason is arithmetic: the error in a cell falls like $1/w$ for Count-Min and $1/\sqrt{w}$ for Count-Sketch, and adding rows at a fixed budget shrinks $w$ proportionally. Depth buys a failure probability — the chance that every row is unlucky — and width buys accuracy, and at a fixed number of bits the two are in direct competition.

The published advice is usually $d = \lceil \ln(1/\delta) \rceil$, which for a one-in-fifty failure probability is four. That is the right rule when $\delta$ is what matters. When the mean error is what matters, three rows and a wide table beat nine rows and a narrow one by a factor of three and a half on this stream.

What is actually lost #

The one-sidedness is not a decoration and losing it costs three specific things.

An estimate stops being a bound. “This key occurred at most 4,300 times” is a sentence a Count-Min sketch can say and a Count-Sketch cannot. Anywhere the answer feeds a decision that must not under-count — a rate limiter, a quota, an admission control — the one-sided structure is answering the question that was asked and the two-sided one is not.

Filtering becomes probabilistic. A heavy-hitter routine built on Count-Min can discard a key the moment its estimate falls below the threshold, because the estimate is an upper bound and a key below it is genuinely below it. With Count-Sketch that discard is a coin flip near the boundary.

The composition changes. Count-Min estimates can be added, subtracted and compared with confidence about the direction of the resulting error; Count-Sketch estimates cannot, and a chain of them accumulates variance rather than a bias in a known direction.

Against that: 2.69 times the accuracy at equal bits, an unbiased answer that can be averaged over repetitions, a second question — $F_2$ — answered by the same table, and validity in a model where the other structure has no theorem at all. Which of those matters is a property of the application and not of the sketch.

The rare key is hopeless either way #

Both structures answer well about heavy keys and neither answers usefully about light ones, and the arithmetic makes that unavoidable rather than fixable.

This stream has 136 keys that occurred exactly once. Count-Min’s mean absolute error on the light keys is 314.9 and Count-Sketch’s is 156.0, so the answers are “about 315” and “about ±156” for a true answer of one. In relative terms those are 31,000% and 15,600% wrong, and halving a number like that changes nothing about what can be done with it.

The reason is structural. Both errors are a fraction of a norm of the whole vector, and neither norm knows anything about the key being queried. A structure whose error is a fixed number of counts is useful exactly for keys whose counts are much larger than that number, and the set of such keys is what “heavy hitter” means. Anybody wanting per-key accuracy for rare keys is asking for a structure whose state grows with the number of distinct keys, which is the exact counter table and costs 92,184 bits here.

This is worth saying plainly because the two structures’ relative merits are often argued about as though a better one would answer both. Neither does, the improvement measured above is real and is confined to keys where the answer was already usable, and the honest summary is that Count-Sketch moves the threshold at which a key becomes answerable down by a factor of about 2.7.

Why a median and not a mean #

Averaging the $d$ rows would also be unbiased and would have lower variance than any single row. The median is used instead, and the reason is the tail rather than the centre.

A row’s error is a signed sum of colliding counts. Occasionally a heavy key collides with the queried key and that row’s error is enormous — not a small perturbation but a term of size $f_{\text{heavy}}$. An average includes that term with weight $1/d$; a median discards it entirely, provided fewer than half the rows are affected. Since a given heavy key collides with the query in each row independently with probability $1/w$, the chance that it lands on more than half the rows is astronomically small.

So the median is doing the same job it does in the median-of-means construction: converting a bound on a typical error into a bound on the failure probability, by requiring a majority of independent things to go wrong at once.

The general turnstile model is where the one-sidedness stops being free, and it is worth drawing because nothing about the structure changes: the same tables, the same bits, the same queries.

Squeezing the table the other way makes the same point from the opposite end. A narrow table piles more keys into every cell, so the collision term grows and the sign is what decides whether it adds or cancels.

What the sign costs to compute #

The signed sketch evaluates two hash functions per row rather than one — a position and a sign — so its work per arrival is double at the same shape. On the measurements above that is eight evaluations per item against four.

Two things make it less than it sounds. The sign needs only one bit, so it can be taken from a spare bit of a wider hash rather than from a second function; and the degree required is two rather than four, because the variance being bounded here is that of a sum over the keys in one column rather than over the whole stream. Implementations that take the sign from the high bit of the same multiply that produced the column are exactly as accurate on the streams measured here, and this file keeps them separate because a shared source is one more thing whose independence would have to be argued rather than assumed.

The comparison worth carrying is the one from the previous essay’s accounting: the plain tug-of-war construction shows every arrival to every register, at 640 evaluations an item for its largest setting. A Count-Sketch of the same 20,480 bits shows each arrival to five, and answers per-key questions the other cannot. That is what hashing to a column rather than broadcasting buys, and it is why the plain estimator is a teaching device and the table is what runs.

A bias does not average out and a variance does #

The unbiasedness is listed above as one item among four, and it has a consequence large enough to decide which structure a system should hold when the answers are going to be combined rather than read one at a time.

Ask both structures about two hundred keys and add the answers up. Count-Min is high by about 300 on each, in the same direction every time, so the total is high by about 60,000 — the biases add. Count-Sketch is off by about 180 on each with a sign that is as likely one way as the other, so the errors partly cancel and the total is off by about $180\sqrt{200} \approx 2{,}500$. A factor of twenty-four, on a quantity neither structure was asked about directly.

That matters because aggregates over many estimates are extremely common and rarely recognised as a different question. Summing the estimated counts of a group of keys; computing an entropy or a Gini coefficient from estimated frequencies; taking a weighted average; reporting what share of traffic a category accounts for — every one of those adds up many per-key answers, and every one of them turns a one-sided error into a systematic error that grows linearly in the number of terms.

The general rule is worth stating in that form. A bias survives averaging and a variance does not, so a structure whose error is one-sided is the right one for a single question with a direction attached and the wrong one for a sum. Count-Min’s over-estimate is a feature when the caller wants “at most”, and it is the whole of the error when the caller wants a total.

And it runs the other way for repetitions of the same query. Independent Count-Sketch tables over the same stream can be averaged, and their answers converge on the truth as $1/\sqrt{r}$; independent Count-Min tables averaged converge on the truth plus the bias, and no amount of repetition removes it. What Count-Min does with repetition is take a minimum, which sharpens the bound and does not remove the direction.

The repair that trades the property the last section is about #

There is a change to Count-Min that recovers much of the accuracy gap, keeps the one-sidedness, and gives up the thing the next section says is the important one. Having all three facts together is what makes it a decision rather than an improvement.

Conservative updating. On an arrival, instead of incrementing all $d$ cells, compute their current minimum and increment only the cells that are at it. The estimate is still an upper bound — the minimum still contains the key’s own count plus a non-negative pile — and the piles grow more slowly, because a cell that is already large stops accumulating.

It is a real improvement and it is cheap: one extra pass over the same $d$ cells that were being touched anyway.

What it costs is linearity. The update rule now depends on the table’s current contents, so the state is no longer a function of the net frequency vector alone — two sequences of updates with the same sum produce different tables. And with linearity go all three of its consequences: the sketches cannot be merged by adding them, the structure has no meaning in a turnstile model where updates may be negative, and the table built on a stream is not the table built on its shuffle.

So the three-way choice is:

Each row gives up exactly one of the three, and there is no row that has all of them. That is the shape this collection keeps finding when a structure looks strictly better than another — the improvement is real and it is paid for on an axis the comparison was not measuring.

The property that survives every model #

There is one thing both structures have that this essay has not used, and the next essay is entirely about it.

Both are linear. Their state is the sum of the updates applied to it, so the table after a sequence of updates is a function of the net frequency vector and of nothing else — not of the order, not of the number of updates, not of how much was inserted and then taken away. That is what makes them mergeable, and it is what makes them work when updates are allowed to be negative.

Count-Min’s one-sidedness does not survive that generalisation and its linearity does. Count-Sketch’s guarantee, which was never about a direction, survives intact. Which is a strange sort of advantage: the structure that promised less has less to lose.