The floor a histogram already knows

Every error a bounded-space counter table makes is the same number wearing two hats. A Space-Saving summary of $k$ counters overestimates by at most its smallest counter; a Misra-Gries summary of the same width underestimates by exactly the number of decrement rounds it performed. Two structures that are one showed those are the same structure separated by a single subtraction, and the two quantities move together for that reason.

So one number decides the accuracy of both. It is called the floor here, and until now the only way to know it has been to run the structure.

The number, and why it is the only one #

The floor is not a diagnostic. It is the entire error term, and it is worth restating why before anything is predicted about it.

Space-Saving’s counters sum to exactly the number of arrivals: every arrival either increments a counter that exists or evicts the smallest and installs the new key at the smallest counter’s value plus one. Nothing is created and nothing is lost, so the table is a partition of the stream’s mass across $k$ slots. A key held by the table has a counter equal to its own arrivals plus whatever it inherited from the keys evicted before it, and that inheritance is bounded by the smallest counter present at the time.

Which gives the guarantee the counter that takes the smallest slot is built on: the counter is never below the truth, and it is above by at most the floor. A key not held by the table has arrived at most floor-many times, because otherwise it would have displaced the smallest counter.

Misra-Gries reads the same table with the floor subtracted. Its shortfall for any key is the number of decrement rounds it ran, and its guarantee — never above the truth, below by at most that count — is the mirror image.

The consequence is that a great many questions about these structures are questions about one scalar. How wrong is the answer. How much worse a merge is than a single pass. Whether widening the table is worth the memory. Every one of them reduces to what does the floor come out at, and every one of them has been answered here by running the thing.

The obvious estimate, which is wrong by a factor of two #

There is a natural way to compute the floor without running anything, and it follows from the mass argument above in one line.

The table holds $k$ keys. If those are the shard’s $k$ heaviest, they account for a known share of the arrivals; call what is left over the tail mass. The counters sum to the total, the held keys’ own arrivals account for everything but the tail, so the errors carried by the table sum to the tail mass. Divide by $k$ and the average error is the tail mass over $k$. The floor, being the smallest counter, ought to be near that.

On the shards above, the tail mass runs a little over two thousand arrivals and $k$ is thirty-two, so this estimate lands between 65 and 70. The measured floors are between 118 and 123. The estimate is low by a factor of about 1.8, on every shard, in the same direction.

A discrepancy that consistent is not noise; it is a term left out. And the term is visible in the guarantee itself: the heavy counters carry no error at all. The most frequent key entered the table before it was full, was never the smallest, and was therefore never evicted. Its counter is exact. So is the second key’s, and the third’s. Those slots hold none of the tail mass, and dividing by $k$ shares the mass among them anyway.

The fixed point #

The mass is shared among the slots that churn — the ones whose key is light enough to be evicted and replaced. A slot churns when its key’s frequency on this shard is below the floor. Which means the count of churning slots depends on the floor, and the floor depends on the count of churning slots.

That is a fixed point, and it is solved the way fixed points are:

$$\varphi \;=\; \frac{\text{mass of every key whose shard frequency is at most } \varphi}{\#\{\text{slots in the top } k \text{ whose key's frequency is at most } \varphi\}}$$

starting from zero and iterating. Each step recomputes which keys are safe at the current estimate, recomputes the mass the unsafe ones have to share, and divides.

The convergence is quick and the destination is right. On the eight shards of the plate at the head of this essay the fixed point returns 119.6, 120.9, 120.3, 120.6, 118.9, 123.6, 121.0 and 122.3; the structures settle at 119, 120, 120, 120, 118, 123, 120 and 121. That is within one arrival on every shard, from a histogram.

The count it settles at is as informative as the value. Twenty-six or twenty-seven of the thirty-two slots churn; five or six hold keys that are never evicted. The naive estimate is wrong by the ratio $32/26.5$ — a factor of 1.2 — plus a second factor of the same size from the mass that the safe keys’ own arrivals remove from the tail. Multiplied, that is the missing 1.8.

Six counters out of thirty-two are doing something different from the other twenty-six, and no summary of the structure says so. The bound is stated for all $k$ slots uniformly, and the slots are not uniform.

The same arithmetic, on a partition that changes everything #

A shard is not a stream that somebody chose; it is what a partition made. The partition the analysis did not mention established that the same arrivals split two ways give a structure two completely different problems, and the floor is where that shows up first.

Under round-robin every shard sees a scaled copy of the whole stream: about eleven hundred distinct keys, the same key ranking, one eighth of every frequency. The floors are consequently almost identical — 118 to 124 across eight shards.

Under hashing the shards are not copies of anything. One of them holds sixteen thousand arrivals and another two thousand, because the heaviest key went somewhere and its neighbours went elsewhere. Each shard sees about four hundred distinct keys instead of eleven hundred, so its top thirty-two covers far more of its own mass, so its tail is smaller — and its floors run from 62 to 96 rather than from 118 to 124.

The prediction lands on all sixteen of those numbers, which is the point. It is not a rule of thumb calibrated on one arrangement. It is the same conservation argument, applied to whichever histogram the partition produced.

What it is worth, and where the confidence runs out #

A predicted floor is not an end in itself. It is the input to every merge question this collection has been asking, because a merge’s damage is built out of shard floors and nothing else — which is the subject of the bill a partition only divides.

But it is worth stating plainly what the prediction costs and what it buys. It costs one pass over a frequency table, which is arithmetic on a histogram anybody planning a deployment already has or can sample. It buys the answer to how wrong will this be for a structure that has not been built, at a width that has not been chosen, under a partition that is still an argument in a design review.

The confidence runs out somewhere, and the place is worth finding on purpose rather than being surprised by.

On the stationary stream the ratio is 1.004, 1.006 and 1.016 at widths of sixteen, thirty-two and sixty-four. On a stream where one key floods a short stretch and is otherwise absent it is 1.047, 1.029 and 1.032 — slightly high, and still inside anything a capacity decision would care about.

On a stream whose popular keys drift, it is 1.127, 1.351 and 1.420. The prediction overshoots, it overshoots more as the table gets wider, and it does so for a reason that is structural rather than statistical.

A histogram has no order in it. The fixed point asks which keys are heavy on this shard, and on a drifting stream the answer is different keys at different times. A key that was the second-heavest for the first eighth of the stream and absent afterwards is, in the whole-shard histogram, a middling key that belongs to the tail — so its arrivals are counted as churn. They were not churn when they happened. The structure was holding that key, exactly, and it cost nothing.

So the model overcharges, and it overcharges more at larger $k$ because a wider table holds more of those temporarily-heavy keys and the histogram misclassifies more of them. That failure is worth an essay of its own and gets one in the histogram that cannot see the order, together with a statistic that says in advance whether it is about to happen.

The naive estimate is not merely imprecise #

One last note on the estimate that was discarded, because there is a version of this argument in which it survives as a rough guide and that version is wrong.

The naive estimate is not a slightly-too-low approximation of the floor. It is a different quantity: the mean error per slot, which is a real number about the table and is not the bound. The bound is set by the smallest counter, and the distribution of counter errors is bimodal — a handful of exact ones and two dozen sitting near the floor — so the mean is nowhere near the maximum and nothing about the mean constrains it.

That is the same mistake, one level down, as quoting a mean occupancy for a structure that will be sized from its peak. Distributions, not averages is a habit here rather than a slogan, and the reason it keeps earning its place is that the summary statistic is nearly always the one that is cheap to compute rather than the one the decision needs.

The fixed point is not more accurate arithmetic on the same idea. It is arithmetic on a different idea: which slots are in play. Six counters out of thirty-two are not, and finding out how many takes an iteration because the answer is defined in terms of itself.

At $k = 64$ on a stationary stream the fixed point returns 52.3 against a measured 51.5, and the naive estimate returns 27.6. The ratio between the careful answer and the crude one has barely moved: it is 1.90 at sixteen counters, 1.79 at thirty-two and 1.89 at sixty-four. Whatever the naive estimate is measuring, it is not converging on the floor as the table grows.

A width is chosen against this number #

The practical form of the question is not what is the floor but how wide does the table have to be, and that is the same question inverted.

A summary is bought to answer a heavy-hitter query with some tolerance — report every key above a share of the stream, and do not report anything below it. One pass and k slots sets out the classical sizing rule, which is $k = 1/\phi$ for a threshold $\phi$ and is a statement about the worst case over all streams. It has to be, because the rule is asked to hold whatever arrives.

The fixed point answers the same question about the stream in hand. Sweeping $k$ and reading off the floor gives the tolerance each width actually delivers on this distribution, and on a Zipf stream that is far better than the worst-case rule promises: at $k = 64$ the floor is 52 arrivals out of five thousand, a little over one per cent, where the general rule would want $k$ near a hundred for the same guarantee.

That difference is the constant the classification discards, and measuring it rather than reciting it is the whole of what the constant the notation drops argues for. The general rule is not wrong; it is a bound over a family of streams, and a deployment runs one of them.

There is one more reason to want the number in advance, and it is the reason measuring what an algorithm keeps exists. Space and accuracy here are one dial, and a dial with an unknown response is not a dial anybody can turn. Being able to say thirty-two counters buys an error of 120 arrivals on this stream and sixty-four buys 52 is a different kind of engineering from doubling the allocation and rerunning.

Doubling the table more than halves the floor #

The sizing question has a shape as well as an answer, and the two measured widths give it. At $k = 32$ the floor is 120; at $k = 64$ it is 52. That is a factor of 2.31 for a doubling, and the excess over two is not noise — it is the term the worst-case rule does not have.

The fixed point says the floor is a tail mass divided by a churning-slot count. The churning count is very nearly $k$, since the safe slots are a handful. The tail mass on a Zipf-distributed shard over a universe of $U$ keys is the mass beyond rank $k$, which for an exponent near one is proportional to $\ln(U/k)$ rather than to a constant. So

$$\varphi \;\propto\; \frac{\ln(U/k)}{k},$$

and doubling $k$ divides the floor by $2\cdot\ln(U/k)/\ln(U/2k)$. At $U = 2{,}048$ that is $2 \times \ln 64 / \ln 32 = 2.40$ against the 2.31 measured — the shape recovered from the distribution, with the small shortfall coming from the safe slots the numerator is not quite free of.

So the returns to width are superlinear while $k$ is well below $U$. That is a stronger statement than the essay’s observation that the classical rule is loose, because the two disagree in the exponent rather than in a constant: $k = 1/\phi$ asserts $\varphi \propto 1/k$ exactly, and the measured stream delivers better than that at every doubling. The gap therefore widens rather than staying put — the rule wants 42 counters where 32 suffice and 96 where 64 do, so the ratio between what is demanded and what is needed goes from 1.31 to 1.50 as the table grows.

Two consequences for a deployment.

Widening is the cheapest lever available, and it is cheapest exactly where somebody would hesitate. A doubling of memory that bought a halving of error would be an ordinary trade; one that buys 2.3 times is not, and the extra comes from a term — the logarithm of the universe over the width — that nothing in the structure’s own bound mentions.

And the lever runs out, predictably. The logarithm goes to zero as $k$ approaches $U$, which is the table holding every distinct key and making no error at all. So the superlinearity is a property of the regime $k \ll U$ and it decays smoothly out of it; a shard with four hundred distinct keys under hashing is much closer to that ceiling than one with eleven hundred under round-robin, which is a second way the partition decides what a width is worth.

Neither of those is visible from a bound quantified over all streams, and both fall out of a histogram. That is the same argument the items that survive k counters makes about which keys a table holds, extended from the membership question to the accuracy one — and it is another instance of a count somebody chose turning out to be the parameter the whole behaviour is a function of, chosen before anything about the stream was measured.

What is now computable #

Three things, none of which needed a structure.

The floor of any shard, at any width. One histogram, one iteration, and an answer within one per cent on a stream whose distribution holds still.

The number of counters that are actually in play, which is a description of the table nothing else here provides and which turns out to be most of the explanation for why the obvious estimate fails.

A warning, in the ratio the last two plates draw. The failure on the drifting stream is not a small residual to be tolerated: at $k = 64$ the prediction is 42% high, which would size a structure wrongly in a way that looks careful. Knowing that the method has a precondition — the shard’s favourites hold still — matters as much as the method, and the precondition is measurable from the same histogram.

Which is the shape this collection keeps finding. A limit is not a prediction made the point about asymptotic notation and it applies to this arithmetic too: what has been computed here is a description of a measured range, checked against measurement, with the case it refuses stated in the same breath. The next essay takes the floor and builds both merges out of it.