The period that is not a promise

Greenwald and Khanna’s summary is given by one parameter, and that parameter is used twice.

Once as the promise. A tuple at rank $r$ may carry a rank uncertainty of at most $2\varepsilon n$, and enforcing that invariant is what makes the structure a summary rather than an array.

Once as a schedule. The structure compresses every $\lfloor 1/2\varepsilon \rfloor$ updates — fifty of them at $\varepsilon = 0.01$ — and every account of the structure prints that number, and none of them says what it is for.

The obvious reading is that the schedule is part of the promise — that a summary compressing more often is a summary holding its invariant more tightly. It is not, and the plate above is the whole of the argument. Compress on every single update and the summary settles at seventy-seven tuples with a worst rank error of 126. Compress every thousandth and it settles at seventy-three tuples with a worst rank error of 120. Across the whole sweep the resident size moves by 10% and the error by 21%, both of them noise against a promise two hundred ranks wide.

The invariant does not know when it was last enforced #

The reason is one line of the structure’s own arithmetic, and it is worth stating before the measurements pile up.

A compression walks the tuple list and merges a tuple into its neighbour wherever the combined band fits under the cap. Afterwards, every tuple satisfies the invariant. That is a property of the list at the moment the pass finishes, and nothing in it refers to how long the list had been growing beforehand.

So a summary that has just compressed is a correct $\varepsilon$-summary whether the last compression was one update ago or a thousand. What a longer gap buys is a longer list to walk when the walk comes; what it costs is the tuples sitting in that list in the meantime. Neither of those is the promise.

This is the same distinction the digest that promises nothing turns on from the other side — there the structure has a bounded state and no bound on its answer, and here the structure has a bounded answer and an unbounded-looking state — and it is why the two questions have to be asked separately every time.

It is worth being precise about what the invariant does and does not cover, because the schedule sits exactly in the gap. Greenwald and Khanna’s condition is on the stored tuples: for every tuple, $g_i + \Delta_i \le \lfloor 2\varepsilon n \rfloor$. A tuple that has just arrived and has not yet been offered to a compression satisfies it trivially — it was inserted with $g = 1$ and a $\Delta$ computed from the cap at its own rank, which is the cap it would have been given at any other moment. So the list is never in violation, not even in the middle of the longest gap. The compression is not repairing a broken invariant; it is reclaiming the space that the invariant would permit reclaiming.

That is the difference between a schedule and an enforcement, and it is the reason the accuracy columns above are flat. An enforcement that ran late would show up in the answer. A reclamation that runs late shows up in the meter.

What the period is for #

Unhook the two uses of $\varepsilon$ and the schedule’s real job appears immediately.

A compression scans the whole retained list, so its cost is the number of tuples in it. Over a stream of $n$ arrivals a summary compressing every $P$ updates does $n/P$ compressions of roughly $|S|$ tuples each, and $|S|$ is the thing the structure’s own bound fixes: $\Theta(1/\varepsilon)$, measured here at $0.77/\varepsilon$ across a twenty-five-fold range. So the total housekeeping is

$$\frac{n}{P} \cdot \frac{c}{\varepsilon}$$

and at $P = 1$ that is $\Theta(n/\varepsilon)$ — a bill that grows as the promise tightens. Set $P = \lfloor 1/2\varepsilon \rfloor$ and the $\varepsilon$ cancels:

$$\frac{n}{1/2\varepsilon} \cdot \frac{c}{\varepsilon} \;=\; 2cn$$

The prescribed period is there so that the total housekeeping stops depending on the promise. That is not a small thing to leave unsaid, and it is measurable to three figures.

The lower series is flat to 3%. The upper one rises by a factor of 25.7 across a range of $\varepsilon$ spanning exactly 25, which is the $1/\varepsilon$ the flat line is standing in front of and hiding.

The predicted constant is $2cn = 2 \times 0.77 \times 20{,}000 = 30{,}800$, against a measured fifty-one thousand. The gap is a factor of 1.66 and it is not slack: a compression scans the list at whatever size it has reached, which is somewhere between the resident count and the peak, and the mean of that ratio over the sweep is 1.66. The arithmetic is right and the constant in it is the headroom, which is the next section.

What it is paid for in #

Between two compressions every tuple that will be merged away is still present. So the summary’s peak is its resident size plus, near enough, its period.

