Two structures that are one

Run two structures side by side over the same stream.

The first is a Space-Saving summary with sixteen counters. Watch its smallest counter — the number a new key inherits when it takes a slot.

The second is a Misra-Gries summary with fifteen counters. Watch the total it has decremented away — the sum of everything subtracted from its counters over the whole run.

There is no obvious reason for these to be related. They are bookkeeping quantities inside two different algorithms, published seventeen years apart, one of them a running minimum over a table and the other a running total of an operation the first structure does not perform.

They are equal. Not approximately, not asymptotically, and not merely at the end: at every one of twenty thousand prefixes, and at every table size tried.

The conversion is a subtraction #

The full statement is stronger than the equality of those two numbers, and it is the thing worth carrying away.

Take a Space-Saving summary with $k$ counters. Subtract its smallest counter from every one of them and delete the keys whose result is zero. What remains is exactly the Misra-Gries summary with $k-1$ counters over the same stream.

Checked at every prefix rather than at the end, because a claim that holds only at the end is a claim about one number and this one is about a state:

The result is due to Agarwal, Cormode, Huang, Phillips, Wei and Yi, in a 2012 paper about merging summaries, where it appears as a lemma on the way to something else. It is not obscure and it is not what these structures are usually taught with.

Why the mechanisms look different #

The two update rules are written in vocabularies that share nothing.

Misra-Gries. A key already present is incremented. A key that is absent, when there is a free slot, takes it. A key that is absent when the table is full causes every counter to be decremented by one, and is itself discarded.

Space-Saving. A key already present is incremented. A key that is absent, when the table is full, evicts the smallest counter’s key, takes the slot, and inherits the count.

One decrements globally and throws the arrival away. The other evicts locally and keeps the arrival. They do not look like the same operation and, taken literally on the stored numbers, they are not.

They are the same operation on the numbers relative to the smallest. A global decrement lowers every counter by one and lowers the minimum by one, so it changes no difference between a counter and the minimum — except for the counter that was at the minimum, which falls to zero and is deleted, freeing a slot. An eviction removes the key at the minimum and puts the new key there at exactly the minimum, so relative to the minimum the new key is at zero and every other counter is unchanged. Both rules, read relatively, do the same two things: retire the key at the bottom, and admit the new one at the bottom.

The one asymmetry is the slot count, and it is the source of the $k-1$.

Ten arrivals, done by hand #

The identity is small enough to watch happen. Three Space-Saving counters against two Misra-Gries counters, on the stream 1, 2, 1, 3, 4, 1, 2, 5, 1, 6.

Row four is where the structures first do something different and it is the row to look at. Key 3 arrives; Space-Saving’s table is full, so 3 takes the minimum slot, which held key 2 at 1, and becomes 3:1. Misra-Gries’s table is full, so every counter falls by one — key 2 hits zero and is deleted, key 1 drops from 2 to 1 — and key 3 is discarded without ever being stored.

The two tables now hold different keys. Key 3 is in one and not the other. And the shifted reading matches anyway, because 3’s count of 1 equals the new minimum and the shift takes it to zero, which is exactly the state of a key Misra-Gries has deleted.

That is the mechanism in one row: Space-Saving stores at the minimum the keys Misra-Gries has just thrown away, which costs it a slot and costs it nothing else. Everything the rest of this essay says is that row, repeated.

The last column is the other half of the identity. The minimum climbs 0, 1, 2, 3 and so does the decrement total, in the same steps, on the same arrivals.

Why one counter fewer #

Space-Saving’s table is always full once $k$ distinct keys have arrived; one of its $k$ counters is always at the minimum, and under the relative reading that counter holds zero. A Misra-Gries table has no such entry, because a counter reaching zero is deleted.

So the relative reading of a $k$-counter Space-Saving table is a Misra-Gries table with at most $k-1$ non-zero entries. Space-Saving spends one slot holding the origin.

That is checkable in the direction that matters — the wrong pairing must fail — and the way it fails is informative:

The agreement lasts exactly until the tables fill, which is when the two update rules first differ at all: before that, both structures are just counting, and every counter is exact. The moment the first eviction happens the readings separate and never rejoin.

That negative half is why the assertion behind this essay is written as a pair. A check that only confirmed the $k-1$ correspondence would be passed by any two structures agreeing on the heavy keys, which these do; requiring the $k$ correspondence to fail is what makes the statement about $k$ rather than about the head of a distribution.

What follows, and it is not nothing #

