The count that outlives its arrivals

Take a stream of forty thousand arrivals in which one key takes about a third of the first half and then never appears again. Run a Misra-Gries summary with sixty-four counters over it, and at the end ask what the heaviest key is.

It says key 1, with a count of 6,039.

Key 1 has zero arrivals in the last four thousand. It has zero arrivals in the last twenty thousand. It is the largest number the structure holds, it is in first place, and it will stay there for as long as the stream runs.

This is not staleness. A stale answer is one that was right recently. This is an answer that has been wrong for half the stream, is wrong by every amount there is to be wrong by, and carries nothing that could indicate it.

Why a counter cannot be run backwards #

The mechanism is worth stating precisely, because “it does not expire” makes it sound like an omission that could be repaired with a timestamp.

A Misra-Gries counter is not a tally of arrivals. It is a number that has been incremented when its key arrived and decremented whenever some other key arrived and found the table full. Both operations happened at unrecorded times, and the counter is their net. Six thousand and thirty-nine is what is left of some larger number after some quantity of decrements — the structure does not know which number, and it does not know how many.

So there is no operation that removes the contribution of the arrivals that have left. To subtract them, the structure would have to know which of its increments were theirs, and that information was destroyed the moment the counters were merged into one integer. The same property that makes the summary small is the one that makes it impossible to window.

The comparison with the previous two essays is exact and it goes the other way. A cardinality estimator’s register also holds a value with no record of when it was set, and there the repair is to keep more: a list of the arrivals that could still matter. Here the equivalent list would be every arrival, because any of the six thousand increments might be the one leaving next, and a structure keeping every arrival is the ring buffer rather than a summary.

What the structures actually say #

Three structures, one moment, and the same question.

The clockless summary’s first two rows are the interesting ones. Key 1 at 6,039 with nothing in the window; then the natural head of the distribution, which is genuinely heavy, at a count several times what it really is over the window — because that count is about forty thousand arrivals and the question was about four thousand.

Both errors are the same error and only one of them is visible. The count is over the wrong interval. On the departed key that produces a number about a key that is not there; on the surviving key it produces a number that is roughly ten times too large. A reader looking only at the ordering would notice nothing wrong with the second and everything wrong with the first, and the structure is doing exactly the same thing in both cases.

Blocks, because there is nothing else #

If a counter cannot be windowed, the counters have to be replaced often enough that expiry becomes a matter of throwing whole tables away.

Cut the window into $b$ blocks of $W/b$ arrivals each. Every block gets its own summary. A block whose last arrival has left the window is dropped entire, and a query merges what remains. Merging Misra-Gries summaries is a thing this collection has already had to be careful about — the merge is not the sum — but merging disjoint stretches of one stream is the easy case, because no key is double-counted.

The cost is two things and they are worth separating.

A factor of $b$ in space, because $b$ tables of $k$ counters is $b$ times one table of $k$. That is the obvious half.

And slack, which is not obvious and does not go away. The oldest surviving block began before the window did. Some of its arrivals are inside the window and some are outside, and the block has no record of which — the counters are integers again, and the whole argument above applies within the block. So the merged answer is about somewhere between $W$ and $W + W/b$ arrivals, and the structure cannot say which.

That second error is the same quantity an exponential histogram charges for its oldest bucket, arriving in a structure that keeps keys rather than bits. The difference is what happens as the structure grows: a histogram’s oldest bucket is a shrinking share of its total as more buckets are allowed, so raising the accuracy shrinks the uncertainty directly. A block’s slack is $W/b$ and shrinks only by adding whole summaries.

Measured, at four settings #

At one block the structure is barely a windowed structure at all: it is a summary over the last $W$ arrivals plus everything that has arrived since the block began, so the answer can be about twice the window that was asked for, and the error is what that produces. At sixteen blocks it is within two per cent — and it holds more bits than the ring buffer, which is 131,072 and exact.

That is the honest summary of the whole approach, and it is a poor showing. A windowed heavy-hitter structure built out of counters costs about what keeping the arrivals costs, at the accuracies where it is worth having, and the reason is not the counters: it is that $b$ tables of $k$ counters at 64 bits each add up quickly, while a window of four thousand 32-bit keys is a fixed 131,072 whatever the accuracy.

