The items that survive k counters

Keep a table of at most $k$ keys, each with a counter.

For each item: if its key is in the table, increment it. If not and there is room, insert it with a count of one. If not and the table is full, decrement every counter in the table and drop any that reach zero.

That is the entire algorithm. It was published by Misra and Gries in 1982, rediscovered twice in the 2000s under other names, and it contains no hash function, no random number and no probability.

Why the decrement rule works #

The counters do not track counts. They track a quantity that is best described as surplus: how far ahead a key is of the general level of everything competing for a slot.

The invariant is that each decrement step throws away $k+1$ occurrences at once — one for the arriving item, which is discarded, and one from each of the $k$ counters. So if there have been $D$ decrement steps over the whole stream, then $D(k+1) \le N$, giving $D \le N/(k+1)$.

Now take any key $x$. Its counter was incremented once for each of its own occurrences that was not thrown away, and decremented at most $D$ times. So

$$f_x - D \;\le\; \hat f_x \;\le\; f_x, \qquad D \le \frac{N}{k+1}.$$

Both halves at once, for every key simultaneously, on every stream. There is no “with probability” anywhere in it and no input that defeats it.

On the stream measured here, with $k = 32$ and $N = 60{,}000$, the bound is 1,818 and the worst shortfall actually suffered by any key is 1,397 — the guarantee is tight to within 30%, which is unusually tight for a bound of this kind and is worth contrasting with what the randomised sketch’s bound turns out to be worth.

The error is one-sided, in the other direction #

Count-Min never returns a count below the truth. Misra-Gries never returns one above it. The two structures answer the same question and are wrong in opposite directions, and that is more useful than it sounds.

An upper bound rules keys out: this sketch says at most 40, so the key is not a heavy hitter. A lower bound rules keys in: this table says at least 3,000, so the key certainly is one. Running both gives an interval, and the interval is exact in the sense that the truth is provably inside it. Neither structure alone provides that.

It also settles an argument about which is “safer” that has no general answer. A monitoring system that must never miss a heavy hitter wants the upper bound; one that must never raise a false alarm wants the lower. Choosing is a statement about which mistake costs more, and it is the same shape of decision as a Bloom filter’s — a filter allowed to be wrong sets it out in the membership setting.

At equal bits, the deterministic one wins #

The field is usually presented with the randomised structures as the powerful ones and the counter table as the simple predecessor. On the question both answer, at equal state, the measurement goes the other way at every size tried.

The comparison has to be set up carefully. Misra-Gries holds $k$ keys and $k$ counters, which at 32 bits each is $64k$ bits. Count-Min holds $d \times w$ counters at 32 bits each. Setting $d = 4$ and $w = 2k$ makes the two the same size, and both are then asked about the ten genuinely most frequent keys.

The bounds go the same way and by more. At 2,048 bits the counter table promises a shortfall of at most 1,818; the sketch promises an over-count of at most 10,194, which on a stream of sixty thousand is 17% of everything that went past.

The reason is not mysterious. Count-Min spends its state on being able to answer about any key, including the 836 keys in this stream that occurred exactly once. Misra-Gries spends all of its state on the keys that survived competition, and answers zero for everything else. When the question is “what were the frequent items”, the second allocation is simply the better one, and the sketch’s generality is being paid for and not used.

What it cannot do #

Three things, and they are why the randomised structure exists.

It cannot be merged into a fixed answer. Two Misra-Gries tables can be combined and the result satisfies the same bound, which is a real and non-obvious theorem — but the merged table is not the table the concatenated stream would have produced. It holds a different set of keys. The summaries that add measures the difference and separates it from the exact mergeability the register-based structures have.

It cannot handle decrements. The invariant counts occurrences thrown away, and an occurrence that is removed from the stream has no meaning in that accounting. There is no turnstile version.

It cannot answer about a key that is not in the table with any precision. It returns zero, and zero is a lower bound and nothing more. For a key that occurred $N/(k+1)$ times — just under the threshold — the answer is zero and the truth is over a thousand. The sketch, for all its looseness, returns a number with the right order of magnitude for such a key, because its error is additive rather than a cliff.