A summary at $\varepsilon = 0.01$ over twenty thousand arrivals reports seventy-seven tuples and occupies a hundred and thirty-six. At $\varepsilon = 0.002$ it reports 397 and occupies 674. The ratio is between 1.70 and 1.93 everywhere measured, and it is not an artefact of the sweep — it is $(|S| + P) / |S|$ with $|S| = c/\varepsilon$ and $P = 1/2\varepsilon$, which is $1 + 1/(2c) = 1.65$ before the peak’s own fluctuation is added.

A deployment that sized its allocation from the number the structure reports has sized it for a little over half of what the structure uses. This is the same failure in-place is a claim documents for sorting, and the same one the stack nobody counts documents for recursion: a structure’s honest footprint is its peak, the number it is happy to quote is something else, and the gap has a name in the source that nobody reads as a space cost.

One knob, two jobs, and they pull in different directions #

Halving $\varepsilon$ does four things at once, and only the first is the one anybody intends.

The promise halves. The resident state doubles. The period doubles. And the peak, being the sum of the last two, also doubles — while the total housekeeping, being their quotient, does not move at all.

That last cancellation is worth dwelling on, because it is the sort of thing that is invisible until somebody unhooks the parameters. A deployment that tightens its promise by a factor of ten pays ten times the memory and nothing at all in compression work. If it also decided, reasonably, to compress more often because the summary is now larger, it would pay ten times the memory and ten times the work, and the second of those would be a cost it invented.

The mirror is worse and is the more likely mistake. A deployment worried about the peak might cap the period at some fixed number of updates — say fifty, whatever $\varepsilon$ is — which caps the headroom nicely and quietly restores the $1/\varepsilon$ in the housekeeping. At $\varepsilon = 0.002$ that is a fivefold increase in scan work for a peak saving of two hundred tuples.

Both of those are decisions somebody makes by reading the code and reasoning about it, which is the point. A parameter that appears once in the guarantee and once in a loop condition is read as one parameter, and every consequence of the second appearance arrives as a surprise. The count somebody chose makes the same case about a window length, and the model a bound was quoted in makes it about the machine a complexity is stated against; this is the version where the two uses share not just a document but a symbol.

The measured shape of the trade is worth writing down, because it is not the shape a reader would guess. Over the swept range the housekeeping falls steeply at first and then flattens — 1,542,402 at a period of one, 50,185 at fifty, 21,508 at a thousand — so almost the whole of the saving is bought by the first fiftyfold increase and the remaining twentyfold buys 2.3 times more. The peak, meanwhile, is linear in the period throughout. Past the prescribed point the curve is nearly all cost, which is a reasonable thing for a prescription to be sitting at and is not what anybody chose it for.

Nothing leaves #

There is one more consequence of the arithmetic, and the rest of this strand rests on it, so it is worth measuring here rather than asserting later.

A compression merges a tuple into its neighbour by adding the tuple’s $g$ to the neighbour’s. It never drops a $g$. So the sum of $g$ over the summary is the number of arrivals, at every instant, before and after every compression.

That is what separates this structure’s schedule from the boundary that hides the burst, where an arrival-counted boundary really does decide which arrivals leave, and where being commensurate with a period in the stream really does hide it. Here the schedule decides only how large the backlog is when it is looked at. The sampler that cannot alias takes that difference apart.

The conservation also explains the flat accuracy column more sharply than the invariant argument does. A rank query walks the list accumulating $g$, and the answer it returns is decided by where the accumulated $g$ crosses the target rank. Since the total $g$ is $n$ whatever the schedule has been doing, two summaries of the same stream at different periods are answering from lists whose rank coordinates agree exactly; they differ only in how finely those coordinates are subdivided. A longer period leaves a finer subdivision in place for a while, which is why the peak is larger, and it does not move any boundary the query is looking for.

That is also the reason the effect that did show up — a 21% spread in worst rank error across the sweep — is noise rather than trend. It has no sign: 126, 126, 126, 126, 126, 143, 120, 145, 120. A structure whose accuracy improved with a longer backlog would produce a monotone column, and a limit is not a prediction applies to a reader’s eye as much as to an assertion.

What was withdrawn #

Two things this essay set out to measure did not survive contact with the measurement, and both belong here rather than in a footnote.

The first is a claim that a longer period makes the summary more accurate, on the grounds that it holds more tuples and therefore more information. It plainly holds more tuples — 1,092 against 108 — and the worst rank error at a period of a thousand is 120 against 126 at a period of one, which is a 5% difference in a quantity that moves by 20% across the sweep for no reason at all. There is no effect here to report. The extra tuples are ones the invariant was going to permit merging anyway, and they carry no information the compressed list did not.

