The pass that was never a parameter

Every summary in this collection is fed through a wrapper whose second iteration throws. The message names the model rather than the mechanism, because the failure it catches is conceptual: an algorithm allowed a second pass is not a streaming algorithm, and its space bound is a statement about nothing.

That enforcement is right and it has been in place since the field opened. What it is not is a parameter.

Every interesting bound in this area is stated in two quantities — passes and space — because they trade against each other. A restriction fixed at one cannot be swept, cannot be plotted, and cannot be traded. So the wrapper now takes a number: a stream may be read exactly $p$ times, and the $p+1$-st read throws with the allowance in the message.

What crosses a boundary #

The moment a second pass exists, a question appears that a one-pass model does not have: what does the algorithm keep between them?

The answer cannot be “whatever it happens to have in memory”, because that is unbounded and the whole subject is bounded memory. A $p$-pass bound in space $s$ is a statement about the state that survives a pass boundary — that is the quantity the lower bounds are about, and it is the quantity an implementation is free to lie about if nobody asks.

So the carry is declared and then enforced, and the enforcement is what makes the numbers mean anything. Between passes the algorithm is reset() — every field wiped — and rebuilt with restore() from its own declared carry and nothing else. A procedure that reports thirty-two bits and quietly keeps a hash map does not produce a slightly optimistic number; it produces a wrong answer at the next pass and stops.

This is the same device as the model enforcement in the essay on turnstiles and the text withholding in the self-index field, applied to the assumption neither covers: that a pass boundary is a moment at which everything not written down is gone.

It is not decoration. The check that keeps it honest is an algorithm built to cheat — one that keeps the exact count of every key in a map and declares a carry of nothing — and the requirement is that it comes back with the map gone. A second version, with the candidate list struck out of a real algorithm’s carry, must return no answer at all rather than the right one.

What a second pass buys #

The canonical case, and it is the cleanest statement of a pass’s value this collection has.

A Misra-Gries summary with $k$ counters over a stream, asked for every key above $\phi$ of it. Its guarantee is that no heavy hitter is missing from its table. It guarantees nothing about the rest, and its counts are lower bounds — so a counter sitting just under the threshold might be a heavy hitter that was decremented, or a light key that was not.

Nothing in the summary decides which. That is not a limitation of the reading; the information is not there. The shortfall is bounded by $n/(k+1)$ and it is not known key by key.

A second pass settles it exactly. Carry the candidate keys across the boundary, count only those, and report the ones that clear the threshold. The result is exact — no false positives and no misses — and the cost is:

The same space, one more read of the data, and the answer goes from these eighteen contain the twelve to these are the twelve.

The carry is the interesting number. It is $k$ keys and a count — 3,680 bits at $k = 128$ — which is smaller than the summary that produced it, because the counts can be thrown away. Only the identities matter; the counts are about to be recomputed exactly.

What the carry is made of #

Three algorithms in these essays carry state across a boundary, and the three carries are worth putting side by side because they are different kinds of object.

A candidate set. The heavy-hitter procedure carries $k$ keys and the stream length: identities and one number. Nothing about the first pass’s counts survives, because the second pass is about to compute them exactly. That is the cheapest kind of carry — an index into the data rather than a summary of it.

An interval. The selection procedure carries two values and a count of what is already below the interval: ninety-six bits, at every pass count and every problem size. The whole result of a counting pass is compressed into “the answer is between here and here, and this many are below”. That is the cheapest carry there is, and it is the reason the multi-pass selection bound is about the working state rather than about the carry.

And a set of split points, when the split rule is data-dependent. Order statistics of a sample, carried so the next pass can count against them. That is the only carry here that grows with the parameter, and it is what an adaptive rule costs at the boundary as well as in passes.

The pattern across all three: a carry is small when the next pass can recompute what it needs and only has to be told where to look. It is large when the next pass needs a summary of what has gone before. Every multi-pass algorithm that is worth its extra read is of the first kind, and stating the carry separately is what makes the difference visible.

The precondition, which is a property of the summary #

