What a second pass buys

The question is the median, exactly, and the algorithm may read the data $p$ times.

At $p = 1$ there is nothing to be done: an exact one-pass selector has to keep the stream, which for thirty-two thousand thirty-two-bit values is 1,048,576 bits, and the floor under that is the subject of the next essay.

At $p = 2$ it is 11,712 bits. At $p = 9$ it is 320.

The method is an interval that narrows #

The whole procedure fits in three sentences.

Keep an interval that must contain the answer, and a count of how many values are already known to be below it. Each pass cuts the interval into $s$ pieces, counts how many values fall in each, and narrows to the piece the target rank lands in. The last pass keeps whatever is still inside the interval and sorts it, which is what makes the answer exact rather than approximate.

The state during a narrowing pass is $s$ counters and the cut points. The state during the last pass is however many values survived. Balance those and the whole thing is decided:

$$s \approx \frac{n}{s^{\,p-1}} \quad\Longrightarrow\quad s \approx n^{1/p}$$

so both the counters and the survivors are about $n^{1/p}$, and that is the peak.

Nine splits a pass, and the count falls by roughly nine each time: 32,768 to 3,685 to 457 to 40 to 3. That is the arithmetic working, and it is working on equal-width cuts of the value range — the rule that needs no knowledge of the data at all.

The exponent, fitted #

A claim of $n^{1/p}$ is a claim this collection has machinery for. Taking logarithms, $\log_2(\text{peak})$ should be linear in $1/p$ with slope $\log_2 n$.

Fitted: slope 13.54, against a predicted $\log_2 32{,}768 = 15$. Worst departure from the fitted line, 12%.

The departure is at the ends and both ends are explained. At $p = 9$ the ideal split count is $32{,}768^{1/9} = 3.17$, which rounds to four — a 26% overshoot that propagates through nine passes — and the peak flattens because the counters cannot go below a handful. At $p = 2$ the survivors dominate rather than the counters, and the survivor count is a random quantity rather than exactly $n/s$.

So the honest statement is: the peak follows $n^{1/p}$ to within twelve per cent over the measured range, and the departures are integer rounding of the split count rather than a different law. The fit is not offered as a demonstration that the exponent is exactly $1/p$ — seven points over a range of thirty-six times cannot establish that — it is offered as a test the claim could have failed, and did not.

Equal width is a bet on the data #

Everything above is on values spread evenly over the range. Change that and the deterministic rule does not degrade — it collapses.

At two passes on a heavy tail the peak is 1,040,608 bits, which is 99.2% of what keeping the entire stream costs. Nine passes gets it to 52,864 — still a hundred and sixty times worse than the same rule on uniform data at two passes.

The reason is exactly one sentence: an equal-width cut narrows the range and not the count. A Pareto distribution puts almost all of its mass in a tiny fraction of its range, so cutting the range into nine pieces puts nearly everything into the first piece, and the pass has narrowed the interval ninefold while eliminating almost nothing.

Two things in that trace are worth noticing. The interval genuinely does shrink — the rule is not broken — and after four passes the count finally drops, from 31,364 to 10,547, because by then the interval has narrowed enough to be inside the bulk of the distribution. The whole cost is paid in the early passes, on a range that is mostly empty.

A rule that needs no data is a rule that has assumed something about it, and the assumption here is that the values are spread evenly enough for range and count to be proportional. That is stated nowhere in the method and it is the difference between three hundred bits and a million.

Adaptive splits, and what they cost #

The repair is to cut at order statistics of the data rather than at equal widths — take a sample, sort it, use it to split. Then each piece holds about the same count by construction, and the distribution stops mattering.

It costs a pass. Nobody knows where the order statistics are until a pass has gone by, so the passes alternate: sample, count, sample, count. Nine passes give four narrowings rather than eight.

The sampled rule is between thirteen and eighty-three times better on this data, at every pass count, while doing half as many narrowings.

And on uniform data it is worse, at every pass count, for the same reason: half its passes buy nothing that equal-width cuts do not already give.

That reversal is asserted on every build, in both directions, because a comparison run only on skewed data would be measuring a rule’s advantage in the one place it has one and calling it a property of the rule.