Once the structures are one, several things that are usually discussed as differences between them stop being differences.

“Which has better accuracy” is not a question about structures. It is a question about which end of an interval to report, and the previous essay measured the answer: the upper end is better above about rank one hundred and the lower end is better below it, on one stream, from one state. There is no configuration in which one structure is more accurate, because there is only one structure.

The two one-sidednesses are the two ends of one bracket. Space-Saving is never below the truth; Misra-Gries is never above it. Both statements are true of the same table, and the width between them is the smallest counter. Presented as properties of rival algorithms they look like a design trade-off; presented as an interval they look like what they are, which is a single quantity the structure knows and reports half of.

The bounds are the same bound. Misra-Gries’s shortfall is at most $n/(k+1)$; Space-Saving’s overshoot is at most $n/k$. Substituting $k \mapsto k-1$ makes the second exactly the first, which is a sanity check the correspondence had to pass and does.

And a merge rule proved for one is a merge rule for the other. That is the use Agarwal and colleagues were making of it: the difficult part of merging these summaries had been done for Misra-Gries and needed doing for Space-Saving, and the lemma made the second free.

How the check is written #

An identity like this is the kind of claim that is easy to assert and easy to assert falsely, so it is worth saying what would have to happen for the assertion behind it to pass while being wrong.

The check runs both structures, converts one, and compares the tables — at every prefix, both keys and counts, sizes included. Three ways it could be vacuous, and what stops each:

It could compare at the end only. Then two structures that converge on the heavy keys would pass, and there are several such pairs. Comparing at every prefix means the check fails the first time a single arrival is handled differently, which on a twenty-thousand-item stream is a strong condition.

It could compare only the counts of keys present in both. Then a structure holding extra keys would pass. The sizes are compared first.

It could be satisfied by any two similar structures. This is the real risk and it is why the wrong pairing is required to fail. Without that clause, an implementation in which the shift was computed from the Misra-Gries side — or one in which both structures were secretly the same object — would sail through.

And one rejection is carried beside it: a conversion performed without the subtraction. Reading Space-Saving’s raw counters as a Misra-Gries table is what a plausible reading of both papers would suggest, and the check requires it to differ, by exactly the minimum.

What is genuinely different #

Three things survive, and it is worth being precise about them because “the same structure” is a claim that invites overreach.

The third counter. Space-Saving stores an error per key — the value it inherited — which Misra-Gries does not. That is real state, thirty-two bits a slot, and it is what makes the per-key bracket available at query time rather than only the global bound. Nothing in the correspondence produces it: the conversion needs only the minimum, and the minimum is one number rather than $k$.

The reporting rule. Which is the whole of the accuracy difference and is not a property of the state.

The work per arrival. Misra-Gries’s decrement touches every counter, so an arrival that misses costs $\Theta(k)$; Space-Saving’s eviction touches one slot plus whatever it costs to find the minimum, which with the right heap is $\Theta(\log k)$ and in the implementation measured here is a linear scan. The stored numbers are the same and the number of operations performed to maintain them is not. This is the second count disagreeing with the first again, and it is the practical reason Space-Saving is the one that gets implemented — a fact that has nothing to do with accuracy and is usually explained in terms of it.

What the third counter is worth, and where #

The error field is listed above as one of three genuine differences, at thirty-two bits a slot, and it is worth pricing rather than noting — because the conversion needs one number and Space-Saving stores $k$ of them, which invites the reading that $k-1$ of them are redundant.

They are not, and the hand-worked table says why. A key’s error field is the minimum at the moment that key entered, not the minimum now. Those are different numbers and the gap between them is the whole value of the field.

Follow key 1 down the ten-arrival table. It enters at the first arrival, when the table is empty and the minimum is zero, so its error is zero and stays zero. By the tenth arrival its counter reads 4 and the table’s minimum has climbed to 3. The global bound therefore permits key 1’s true count to be anywhere from 1 to 4; the error field says it is exactly 4.

That is the pattern rather than a lucky row. A heavy key enters early, when the minimum is small, and is never evicted afterwards — so its error is frozen at whatever the minimum was when the stream was young, while the global floor keeps climbing on everybody else’s behalf. A light key enters late, at the current minimum, and carries the whole of it.

So the thirty-two bits a slot buy a bracket that is tightest exactly where a heavy-hitter query looks. The global floor is the worst case over the table and is carried by the keys nobody asked about; the per-key error is near zero for the top of the distribution and near the floor for the bottom. On the ten-arrival table the difference between the two readings for key 1 is the difference between an interval three wide and an exact answer.