The second is a tidier version of the headroom arithmetic in which the peak is exactly $|S| + P$. It is not exact — the worst departure is 14% — because tuples merge during the gap as well as at the compression, whenever an arrival lands next to a band it fits inside. The structure does not wait for the pass to merge; the pass is only where the scan happens. Reporting $|S| + P$ as an identity would have been neat and would have been a claim the measurement refuses.

The schedule the cancellation actually asks for #

The flat bill above was obtained by putting $1/2\varepsilon$ in the period and $c/\varepsilon$ in the state, and watching the $\varepsilon$ cancel. That cancellation is worth doing once more without committing to either expression, because the general form says something the special case hides.

Let the resident state be $|S|$, whatever law it follows. A compression scans it, there are $n/P$ compressions, so the housekeeping over the stream is

$$\frac{n}{P}\,|S|$$

and the bill is independent of the promise exactly when $P$ is proportional to $|S|$. Not when $P$ is proportional to $1/\varepsilon$ — that is a coincidence of Greenwald–Khanna’s state happening to be $\Theta(1/\varepsilon)$, and it is the reason the prescribed number reads as a fact about $\varepsilon$ when it is a fact about the list.

So the rule the arithmetic is asking for is compress every $|S|$ updates, and $|S|$ is not a quantity the structure has to derive. It is the length of a list it is holding. A schedule written that way has no $\varepsilon$ in it at all, needs no bound on the state to be correct, and would go on cancelling for a structure whose state grew as $\log(1/\varepsilon)$ or as $1/\sqrt{\varepsilon}$ — the case the fitted $0.77/\varepsilon$ above cannot speak to.

The constant it lands on is exact rather than fitted. With $P = |S|$ the bill is $n$ tuple examinations over $n$ arrivals: one per arrival, amortised, which is the tidiest statement of cost this structure admits and is a genuinely amortised one — no single arrival does that work, and the arrival that triggers a pass does all of it.

Against the prescribed schedule that is a saving. Greenwald–Khanna’s $|S|/P$ is $0.77/\varepsilon$ over $1/2\varepsilon$, or 1.54 examinations an arrival, so the self-sized period costs about two thirds of what the prescribed one costs. What it spends instead is headroom: the peak becomes $|S| + P = 2|S|$ rather than the measured 1.65, so the ceiling a deployment must provision rises by a fifth.

That is a legible trade rather than a free improvement, and it is legible in the units a deployment cares about — a fifth more memory for a third less scanning — which is precisely what the shared symbol makes impossible to see. It also puts the memory ceiling on the right side of the equation. A deployment with a hard cap of $M$ tuples can set $P = M - |S|$ directly and never think about $\varepsilon$ again, and the structure will spend whatever scanning that implies rather than requiring somebody to solve for it.

None of that is measured here. It is arithmetic on the same two quantities the plates above measured, and it is stated as arithmetic; the sweep that would test it varies the state law rather than the period, which is a different structure and a later essay.

Both readings hold on a different input distribution, which is the check that the schedule is about the structure rather than about the values going through it.

The rule this leaves #

A structure’s parameters are not always the parameters of the object it is a summary of. $\varepsilon$ is a promise and $\lfloor 1/2\varepsilon \rfloor$ is a schedule, and they share a symbol because sharing it makes one bill constant.

That is a good reason, and it has a cost that nobody states: the promise and the schedule can no longer be tuned apart. A deployment with a hard memory ceiling and no particular pressure on CPU wants a small period and a tight $\varepsilon$; one with the reverse wants the reverse; and the structure as written offers both of them the same diagonal through the space.

Unhooking the two is a three-line change and it is the thing this essay was built on. The measurements above are the case for offering the knob: over a thousand-fold sweep it moves the peak by ten times and the housekeeping by seventy, and it moves the answer by nothing.

And the check that has to be able to fail: a period of zero is refused rather than clamped. A structure that silently accepted it would compress between arrivals, cost $n|S|$, and answer correctly — which is exactly the failure this essay is about, a schedule that is wrong in a currency nobody is reading.

The honest limit is the range. Everything above was measured on a log-normal stream of twenty thousand values with $\varepsilon$ between 0.05 and 0.002, and the flatness of the housekeeping bill rests on $|S| \propto 1/\varepsilon$, which is the structure’s bound and holds here to within the 0.75–0.79 spread of the fitted constant. A summary whose state did not go as $1/\varepsilon$ — the t-digest, for one, whose centroid count is set by $\delta$ and by the arcsine scale rather than by a tolerance — would need a different schedule to buy the same flat bill, and this essay has not measured what that schedule is.