The floor when the values repeat #

One row above is flat and it is not noise: the sampled rule reports 4,032 bits at five, seven and nine passes, and 126 survivors each time.

The values here are a heavy-tailed distribution rounded to integers, and 126 of them are equal to the answer. An interval cannot be narrowed below a single value, so once the interval has collapsed onto the answer’s value, the survivor count is its multiplicity and no further pass changes anything.

That is a real floor and it is worth stating in general: exact selection by interval narrowing cannot get below the multiplicity of the answer, whatever the pass count. On continuous data the multiplicity is one and it never binds. On integer or bucketed data — which is most real data — it binds at whatever the mode’s local density is, and it is the reason the sampled curves flatten while the deterministic ones are still falling.

The repair is to stop narrowing and start counting: once the interval holds one distinct value, the answer is that value and the survivors need not be kept. That is an implementation choice rather than a property of the method, it is not taken here, and the flat rows above are what it costs.

What crosses the boundary, and it is nearly nothing #

The working state is what the plates above draw. The carry — what survives a pass boundary — is a different quantity and it is the one a bound in $p$ and $s$ is stated in.

Ninety-six bits. Two values and a running count, and nothing else survives a pass. The counters are recomputed from scratch every time, the survivors are recomputed from scratch every time, and the algorithm’s entire memory of everything before this pass is where to look.

The sampled rule’s carry is larger, because the split points have to survive: an interval, a count, and $s$ order statistics. That is the only carry in these essays that grows with the parameter, and it is what an adaptive rule costs at the boundary as well as in passes.

The carry is enforced rather than believed. Between passes the algorithm’s state is wiped and rebuilt from its declared carry alone, so a procedure keeping a hash map on the side returns a wrong answer rather than a flattering number.

The two passes at the ends are different from the others #

The sweep hides a structural point that is worth drawing out, because it explains both ends of every curve above.

The last pass is not a narrowing pass. It keeps whatever is inside the interval and sorts it, and its state is the survivor count rather than the split count. So a $p$-pass run has $p-1$ narrowings and one collection, and at small $p$ the collection dominates: at two passes the single narrowing leaves 214 survivors and 11,712 bits, of which the counters are a fifth.

And the first narrowing is the only one that sees the whole data. Every later pass counts only what is inside the current interval, so the later passes are cheaper in work even though they are the same length in reads. That asymmetry is invisible in a state measurement and is most of what a real implementation would care about.

Between them these explain why adding a pass helps enormously at the cheap end and barely at all at the expensive one. Going from two passes to three replaces one enormous collection with a narrowing and a smaller collection — a factor of five and a half. Going from seven to nine replaces two small narrowings with two smaller ones, and the split count is already down to four or five where integer rounding dominates.

There is a point past which more passes buy nothing, and it is where $n^{1/p}$ reaches the smallest split count that makes sense. At $s = 2$ each pass halves the interval and $p = \log_2 n$ passes are needed — fifteen here — which is the binary search the whole method generalises. Below that split count there is nothing left to give up.

There is a third repair that costs neither a pass nor an assumption, and it is worth naming because it is what a production selector usually does: cut on the bits of the values rather than on their range. A radix split on the top $\log_2 s$ bits is an equal-width cut in disguise, so it inherits the collapse; a split on the exponent field of a floating-point value is an equal-width cut in the logarithm, so it inherits the repair. The representation the values already carry decides which of the two rules is being run, and neither the code nor the analysis mentions it, which makes this one of the quieter ways a method’s behaviour is settled by something nobody chose.

Where the passes actually come from #

Nothing here charges for a pass, and it is worth saying where the charge would come from if it were made, because it is a field this collection already has.

In the external-memory model a pass is $n/B$ block transfers, so a nine-pass algorithm holding 320 bits does nine times the I/O of a one-pass algorithm holding a million. Which of those is better depends on the ratio between memory and bandwidth, and that ratio is a property of a machine rather than of an algorithm.

So passes and space are being traded here and the exchange rate is deliberately left out. What the plates establish is which points are on the frontier; what a reader supplies is what a pass costs where their data lives. On a wire it is infinite — there is no second pass — and every point but the leftmost is unavailable.

