The counter that takes the smallest slot

Misra-Gries answers a heavy-hitter query with a number that is never above the truth. Count-Min answers with one that is never below it. Both are useful and both are one-sided, and this collection has measured both.

There is a third counter-based structure that keeps two numbers per key, and the pair brackets the truth from both sides.

Space-Saving, from Metwally, Agrawal and El Abbadi in 2005, works like this. Keep $k$ counters, always full once $k$ distinct keys have arrived. A key already in the table is incremented. A key that is not present takes the slot of the smallest counter — and it keeps that counter’s value and adds one to it. The value it inherited is written down beside it as that key’s error, because everything up to it belonged to somebody else.

So the structure holds, for each key, a count and an amount of that count it is not sure about. The true frequency is between count − error and count, always.

The bracket is empty where the answers are #

The first surprise is on that plate and it is worth stating on its own: the structure is exact on precisely the keys anybody asks it about.

A key’s bracket is the value it inherited when it last took a slot. A key that has been in the table since before the table filled inherited nothing, so its bracket is zero and its counter is its true count. And the keys that were there from the beginning are, on any skewed stream, the heavy ones.

At sixteen thousand bits over sixty thousand arrivals of a Zipf stream, Space-Saving is exact on nineteen of the twenty heaviest keys and off by one on the twentieth. The bracket at the bottom of the table is 937 wide.

The published guarantee is weaker than this and is the same guarantee for every key: no reported count is below the truth, and no reported count exceeds the truth by more than $n/k$. That bound is tight only at the bottom of the table. What the structure knows, key by key, is much more precise than what the bound says — and the second number per key is where it is written down.

What that costs, and what it buys #

Three counters’ worth of state per key rather than two: a key, a count, and an error. Ninety-six bits against Misra-Gries’s sixty-four, so at a fixed budget Space-Saving holds two-thirds as many keys.

Measured at three budgets on the same stream, against exact counts from a referee neither structure can reach — mean absolute error on the twenty heaviest keys:

Space-Saving wins at every budget and the margin grows: at the largest it is a thousand times more accurate than either, while holding fewer keys than one of them and a quarter as many cells as the other.

That is a large enough gap to be suspicious of, and the resolution is the next essay’s subject. The short version is that it is not a better structure. Space-Saving with $k$ counters holds exactly the state Misra-Gries with $k-1$ holds, shifted up by a single number. The difference in the table above is entirely in which end of the bracket each structure reports.

The reversal #

Which makes a prediction that can be checked, and it is the check that makes the comparison honest rather than flattering.

If the only difference is which end of an interval is reported, then Space-Saving must be worse wherever the truth sits at the lower end — that is, on the light keys, where a slot has changed hands recently and the inherited count is most of what the counter holds.

The reversal happens at about rank one hundred, and it is exactly where the argument says it should be: above it the truth is near the top of the bracket and below it the truth is near the bottom. Count-Min is worse than both everywhere, and its error is flat across the bands, because its error is a fraction of the whole stream rather than a property of the key.

The right way to read the table is not that one structure is better. It is that one piece of state supports two reporting rules, that they are optimal on different parts of the distribution, and that the structure holding both numbers is the one that could choose — which is what the bracket is for and what neither of the other two has.

The bound, and what the structure actually knows #

The published guarantee says the overshoot is at most $n/k$. The smallest counter is what the overshoot actually is. Those are different numbers and the gap between them is worth measuring, because the first is what a reader is told and the second is what the structure could report.

Two things in the last two columns. The worst overshoot equals the smallest counter exactly, at every size — which is not a coincidence but a restatement of the eviction rule, since the largest inheritance any key can be carrying is the largest value the smallest slot has ever held, and that is the current smallest counter. And the mean overshoot across the whole table is about two-thirds of it, because most keys took their slot when the smallest counter was smaller than it is now.

The bound is between 1.4 and 1.9 times the truth here, which is a good bound as bounds go. What matters is that it is a bound about the structure and the bracket is a fact about the key — and the second is available for free, at query time, from a number the structure is already storing.