The threshold reading #

The clean way to state what the structure delivers is as a threshold rather than as an accuracy.

Any key occurring more than $N/(k+1)$ times must be in the final table. If it were not, it would have been decremented out, which takes at least as many decrement steps as it had occurrences, which is more than $D$ can be. So setting $k = \lceil 1/\phi \rceil - 1$ guarantees that every key with more than a $\phi$ share of the stream is present.

That is a very strong statement for such a small structure: to catch every key carrying more than 1% of a stream of any length, ninety-nine counters suffice, forever. It comes with the necessary caveat that the table also contains keys that do not qualify — the guarantee is one-directional — so a second pass, or a Count-Min sketch alongside, is needed to say which of the survivors genuinely cleared the bar.

The two-pass version is worth naming because it is what production implementations do and because it steps outside this field’s rules to do it. Pass one finds the candidates; pass two counts them exactly. That is not a streaming algorithm, and its accuracy is not comparable with anything on this page.

Why it is in the structures field #

It sits with heaps and hash tables rather than with the sketches, and the placement is a claim.

Everything else in this phase is a projection: the state is a lossy image of the frequency vector, and the key never appears in it. Misra-Gries keeps keys. Its table is an ordinary associative structure with an eviction policy, its state is legible, and the operations on it are the ones any cache performs. What makes it belong to the streaming field’s argument is the policy — decrement everything rather than evict the smallest — and what makes it belong here is that it is a data structure in the sense the rest of this site uses the word.

The eviction-policy framing is also the clearest way to see why the odd-looking rule is the right one. Evicting the minimum on a miss is the obvious alternative and it has no bound at all: a stream that alternates between two keys with a table of size one evicts on every item and reports nothing, forever. The decrement rule charges the arriving item against every incumbent, so the incumbents pay for their own protection, and the accounting closes.

Both structures are worth drawing once more at a different width, because the whole comparison is a comparison at equal bits and a width is what buys the bits.

What the rule costs per item #

A decrement step touches every counter, so a naive implementation is $O(k)$ in the worst case and the worst case happens on every miss. On a stream with no skew that is $O(k)$ per item, which for $k = 99$ is a hundred operations to process one.

It is avoidable and the fix is worth knowing because it is a nice piece of ordinary data-structure work. Keep the counters grouped by value in a doubly linked list of buckets, so that “decrement everything” is a single operation on the lowest bucket rather than $k$ operations on $k$ counters. Then every step is $O(1)$ and the structure’s per-item cost is a constant, matching Count-Min’s $d$ hashes rather than losing to it by a factor of $k$.

The measurement here does not use that implementation, because the quantity these essays report is state and error rather than time, and the two implementations hold identical state and produce identical answers. What the choice would change is a number this field does not print. It is recorded here so the comparison in the table above is not read as a comparison of speeds, which it is not.

Space-Saving, named and not measured #

There is a close relative that keeps $k$ counters and overestimates rather than underestimates. On a miss with the table full it takes the smallest counter, replaces its key with the arriving one, and increments — so the new key inherits the evicted key’s count as a head start.

That gives an upper bound rather than a lower one, with the same $N/(k+1)$-shaped error, and it has a property Misra-Gries lacks: the table always holds exactly $k$ keys, so the structure degrades more gracefully when the stream has fewer heavy hitters than the table has slots.

It is named here and not implemented, on the same principle the coding field applied to arithmetic coding’s successors: quoting its measured accuracy against numbers produced here by a different structure would be asserting a comparison rather than making one, and the variants differ in exactly the ways that decide such a comparison. What can be said without measuring anything is structural — one gives an upper bound, the other a lower, and the interval between two structures of $k$ counters each is narrower than either alone.

The one counter it does not keep #

The structure can bracket its own answers, exactly, for the price of a single extra integer — and it does not, which is worth pointing out because the omission is universal and the repair is a line of code.

The shortfall for any key is at most $D$, the number of decrement steps performed. $D$ is not a quantity that has to be bounded or estimated: it is a thing the structure does, and counting it costs one increment per decrement step. With it in hand, every answer becomes an interval rather than a number:

$$\hat f_x \;\le\; f_x \;\le\; \hat f_x + D$$

and the truth is provably inside, with no probability attached anywhere.

The interval is a good deal tighter than the guarantee. On the stream measured above with $k = 32$, the bound $N/(k+1)$ is 1,818 and the measured worst shortfall is 1,397 — but $D$ itself is what the structure actually did, which is at most 1,397 and is known exactly rather than bounded. The guarantee is a worst case over streams and $D$ is a measurement of this one, so reporting $D$ converts a promise into a fact, and the fact is always at least as good.

That closes the gap this essay’s comparison leaves open in an uncomfortable place. Count-Min’s number arrives with an additive bound that is a design parameter — 10,194 at the state compared above, and the realised errors are far below it with no way to know by how much. Misra-Gries’s number can arrive with an additive bound computed from the run, and every key’s interval is the same width because the decrements were applied to everything.

It is the same move a quantile summary can make and does not: the structure holds enough to say how much it does not know, and reports a point estimate instead. The difference here is that the accounting is exact rather than approximate, and the cost is one counter.

The order is exact even though the counts are not #

There is a second property hidden in the uniformity of the decrement, and it is the one that matters most for the question the structure is usually asked.

Every decrement step subtracts one from every counter. So two keys that have both been in the table since before the first decrement have both been decremented exactly $D$ times, and their counters differ by exactly what their true counts differ by:

$$\hat f_x - \hat f_y \;=\; f_x - f_y$$

Their relative order is exact, and so is the gap between them. The counts are all wrong by the same amount and a shared error cancels in a difference.

That is a much stronger statement than the bound suggests, and it is the statement a top-$k$ query actually needs. A monitoring system asking which five endpoints are busiest does not need any of the five counts to be right; it needs the ranking, and the ranking of the long-lived incumbents is not approximate at all.

The qualification is the phrase since before the first decrement. A key that entered the table late has missed some of the decrements, so its shortfall is smaller and its counter is closer to the truth than its neighbours’ — which biases it upward relative to them. So a newcomer can outrank an incumbent it has not really overtaken, and the error is one-directional: recent arrivals look better than they are.

That gives the practical reading. The table’s ordering is trustworthy among keys that have been there a while and optimistic about keys that have just appeared, which is exactly the behaviour a reader would want from a structure designed to find persistent heavy hitters and exactly the wrong behaviour for detecting a sudden burst. The structure is a summary of the whole stream, and something looking for a change needs a window rather than a better counter rule.

The measurement that settles it #

The claim this essay is built on — that the deterministic structure is more accurate at equal bits — is exactly the kind that is easy to arrange by choosing the comparison. Three things were fixed in advance to keep it honest.

The state is counted in bits, from the shape of both structures, including the key stored beside each Misra-Gries counter. Leaving the keys out would have halved its apparent cost and won the comparison by bookkeeping.

The question is the one both are designed for: the ten genuinely most frequent keys, taken from the exact truth. Asking about the tail would have won it for Count-Min, which returns a number there, and asking about a single heavy key would have been one sample.

And the direction of each error is reported rather than its magnitude alone, since the two are wrong in opposite ways and an unsigned comparison would hide it.

What the comparison does not show, and is worth stating so the result is not over-read, is anything about streams with no skew. On a uniform stream there are no heavy hitters, the counter table’s contents are arbitrary, and both structures are equally uninformative. The result is about the streams these structures are deployed on, which are skewed, and it holds because skew is what a $k$-counter table is built to exploit.

Nor does it show that the randomised structure was a mistake. Count-Min answers a strictly larger set of questions, merges without loss, survives decrements, and gives an upper bound where this gives a lower one. What the comparison shows is narrower and still worth having: on the one question both are built for, at the same number of bits, the structure with no randomness in it is the more accurate of the two, and its bound is five times tighter. A field that presented the randomised structures as the advance would have that the wrong way round, and the way to find out which it is was to count the bits on both sides and ask them the same question.