Whether the sampled rule’s passes can be fused #

The sampled rule spends half its passes producing no narrowing at all, which is the whole of why it loses on uniform data. The obvious repair is to fuse the two: gather the reservoir while counting, so that every pass both narrows the interval and collects the sample the next narrowing will cut on.

It is worth working out what that costs, because the arithmetic settles the question and the answer is not the one the idea promises.

A reservoir gathered during pass $i$ is a sample of the interval as it stood during pass $i$. At the end of the pass the interval shrinks to one piece in $s$, and only the sampled values that happen to fall inside that piece are usable as cut points for the next pass. In expectation that is one in $s$ of them. So a fused rule that wants $s$ usable order statistics at every pass must carry a reservoir of about $s^2$, and the state during a narrowing pass becomes $s^2$ counters-and-samples rather than $s$ counters.

Balance that against the survivors as before. The peak is now the larger of $s^2$ and $n/s^{\,p-1}$, which is minimised at $s \approx n^{1/(p+1)}$, giving a peak of about $n^{2/(p+1)}$ against the unfused rule’s $n^{1/\lceil p/2 \rceil}$. Fusion wins for large $p$ and loses for small $p$, and the crossover is around five passes — which is exactly where the sampled column above stops improving for a different reason.

Two honest caveats on that paragraph. The factor of $s$ in the surviving sample is an expectation and a run can be unlucky, so a fused implementation needs a fallback for the pass where too few samples survive, and a fallback that reverts to equal-width cuts inherits the collapse this essay is about. And none of it is measured here: the arithmetic above is a derivation from the same balance that produced $n^{1/p}$, offered as a reason not to expect much rather than as a result. A cheap derivation that says an idea is not worth implementing is worth more than an expensive implementation that says the same thing, provided it is labelled as what it is.

A transform is a cheaper repair than a pass #

The sampled rule buys its robustness with passes. There is a repair that costs none, and putting it beside the other two makes the essay’s thesis sharper rather than softer.

Cut at equal widths in $\log v$ rather than in $v$. On a Pareto or a log-normal distribution the mass is spread evenly in the logarithm, so equal-width cuts in log space hold roughly equal counts, and the narrowing behaves the way it does on uniform data. The cut points are still computed from the range alone, no pass is spent learning anything, and the carry does not grow.

What has changed is not the amount of knowledge the rule uses but its honesty about it. Equal-width cuts on the raw values are a bet that the data is uniform; equal-width cuts on the logarithm are a bet that it is log-uniform. Neither rule reads the data and both are assumptions; the second is simply a better assumption about the kind of data that produced the disastrous column above, and it is wrong in its own way — on uniform data it puts most of the mass in the last piece and collapses exactly as the first rule does on a heavy tail.

That symmetry is the point. There is no distribution-free rule that reads no data, and the sampled rule’s extra pass is the price of not having to guess which family the data is in. A deployment that knows its latencies are log-normal should cut on the logarithm and keep its passes; one that does not know should spend the pass and stop guessing.

It also names precisely what the sampled rule is buying, which the tables above leave implicit. It is not accuracy — every point on every curve is an exact answer. It is not passes — it spends more of them. It is independence from a property of the data that nobody wrote down, and that is worth paying for in proportion to how surprising the data is allowed to be.

What is not measured here #

Randomised selection in one pass, approximately. The whole apparatus above is about exactness. An approximate median is available in one pass and very little space, from the quantile summaries two essays back, and the comparison between “exact in nine passes” and “within one per cent in one” is a comparison of different products.

Work. Each pass here scans the whole data. A narrowing pass could skip values outside the interval if the data were indexed, and the count of operations would then fall with the interval rather than staying at $n$ every pass. Nothing here measures operations, only state.

The known bound. Munro and Paterson proved a $\Omega(n^{1/p})$ lower bound for $p$-pass selection in a comparison-based model in 1980, and the measurements above sit on that shape. The bound itself is not demonstrated here, and the next essay is precise about which parts of the floor this collection performs and which it quotes.