This is the same shape as the constant the notation drops with the roles reversed. There, the class was honest and the constant was hidden. Here the bound is honest and it is being quoted in place of something the implementation can compute exactly.

The smallest counter is the whole story #

One number decides everything about this structure: the value of its smallest counter. It is the width of every bracket, it is the worst overshoot, it is what a newcomer inherits, and it is the threshold below which a key cannot be distinguished from noise.

It grows roughly linearly in the stream on a stationary source, which means the structure’s uncertainty grows without limit as the stream runs, at a rate of about one per $k$ arrivals. That is not a defect — it is the price of a fixed-size structure over an unbounded stream, and Misra-Gries’s shortfall does exactly the same thing — but it has a consequence worth stating: the useful lifetime of a Space-Saving table is bounded by how large the smallest counter is allowed to get relative to the threshold being asked about.

At $k = 170$ and a threshold of one per cent, the bracket reaches the threshold at about a million arrivals. Past that, every answer the structure gives about that threshold is cannot tell.

Where the eviction rule comes from #

The rule — take the smallest slot, inherit its count — looks arbitrary and is forced.

Suppose a new key took a slot and started from zero. Then the structure would be underestimating that key by however much it had already arrived before taking the slot, with no bound on the amount, and the guarantee that no count is below the truth would be gone. Suppose instead the new key evicted a random slot. Then a heavy key could be evicted while a light one survives, and the guarantee that every key above $n/k$ is in the table would be gone.

Inheriting the smallest count is the unique choice that keeps both. The evicted key’s count was the smallest, so it was at most $n/k$; the new key’s true count is at least one; and the inherited value is an upper bound on what the new key might already have accumulated unnoticed, because anything arriving more often than the smallest counter would itself be in the table.

What the third number is for #

There is a use for the bracket that neither of the other structures can offer, and it is the reason to pay the extra thirty-two bits.

A query can come back with a decision rather than an estimate. Asked whether a key is above a threshold $\phi n$, the structure answers yes when the lower bracket is above it, no when the counter is below it, and cannot tell in between. The third answer is the useful one: it is the only one of the three structures that can say so, and the width of the uncertain band is the smallest counter, which is a number the structure knows exactly at query time rather than a bound derived from $n$ and $k$.

On the stream above with $k = 170$, the smallest counter is 187 and the stream is sixty thousand, so at $\phi = 0.01$ — a threshold of six hundred — the uncertain band is a third of the threshold. At $\phi = 0.005$ it is more than half. A structure that reports “cannot tell” on a third of the range around the threshold is more useful than one that reports a number and lets the reader believe it, and that is the whole argument for the third column.

Two structures, one comparison, and a caution about it #

The table of error bands above compares three structures at a fixed number of bits, and it is worth being explicit about what that comparison does and does not settle, because “at equal bits” is a phrase that can hide a lot.

The three structures hold different numbers of things at the same budget: 170 keys with brackets, 256 keys without, and 512 counter cells with no keys at all. Choosing bits as the common axis is a choice, and it is the right one for this collection — state in bits is the unit this field has used since it opened — but it is not the only reasonable one. Compared per counter, Count-Min looks much better and Space-Saving much worse; compared per hash evaluation, Count-Min does four per arrival and the other two do none.

And there is a subtler asymmetry. Space-Saving and Misra-Gries can only answer about keys they hold, so their error on a key that was evicted is the key’s whole count; Count-Min answers about any key at all. The bands above are computed over keys ranked by their true frequency, so the light bands include keys the counter-based structures have never heard of and Count-Min has an estimate for. That is why Count-Min’s error is flat and the others’ fall: the three are not answering the same question at the bottom of the distribution, and a table that did not say so would be comparing a structure that abstains with one that guesses.

The midpoint halves the worst case, for nothing #

The reversal is presented above as a reason to keep both reporting rules and choose between them. There is a third rule that needs no choosing and is better than either in the one respect a bound cares about.

