A floor with two variables in it

The previous essay left a condition dangling. A fold’s charge to a surviving key is one floor per level, and that equals the older model’s $m-1$ leaf floors exactly when the floor doubles as the mass doubles. At eight shards under hashing it does, to within 0.03. At sixty-four it does not, by 0.53.

So: does a Space-Saving floor scale with the arrivals that produced it?

The answer is that the question is malformed, and the way it is malformed is the finding.

One partition gives a law #

Split a forty-thousand-arrival Zipf stream round-robin into 128, 64, 32, … , 1 shards and measure the floor each settles at.

313 arrivals → 6.9. 625 → 14.3. 1,250 → 29.3. 2,500 → 59.6. 5,000 → 120.1. 10,000 → 241.0. 20,000 → 483.0. 40,000 → 967.0.

Fitted: $0.0203 \cdot n^{1.018}$, worst residual 2.7%. That is a clean law over a hundred-and-twenty-eight-fold range and it is as close to linear as this site’s fits get. Doubling the mass doubles the floor.

The other gives nothing #

Split the same stream by hashing the keys and the numbers are these.

313 → 0.1. 625 → 2.8. 1,250 → 10.4. 2,500 → 29.1. 5,000 → 74.8. 10,000 → 180.0. 20,000 → 424.5. 40,000 → 967.0.

The two agree at the right-hand end, as they must: one shard is the whole stream either way, and both read 967. Everywhere else they diverge, and the hashed column is not a power law. The local exponent between adjacent pairs runs 5.17, 1.91, 1.48, 1.36, 1.27, 1.24, 1.19 — still falling at the widest end measured, with no sign of settling.

A least-squares line through those eight points reports $n^{1.73}$ with a worst relative residual of 441%. The fit is refused. The floor a histogram already knows computes these numbers from a histogram and never had to ask how they scale; asking is what turned up the crossover. Printing an exponent through a slope that is still moving is a number describing none of the points, and this site withdrew two of its earliest complexity claims for exactly that reason.

The second variable #

The floor is a fixed point over the tail of a shard’s histogram — the mass of everything the table is not holding, shared among the slots that churn. So what it depends on is not the mass but how much of the shard’s key space the table covers, and the two partitions move that quantity in completely different ways.

A round-robin shard is a sample. It sees the whole universe, thinned. Its distinct-keys-per-arrival falls as it grows — 0.479 at the smallest, 0.078 at the largest — because coupon collection saturates. But at every size it holds far more distinct keys than thirty-two counters can: 150 at the smallest shard measured, 3,127 at the largest. The table’s share of the shard’s key space runs from 0.21 down to 0.010, and it is small throughout.

A hashed shard is a scaled copy. Hashing splits the universe, so a shard holds one $m$-th of the keys and one $m$-th of the mass, and its distinct-keys-per-arrival is 0.078 at every size measured, to three figures. What moves instead is the table’s share of that key space, and it moves across everything: 32 counters against 24 distinct keys at the small end, and against 3,127 at the large end. The share runs from 1.33 down to 0.010.

At 1.33 the table holds the shard’s entire key space. The summary is exact; there is no tail; the floor is 0.1, which is the rounding of nearly nothing. At 0.010 it is a summary and the floor is 967.

A range that crosses from an exact structure to a summary is not a power law over that range, and it should not look like one. It does not.

The point where the structure stops being a summary #

The small end of the hashed column is worth its own paragraph, because a floor of 0.1 is not a small floor — it is the absence of one, and it means something different.

At 128 shards a hashed shard holds about 24 distinct keys and 313 arrivals. A table of thirty-two counters never fills. Nothing is ever evicted, so floor is defined as zero by the structure’s own rule, and the 0.1 in the table is the mean over 128 shards of which a handful did fill.

The structure is exact there. It is not a summary of that shard; it is a complete count of it, holding every key with its true frequency, and the error it contributes to a merge is nothing at all. That is why the leaf model’s total collapses at high shard counts: it is summing 127 copies of a number that is nearly zero because the leaves are nearly perfect.

And it is why the level account does not collapse. The leaves are exact and the nodes are not — by the third level of a 128-way fold the subtree holds four shards’ key spaces against the same thirty-two counters, the table has stopped fitting, and the floors begin. The charge is real and it happens entirely above the leaves, which is precisely the region a leaf model cannot see.

This is also the sharpest available statement of what “regime” means for this structure. There are three: one where the table holds everything and the summary is exact, one where it holds a small share and the floor is proportional to the mass, and a crossover between them that is neither. Every published bound is about the second. Every measurement in this collection before these essays was in the second. And a deployment sharding finely enough puts its leaves in the first and its merges in the crossover.