The blocked structure wins on space only where the window is long relative to how many distinct keys are heavy in it — which is exactly where the counter-based approach was always meant to be used, and is a condition that is easy to state and easy not to check.

When the blocked structure is worth building #

The table above is one configuration and it would be easy to read it as a verdict. The arithmetic is small enough to do in general, and it says something more useful than “counters lose”.

The ring buffer costs $W \cdot \lceil \log_2 u \rceil$ bits — the window length times the width of a key — and nothing else, at any accuracy, for ever. The blocked summary costs $b \cdot k \cdot (\lceil \log_2 u \rceil + c)$ where $c$ is a counter’s width. Setting them equal and cancelling the key width gives the crossing:

$$b \, k \left(1 + \frac{c}{\log_2 u}\right) < W$$

At 32-bit keys and 32-bit counters that is $2bk < W$. Eight blocks of sixty-four counters is $1{,}024$, so the blocked structure is smaller than the buffer only for windows past about a thousand — and the measurements above use $W = 4{,}096$ with $k = 128$, which is $2{,}048$ against $4{,}096$, a saving of less than two.

So the counter-based approach pays where the window is long and the number of heavy keys in it is small, and the ratio between those two quantities is the whole of it. A window of a million arrivals with fifty heavy keys is a factor of five thousand and the summary is obviously right; a window of four thousand with a hundred and twenty-eight counters is a factor of sixteen before the counters’ own width is charged, and it is not.

Nothing in the literature on these structures is wrong about that. What is easy to miss is that the comparison is against the window, not against the universe — the intuition that a summary beats keeping everything comes from the cash-register model, where “everything” is unbounded, and over a window it is $W$.

The threshold moved, and it is not the same question #

One more thing changes when a heavy-hitter question is asked about a window, and it is easy to miss because the notation does not change.

“Heavy hitter” means a key whose count is at least $\phi$ of the stream. Over a window the denominator is $W$ rather than $n$, so the same $\phi$ names a much smaller absolute count — at $\phi = 0.01$ and $n = 40{,}000$ that is four hundred arrivals, and over a window of four thousand it is forty.

Forty is inside the noise of every structure above. The blocked summary’s shortfall at eight blocks of sixty-four counters is up to $512/65 \approx 8$ per block and up to sixty-three in total; its slack is up to five hundred and twelve arrivals of a key that may or may not be the one asked about. The threshold and the error bar are the same size.

That is not an argument against windowed heavy hitters; it is an argument that $k$ has to be chosen against $W$ rather than against $n$, and the rule $k > 1/\phi$ has to be applied per block rather than to the structure. Eight blocks each needing a hundred counters is eight hundred, which is where the crossing arithmetic above puts the structure firmly behind the ring buffer for this window length. Both facts are consequences of the same substitution and neither is visible in a bound written in $\phi$.

The two errors do not add, and neither dominates #

It is tempting to treat the slack as a small correction on top of the summary’s shortfall. It is not, and the two behave differently enough that a single error bar would be misleading.

The shortfall is a property of $k$: every key’s reported count is below its true count by at most the number of decrements, which the summary bounds by (arrivals in the block) over $k+1$. It is one-sided — the structure never overstates a key within a block — and it is bounded by something the structure knows.

The slack is a property of $b$, and it is one-sided the other way: arrivals outside the window are counted in, so a key that was heavy just before the window opened is overstated. On a stationary stream the two roughly cancel and the merged answer is close. On a stream where something is changing — which is the only kind of stream a window is for — they do not cancel, and which one dominates depends on whether the key in question is rising or falling.

What a stamp per block buys #

The blocked structure is the one place in this group where knowing the time is nearly free: one stamp per block rather than per key, 117 bits out of 18,549 in the default configuration.

Coarseness is what makes it cheap, and the slack is what coarseness costs. That is the whole trade and it generalises past this structure: how finely does the summary need to know when things happened, and what does it give up by knowing less? A ring buffer knows to the arrival and pays with the arrivals. A stamp per key knows to the arrival and pays a clock per key. A block knows to the block and pays with an answer about the wrong number of arrivals.