Two consequences worth having.

The identity does not make the extra state redundant. The conversion needs the current minimum because it is converting the table, and a table is a state at an instant. The error fields are a record of the table’s history, which the shift discards, and history is what makes a per-key bracket possible at all. Two structures with the same state can carry different amounts of information about how they got there.

And it explains which structure gets deployed, again. The essay’s third difference — that Misra-Gries pays $\Theta(k)$ per missed arrival and Space-Saving pays $\Theta(\log k)$ — is one practical reason Space-Saving is the implemented one. This is a second, and it is about the answer rather than the work: a count that is never under is a useful guarantee, and never under and provably exact on the keys that matter is a considerably more useful one. Neither is available from the shifted reading, and both come from a field the correspondence has no use for.

Which sharpens rather than weakens the identity. The two structures hold one state; one of them also holds an annotation on it; and the annotation is worth nothing to a merge, nothing to the bound, and a great deal to a query about the top of the distribution — which is exactly what the counter that takes the smallest slot measured when it found the upper reading better above rank one hundred and worse below it.

The shape this is an instance of #

A shared name is not a shared function, and this collection has made a point of it. The reverse case is rarer and is what happened here: two different names, two different pseudocodes, two literatures, and one function.

The thing that hid it is that the difference between the two states is a constant offset, and an offset is invisible in every way these structures are usually looked at. It does not change the ordering, so a top-$k$ comparison shows nothing. It does not change the ratio between counters, so a plot of the distribution shows nothing. It does not change which keys are present, except at the single boundary key. It changes the numbers, which is exactly what a reader compares — and it changes all of them by the same amount, which is exactly what a reader does not check for.

A drifting stream is one way for the table to churn; a bursty one is the other, and it produces the opposite shape. Where drift keeps the minimum climbing steadily because every arrival is a new contender, a burst is one key arriving over and over into a slot it already holds — so nothing is evicted, the minimum does not move, and the correspondence has a flat stretch to be checked on.

Why it stayed hidden for seventeen years #

Misra and Gries published in 1982; Metwally, Agrawal and El Abbadi in 2005; the correspondence in 2012. Two of those gaps are long enough to be worth a sentence about what makes a fact like this hard to notice.

The two papers are about different things. Misra and Gries were solving a decision problem — find the elements occurring more than $n/k$ times — and their structure is a means to it, described in terms of a “candidate set” rather than as a summary anybody would query. Metwally and colleagues were building a system for network monitoring, and their structure is described as a data structure with an API. Neither paper’s abstract is about the object the other paper’s is about, and a reader looking for one would not find the other.

And the empirical route is blocked by the offset. Anybody running both structures on the same stream and comparing them would see two tables of different sizes holding overlapping key sets with systematically different numbers — which reads as “two different approximations”, because that is what two different approximations look like. Seeing the identity requires subtracting a quantity nobody has a reason to compute, and neither structure’s interface exposes it: Space-Saving’s minimum is an implementation detail of its eviction, and Misra-Gries’s decrement total is not stored at all in the usual implementation.

That is worth generalising, because it is the same failure this collection keeps finding in other forms. A relationship that is a constant offset is invisible to every comparison that is scale-free. Ratios, orderings, distributions, plots on log axes: all of them are unchanged by adding the same number to everything, and all of them are what a reader reaches for when comparing two structures. The one comparison that would have shown it — subtract and see if the difference is constant — is the one nobody makes, because there is no reason to expect a constant.

What is not measured here #

The general merge. The correspondence transports Misra-Gries’s merge rule to Space-Saving, and this collection has measured that rule for Misra-Gries only. Whether the transported rule is the one implementations actually use is a question about implementations rather than about the structures.

Weighted updates. Both structures generalise to updates carrying a weight rather than counting one, and the correspondence is stated here for unit updates because that is what is measured. Nothing in the argument obviously requires unit weights and nothing here establishes that it survives them.

Ties. When several counters share the minimum value, which one is evicted is a choice, and the implementation here breaks the tie by key so that a run is reproducible. Misra-Gries’s decrement deletes all of them at once. The correspondence survives it here — a tie means several keys sitting at relative zero, and the shifted reading has none of them either way — but a Space-Saving implementation whose tie-break made a heavy key evictable would not be the same structure any more, and that is a property of the tie-break rather than of either algorithm.