The procedure is often described as “one pass to find candidates, one to verify”, and stated that way it is wrong.

The candidate set is a superset of the heavy hitters only when $k$ is large enough. Misra-Gries’s guarantee is that any key occurring more than $n/(k+1)$ times is in the table, so a threshold of $\phi n$ needs $k + 1 \ge 1/\phi$. Below that, keys above the threshold can be absent from the table, and the second pass counts a candidate set that does not contain them.

Measured, at $\phi = 0.01$ on a stream with twelve genuinely heavy keys:

The first row is the failure mode that looks most like success. Twenty-five counters is a quarter of what the guarantee needs; the second pass is still exact, it is still fast, it returns seven keys and every one of them really is heavy. The output has no false positives and it is missing five answers, and nothing in it says so — the counts are exact, the threshold is exact, and there is no signal anywhere that the candidate set was not a superset.

Both halves are asserted. The two-pass answer at sufficient $k$ must have no false positives and no misses; the two-pass answer at insufficient $k$ must miss something, because an assertion that only checked the good case would leave the precondition looking decorative.

Why the first pass narrows the second #

The two passes are doing different things and it is worth naming what each contributes, because “verify” undersells the first one.

The second pass on its own — counting every key exactly — needs a counter per distinct key, which on this stream is 2,048 of them and 131,072 bits. That is not a summary; it is the exact structure the whole field exists to avoid.

The first pass’s contribution is that it bounds what the second pass has to be about. It reduces the universe from every key that occurred to $k$ candidates, and it does so in the space the streaming model allows. The second pass is then exact over a small universe, and small is what makes it fit.

That is the shape of nearly every multi-pass algorithm: an early pass narrows a candidate set, a later pass is exact over the narrowed set, and the space bound is set by how much narrowing the earlier passes managed. The essay on selection takes it to its limit — narrowing an interval instead of a key set, and doing it $p-1$ times.

What the model becomes #

Turning the restriction into a dial changes what the field’s bounds are statements about, and it is worth saying precisely what.

A one-pass space bound is a special case. Everything in this collection’s streaming field is $p = 1$, and every one of those bounds remains exactly what it was. What changes is that they are now points on a curve rather than the whole story.

And several of the results become sharper. The exact distinct-count floor of $\log_2\binom{u}{u/2}$ bits, and the window floor of exactly $W$ bits, are both one-pass arguments — the pigeonhole is over the states an algorithm can be in after reading a prefix, and it says nothing about an algorithm allowed to read the prefix again. Neither bound survives a second pass, and the essay on the selection floor is about exactly that gap.

And the estimate-versus-exact axis moves. Nearly every structure in this field trades exactness for space. Multi-pass algorithms trade reads for space and keep exactness, which is a different bargain and is available whenever the data is on a disk rather than on a wire. The two are not alternatives so much as different columns in the same table, and the field has only ever had one of them.

What a pass costs #

Nothing here charges for a pass, and that is a deliberate omission with a consequence.

A pass over data on a disk is a sequential read, and this collection has a field about what that costs: the external-memory model counts block transfers, and a pass is $n/B$ of them. Two passes is twice that, and on a large enough dataset the second read is the dominant cost of the whole computation. A pass over data on a wire does not exist at all — the wire has moved on.

So the right way to read every plate in these three essays is: passes and space are being traded, and the exchange rate is left to the reader, because it depends on where the data is. What can be said without knowing that is which points are on the frontier, and that is what the plates draw.

Two passes is not the same as twice the space #

It is worth checking whether the second pass is doing something a bigger summary could have done instead, because if it is, the resource is not new.

It is not, and the arithmetic is worth doing. A key is reported when its count plus the shortfall bound clears the threshold, because the count is a lower bound and the structure has to be conservative. So eliminating false positives means driving $n/(k+1)$ below the gap between the threshold and the nearest non-heavy key’s true count.

On this stream the threshold is 400, the twelfth heavy key has 414 arrivals, and the heaviest non-heavy key has 394. The gap is six. Six is $n/(k+1)$ at $k = 6{,}666$, and measured, the false positive disappears at $k = 6{,}667$ and not before:

Four hundred and twenty-six thousand bits, against eight thousand and one more read: a factor of fifty-two. And the structure at that point holds more counters than the stream has distinct keys — 6,667 against 3,127 — so it is not a summary at all any more, it is the exact answer with a redundant bound attached.

No amount of state makes a one-pass Misra-Gries certain about a key near the threshold, short of becoming the exact structure. The shortfall bound falls but never reaches zero while any decrement has happened, and how close a non-heavy key sits to the threshold is a property of the data that no parameter can anticipate. The second pass gives certainty, which is a different thing from precision, and the one-pass model has no price for it at all.

That is the general reason passes are worth having as a separate axis rather than being folded into space. They buy a kind of answer, not a quantity of accuracy.

Only the uncertain candidates need carrying #

The procedure as described carries every key in the table and re-counts all of them. It need not, and the reduction comes from a number the first pass already has.

Misra-Gries’s counts are short by at most $D$, the number of decrement steps performed — a quantity the structure can tally as it runs, for the price of one integer. With it in hand, every candidate falls into one of three classes:

• certainly heavy — its count already exceeds the threshold, and the true count is at least the count;
• certainly not — its count plus $D$ is still below the threshold, and the true count is at most that;
• uncertain — its bracket straddles the threshold.

Only the third class needs a second pass. The first two are settled by the first pass with no further reading of anything, and the answer for them is exact rather than probable.

That shrinks the carry from $k$ keys to however many sit within $D$ of the threshold, which on a skewed stream is a small number — the heavy keys are heavy by a wide margin and the light ones are light by a wider one, and only the handful clustered around the boundary are in doubt. On the stream measured here the threshold is 400 and the crowd near it is thin, so most of the eighteen candidates are decided before the second pass begins.

The second pass is therefore not a verification of the candidate set; it is a resolution of the boundary, and the boundary is the only part of the answer the first pass was uncertain about.

Two consequences worth having. The carry number quoted above — 3,680 bits — is an upper bound rather than the cost, and the actual cost depends on how many keys sit near the threshold, which is a property of the data. And the same three-way classification is what makes a partial second pass sensible: an implementation short of time can resolve the uncertain candidates in whatever order it likes and stop, reporting the ones it settled and the ones it did not, which is a strictly better failure mode than either extreme.

A carry is a message #

There is a reading of the carry that makes its size matter beyond bookkeeping, and it is the one that connects this essay to the setting where multi-pass algorithms are actually deployed.

A pass boundary and a communication round are the same event. An algorithm that reads a stream twice on one machine, carrying $c$ bits between the passes, becomes an algorithm that runs on $m$ machines in two rounds, sending $c$ bits per machine in between. The carry is not an accounting device in that setting — it is the message, and the quantity that decides whether the distributed version is affordable.

That gives the three carries in the section above a second reading. A candidate set of 3,680 bits is a message a coordinator can gather from a thousand shards without noticing. An interval and a count — ninety-six bits — is nothing at all. A set of order statistics grows with the split count and is the only one of the three that would show up on a network graph.

It also explains why the carry has to be enforced rather than declared. On one machine an undeclared carry is a memory leak that flatters a number; distributed, it is a message that has to be sent and cannot be, so an algorithm whose real carry exceeds its stated one does not merely report a wrong figure — it does not run.

What is not measured here #

Passes that are not identical. Everything here reads the same stream in the same order every time. An algorithm allowed to read it backwards on the second pass is strictly more powerful, and the multi-pass lower bounds in the literature are usually stated for forward passes only.

Streaming with a sorted or indexed second pass. A great deal of practical multi-pass work reads the data once to build an index and then reads selectively rather than passing over everything. That is a different resource again and none of the machinery here measures it.

The rounds-versus-passes distinction. In a distributed setting the analogous resource is a round of communication, and the two are related but not equal — one round can perform several passes in parallel over different shards. Nothing here is about that model.