Which is why the leaf model failed where it did #

The condition on the identity was “the floor doubles when the mass doubles”. That is now readable as “the table’s share of the key space is not changing”, and the two partitions answer it in opposite ways.

Under round-robin the share is small everywhere and changes only slowly, so the floor scales and the two models agree. Under hashing merging two shards doubles the mass and doubles the distinct keys, so the table’s share halves at every level, so more of the histogram is tail, so the floor more than doubles — 2.53, 2.45, 2.44, 2.40, 2.39 at sixty-four shards.

The departure from doubling is therefore a direct read on how fast the share is moving, and it is the diagnostic the warning that is silent for the right reason puts to work.

What a deployment does with this #

Two practical readings, and they point in opposite directions.

Sharding more finely makes the leaves better and the fold worse. Each shard’s table covers more of its own key space, so each shard’s summary is closer to exact — and there are more merges, each of which combines key spaces and pushes the table’s share down. At sixty-four shards the leaves are essentially exact and the surviving key is still charged 409, which is more than the 313 it would be charged at four shards where every leaf is a genuine summary. The intuition that finer sharding gives better per-shard answers is correct and it does not survive the merge.

The width is the knob that reverses it. Doubling $k$ moves the table’s share up at every level of the fold, and it moves it up most where the fold is deepest. A deployment that has decided on its shard count for reasons of throughput can still choose where the crossover sits, and the choice is worth more at high shard counts than at low ones. What it cannot do is read the right width off any published statement of the structure, because the published statement is $\varepsilon = 1/k$ and takes no view on how many distinct keys are in play.

What a two-variable quantity does to a bound #

There is a broader point here about how a quantity like this gets stated, and this site has met it once before.

Two parameters, one bound is where a graph algorithm’s cost turned out to need two variables and a stated density regime, because $O(E \log V)$ and $O(V^2)$ are the same algorithm at different densities and quoting either alone is quoting a regime. The floor is the same shape of object: it is a function of the mass and of the table’s share, and every statement of it so far has held the second fixed by accident.

The difference is that a density regime is something a person states, and the table’s share of a shard’s key space is something a partition sets without anybody choosing it. The partition the analysis did not mention is the first place on this site where a parameter arrived that way, and this is the same parameter arriving again in a quantity nobody had connected to it. Nobody sharding a stream by hash is thinking about how many distinct keys land on each shard; they are thinking about giving each key one home. The consequence for the floor arrives free.

The width is the other way to move it #

If the share is what matters, then the counter width should be interchangeable with the shard count, and it nearly is.

Thirty-two counters against a sixty-four-way hashed shard is the same share as sixty-four counters against a thirty-two-way one, and the floors ought to correspond. They do to within the noise of a single stream, which is a weaker check than it sounds because the two configurations also differ in absolute mass — and mass is the first variable.

The cleaner statement is the one the refusal already makes. A floor quoted for “a Space-Saving summary of $k$ counters over $n$ arrivals” is under-specified, and what is missing is the number of distinct keys in play. Every published statement of this structure’s error is of the form $\varepsilon n$ with $\varepsilon = 1/k$, which is a bound and is correct; the realised floor is far below it and is where all the interesting behaviour lives, and it needs the third number.

The same iteration on a stream whose favourites move is the check that the third variable is doing the work rather than the stationarity. A drifting shard’s histogram has a longer body and a shorter head, so more of its slots churn — and the fixed point should land higher for that reason and not because anything about the width or the mass has changed.

The refusal, and the machinery for it #

A fit that declines to publish is a small piece of machinery and it is the load-bearing part of this essay, so it is worth saying how it decides.

It computes the local exponent between each adjacent pair of points and looks at the spread. If one exponent describes the range, those numbers agree; if the slope is drifting, they do not. Under round-robin they span 0.08 and the fit is offered. Under hashing they span 3.98 and it is withheld.

The check that keeps it honest is the one that would otherwise be missing: the fit must still have been computed. A refusal that came from the fitter failing to converge, or from too few points, would be the right answer arrived at by accident and would stop being the right answer as soon as somebody added a point. So the hashed sweep returns the fit it declined to publish, and the check asserts both that the published one is absent and that the attempted one exists.

Two declared complexity claims were withdrawn among this site’s earliest work because the fit refused them, and the machinery for refusing has been here since. What was missing was a refusal criterion that could see a drifting slope, as opposed to a poor one — a residual measures distance from a line and says nothing about whether a line was the right object.

Where this sits among the other floors #