There is no fourth option in which the structure knows coarsely and answers precisely, and the reason is the floor under a window: an exact answer over the last $W$ arrivals needs enough states to distinguish all of them, and every reduction in what is remembered about when is a reduction in how many windows can be told apart.

A stamp per counter fixes the headline and not the counts #

The failure this essay opens with — a key with nothing in the window reported as the heaviest thing in it — is the worst thing the structure does and it is separable from everything else. It is also cheap to remove.

Give each counter one more field: the position of the last arrival that incremented it. That is one stamp per counter rather than per arrival, so at sixty-four counters and a window of four thousand it is $64 \times 13 = 832$ bits — five per cent on top of the 16,410 the clockless summary already holds.

With it, a query can drop or flag any counter whose last increment is outside the window. Key 1 has not been incremented for twenty thousand arrivals, so its stamp is far outside, and the structure can say this key has nothing in the window — which is exactly the sentence it currently cannot form.

What the stamp does not do is fix the counts. A counter that was last incremented inside the window is holding a number about the whole stream, and knowing when it was last touched says nothing about how much of it is recent. The surviving heavy key in the table above, reported at roughly ten times its window count, is unaffected: its stamp is current and its number is still about forty thousand arrivals.

So the repair separates the two errors cleanly, and it is worth having precisely because they are different in kind. A key that is absent from the window is a categorical error and a key whose count is ten times too large is a quantitative one, and only the first can be fixed without the block decomposition. An implementation that added the stamp would go from reporting a phantom at the top of its table to reporting the right keys with the wrong numbers, which is a considerable improvement in exchange for five per cent.

It is also the cheapest instance of this collection’s recurring repair: the structure holds enough to say something about what it does not know, and the interface has nowhere to put it.

The blocks answer a question the window does not #

The blocked structure is built to answer what is heavy in the last $W$ arrivals, and having built it, a second question becomes available for nothing — and it is usually the one somebody actually wants.

The blocks are summaries of disjoint, consecutive stretches. So the difference between the newest block’s counts and the oldest’s is an estimate of what is rising, and comparing any two blocks gives a rate of change over the interval between them. No extra state, no extra pass, and no new structure: the arithmetic is a subtraction over tables that already exist.

That matters because “which keys are heavy” is rarely the operational question. A monitoring system knows which endpoints are busy; what it wants to know is which endpoint got busy in the last five minutes, which is a difference rather than a level. A structure reporting levels forces the difference to be computed by storing yesterday’s answer and subtracting, which works and requires somebody to have decided to store it.

Two cautions, and both follow from the shortfall being one-sided. Each block’s counts are under their truths by up to its own shortfall, so a difference of two blocks has an error of up to the sum of two shortfalls and can go either way — the level estimates are one-sided and the difference is not. And a key present in one block’s table and absent from the other’s has an unknown count on one side, so the difference is a lower bound rather than an estimate.

Neither prevents the comparison from being useful for ranking the risers, which is what an alert wants. It is the same distinction the level-versus-difference reading makes about a frequency sketch: a structure whose errors are stable across two readings is a better instrument for change than for magnitude, and here the stability comes from the blocks being separate rather than from the hashes being fixed.

What is not measured here #

Space-Saving in the blocks. The blocks above hold Misra-Gries tables, and the next two essays show that the obvious alternative is the same structure read differently, so nothing about the slack or the state would move. What would move is which direction the within-block error goes, and a blocked structure whose within-block error is one-sided upwards would compound with the slack rather than partly cancel it. That is a real difference and it is not drawn.

The λ-counting approach. There is a family of windowed heavy-hitter structures that keep a decaying count rather than a windowed one — every arrival multiplies the existing counts by a factor slightly under one — which answers a related but different question and has no $W$ in it at all. It is not a sliding window and it is not compared here.

Deletions. Everything above is a window over an insert-only stream. In a model where updates can be negative, as the turnstile essay sets out, a windowed count means something else again, and none of these structures is valid in it.

The structure at the top of this page is not defective. It is a correct summary of a stream, being asked about a window, and answering the question it was built for. What is missing is anything in its output that says which question that was.