The thread: A pass is a resource
The pass that was never a parameter
One pass is the streaming model's defining restriction, and this collection has enforced it by making a second read throw. A prohibition cannot be swept. Turn it into a dial and the first thing it says is that a second pass turns eighteen candidate heavy hitters, six of them wrong, into twelve that are exactly right — for 3,680 bits carried across the boundary and no extra space at all.
The other axisWhat a second pass buys
Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.
The floorsThe pass that runs the other way
Exact heavy hitters over the last 4,096 of 40,000 arrivals cost 40,000 reads and a ring of 4,096 keys and stamps read forwards, and 4,096 reads with no stamps read backwards. Every lower bound in the sliding-window model is a bound about an access pattern, and the word doing the work never appears in the statement.
The floorsA floor one pass cannot get under
An exact one-pass selector must reach a different memory state for every prefix it might have read, and the pigeonhole that proves it is small enough to perform — nine hundred and twenty-four prefixes through a nine-bit state, the collision produced, the suffix that separates it, and two true medians it cannot both return. Ten bits collide on none, so the bound is exact — and a second pass walks under it by a factor of ninety.