Report the midpoint of the bracket. The truth is somewhere inside, so the error of the midpoint is at most half the bracket’s width — and the error of either endpoint is, in the worst case, the whole width. So reporting the middle halves the worst-case error for every key simultaneously, at the cost of one subtraction and one shift at query time.

That is not a marginal improvement in the way a constant usually is, because of where the two endpoints are wrong. Space-Saving’s counter is exactly right at the top of the distribution and maximally wrong at the bottom; Misra-Gries’s lower end is the reverse. The midpoint is never exactly right and never maximally wrong, which for a structure whose output is going to be read by something that does not know which band a key is in is the safer position.

The reason it is not the standard rule is worth stating rather than glossing, because it is a real objection. Both endpoints are one-sided, and one-sidedness is a property some callers need: a filter that must never discard a genuine heavy hitter wants the upper end, and one that must never raise a false alarm wants the lower. The midpoint is two-sided and gives up both, so it is the right rule exactly when the output is an estimate to be read and the wrong one when the output is a decision to be acted on.

Which is the same division this collection keeps arriving at — an estimate and a guarantee are different products — and here, unusually, the structure holds enough to supply all three from one table.

Sizing for a decision rather than for a count #

The threshold reading above says the structure answers yes, no or cannot tell, and that the uncertain band is as wide as the smallest counter. That turns sizing into arithmetic, and the arithmetic gives a number several times larger than the usual rule.

The smallest counter is about $n/k$. To ask about a threshold of $\phi n$ and have the uncertain band be a fraction $\beta$ of it:

$$\frac{n}{k} \;\le\; \beta \phi n \qquad\Longrightarrow\qquad k \;\ge\; \frac{1}{\beta\phi}$$

The familiar rule of thumb is $k \approx 1/\phi$ — ninety-nine counters to catch everything above one per cent — and that is the value at which the uncertain band is as wide as the threshold itself, which is to say the structure can never answer anything but cannot tell near the boundary. To get the band down to a tenth of the threshold takes ten times as many counters: a thousand, not a hundred.

So the standard sizing rule sizes for the guarantee and not for the answer, and the two differ by whatever resolution somebody actually wants at the threshold. That is the same relationship this collection found between a sketch’s width and the question it is being asked — what fraction of the stream is the smallest thing worth being right about — and the resolution is the parameter neither structure’s usual account contains.

It also gives the honest lifetime figure. The band grows at about one per $k$ arrivals, so a table sized for a resolution $\beta$ at threshold $\phi$ delivers it until the stream reaches whatever length made $n/k$ equal to $\beta\phi n$ — which is to say never expires, because both sides scale with $n$. The lifetime worry raised above applies to an absolute threshold, not a proportional one, and the two cases want different answers: a proportional threshold is stable forever and an absolute one has a shelf life.

What is not measured here #

Ordering. Space-Saving is usually recommended for top-$k$ rather than for point queries, and the quantity that matters there is whether the reported ordering is right rather than whether the counts are. The measurements above are all point errors. The ordering on this stream is correct in the top twenty and it would be a different essay to establish where it stops being.

The stream shapes that break it. On a uniform stream there are no heavy hitters, every arrival evicts somebody, and the whole table churns — the brackets are then the full width of the smallest counter on every key, and the structure reports $k$ arbitrary keys with equal confidence. That case is measured in the essay that introduced Misra-Gries and it applies here identically, because the two structures are the same one.

A merge. Two Space-Saving tables can be combined, and the rule is the same subtraction the next essay is about, applied twice. It is not measured here, and the reason is that the merged structure’s bracket is the sum of the two smallest counters rather than either of them — which makes merging strictly worse than building over the concatenation, exactly as it is for Misra-Gries and exactly as it is not for Count-Min.

Deletions. Every structure in this family assumes each update adds. Under a model where counts can decrease, as the turnstile essay measures, the eviction rule has no meaning — there is no smallest counter to inherit from when counters can go down — and none of the guarantees above survives.