This site has a field called floors and it has, until now, been about lower bounds — the comparison floor, the state floor, the one-pass floor. Those are statements that nothing can do better, proved by counting.

The floor in this essay is a different object with the same name, and the collision is worth naming rather than tolerating. A Space-Saving floor is the smallest counter in a table: an observed quantity that the structure settles at, which decides how wrong its answers are and which nothing about the problem forces. The floor under every comparison sort is a floor nobody can get under. This is a floor the structure ends up at.

The two do have something in common and it is the thing this essay is about. The floor moves when the question does makes the case that a lower bound is a function of what is being asked, and quoting one without its question is quoting half of it. The same is true here in a different variable: the settled floor is a function of the table’s share of the key space, and quoting one without that is quoting half of it too. Both are cases of a number that reads as a property of a structure and is a property of a structure and a situation.

The bill a partition only divides shows the two structures’ damages summing to the sum of the shard floors — an exact conservation, and one whose terms are now known to be regime-dependent quantities. The conservation survives, because both sides are computed from the same floors; what moves is what those floors are worth.

The share does not collapse the two columns #

The interchangeability claim above is checked against the noise of one stream and flagged as weak because mass confounds it. The confound is removable: divide each floor by its shard’s arrivals and the first variable is gone, leaving a quantity that should depend on the share alone if the share is the whole story.

Under round-robin, floor per arrival runs 0.0220, 0.0229, 0.0234, 0.0238, 0.0240, 0.0241, 0.0242, 0.0242 across the eight shard sizes — flat to within ten per cent, which is the same fact as the exponent of 1.018.

Under hashing it runs 0.0003, 0.0045, 0.0083, 0.0116, 0.0150, 0.0180, 0.0212, 0.0242 — a factor of seventy-six, which is the crossover.

Now put them on the share instead. Hashing holds distinct keys at 0.078 an arrival throughout, so the shares are 1.31, 0.66, 0.33, 0.16, 0.082, 0.041, 0.021, 0.010, and the two columns can be read against each other wherever the shares meet.

At the largest shard both partitions are the same object and both read 0.0242 at a share of 0.010, which is a consistency check rather than evidence. The informative comparison is at the round-robin sweep’s small end: a share of 0.21, at which round-robin’s floor per arrival is 0.0220. Interpolating the hashed column between its 0.16 and 0.33 points puts hashing’s value at that share near 0.011.

A factor of two apart, at the same share. So the share is a necessary second variable and it is not a sufficient one, and the two knobs are not interchangeable after all — the check that found them “interchangeable to within the noise” was comparing configurations whose masses differed by enough to hide it.

The mechanism is visible once the two partitions are described as operations on a histogram rather than on a stream. Round-robin thins every key’s count by $m$ and keeps every key. Hashing keeps every count intact and discards all but one key in $m$. Both leave the table holding thirty-two counters against a similar number of distinct keys, so both produce the same share — and they have done completely different things to the tail the fixed point is computed over.

A thinned histogram has the global shape with every atom shortened, so its tail is many tiny counts. A subsampled one has a random handful of the global atoms at full height, so its tail is fewer, larger counts. The fixed point divides tail mass among churning slots, and those two tails divide differently at equal mass and equal count.

Which is exactly the sentence the section below reaches for and states as a caution rather than a result: the shape of the resulting histogram is what decides how the floor responds. It is not a fourth variable waiting on a Zipf exponent — it is a third variable already separating two columns on this page, and the floor a histogram already knows computes from the histogram directly and is therefore right about both without needing to name any of them.

The negative that survives is the one the essay is for, strengthened rather than weakened. A floor is not a function of the arrivals; it is not a function of the arrivals and the share either; and every quantity that would pin it down is a thing the partition the analysis did not mention sets without being asked.

What is left open #

The crossover has no closed form here. What is measured is that it exists, where it sits for this stream and this width, and what its two ends look like. A treatment that predicted the shape of the curve — rather than declining to fit a line to it — would need the Zipf exponent as a fourth input, and the whole point of the fixed point is that it works from a histogram rather than from a fitted distribution.

And nothing here measures a stream that is not Zipf. The 0.078 distinct-keys-per-arrival constancy under hashing is a consequence of hashing splitting the universe uniformly, which holds for any key distribution; the shape of the resulting histogram is what decides how the floor responds, and a uniform key distribution would put the crossover somewhere else entirely.

What is robust is the negative and it is the one the next essays rest on: a floor is not a function of the arrivals alone, one partition on this site holds the second variable nearly still and one moves it across a crossover, and every earlier statement about floors on this site was made under the first.