The estimate that squares the stream

A stream of keys goes past once. Three questions about it, in order of how obvious the answer is.

How many items were there? A counter. One register, exact, and an approximate one is smaller still.

How many distinct keys were there? Not a counter — a counter cannot tell a repeat from a new arrival — but a bank of small registers reading the leading zeros of a hash gets within two per cent of it in a few kilobits.

What is the sum of the squared frequencies? There is nothing to count at all.

Write $f_x$ for the number of times key $x$ occurred. The three questions above are $F_1 = \sum_x f_x$, $F_0 = \sum_x [f_x > 0]$ and $F_2 = \sum_x f_x^2$, and the third is the one this essay is about. The obvious route to it needs every $f_x$, which is a counter per distinct key, which is the thing the field exists not to do.

What the second moment is a measurement of #

$F_2$ has three names in three literatures and they are the same quantity.

To a database it is the self-join size: the number of pairs $(i, j)$ of stream positions carrying the same key, which is exactly what a join of the stream with itself produces and exactly what a query planner needs to estimate before it commits to a plan.

To a statistician it is the index of coincidence: the probability that two positions drawn at random hold the same key is $F_2 / F_1^2$, give or take the sampling-without-replacement correction.

To anybody who has to size anything it is the skew. A uniform stream over $u$ keys has $F_2 = F_1^2/u$; a stream where one key takes everything has $F_2 = F_1^2$. The ratio between the two is $u$, and where a real stream sits between them decides whether a hash-partitioned workload balances or one worker gets everything.

On the stream measured throughout this essay — 60,000 items over a universe of 2,048 keys, Zipf with $s = 1.1$ — the numbers are $F_1 = 60{,}000$, $F_0 = 2{,}004$ and $F_2 = 153{,}983{,}342$. That last is $0.0428 \cdot F_1^2$, against $1/2004 = 0.0005$ for a uniform stream on the same keys: this stream is eighty-six times more concentrated than a flat one, which is a fact about it no counter of items or of distinct keys reports.

The last row is there because the family does not continue indefinitely. $F_\infty = \max_x f_x$ has no one-pass estimator with a useful guarantee at all, and the reason is the same counting argument that floors the exact distinct count: a summary small enough to be interesting cannot distinguish a stream whose heaviest key occurred twice from one whose heaviest key occurred once, when the rest of the stream is the same. Every moment between 0 and 2 has an estimator in polylogarithmic space and every moment above 2 needs polynomial space, which is one of the sharper results in this subject and is quoted here rather than demonstrated.

The price of the obvious method #

Keeping a counter per key is not absurd. It is $F_0$ counters, each wide enough for the largest frequency, plus a key beside each. Here that is 2,004 keys at 32 bits with a 14-bit counter each: 92,184 bits, or eleven and a half kilobytes, and the answer is then exact.

The estimator below reaches 4.3% of the right answer in 20,480 bits and 17.5% in 1,280 — a fortieth and a seventieth of what the exact method costs. That is the trade, and as usual on this site it is stated as two numbers rather than as an adjective.

One number, one sign per key #

Here is the whole algorithm. Draw a function $s$ that assigns every key a $+1$ or a $-1$. Keep one register $Z$, initially zero. When key $x$ arrives, add $s(x)$ to it. At the end, report $Z^2$.

That is Alon, Matias and Szegedy’s estimator, and the reason it works is one line of algebra.

$$Z = \sum_x s(x) f_x, \qquad Z^2 = \sum_x f_x^2 + \sum_{x \neq y} s(x)s(y) f_x f_y$$

The first sum is $F_2$. Every term of the second contains $s(x)s(y)$ for two distinct keys, and if the two signs are independent and each is $\pm 1$ with equal probability, that product has expectation zero. So $\mathbb{E}[Z^2] = F_2$, exactly, at every stream length and on every stream.

The estimator does not know the frequencies and never assembles them. It sees each arrival once, adds one number, and the squaring at the end reconstitutes a sum over keys that were never separately represented.

One register is hopeless and unbiased, at once #

Unbiasedness is a statement about the mean over draws of the hash family. It says nothing about any particular run, and the particular runs here are dreadful.

Two hundred draws of a single register over the same stream: the mean error is 10.7%, which is inside the noise of two hundred samples, and the root-mean-square error is 105%. The worst single run was 317% high. Ninety-two of the two hundred came back below the truth and one hundred and eight above.

The variance is what makes this so. $Z^2$ is the square of a sum of $\pm 1$ terms weighted by frequencies, and when the analysis is carried out the bound is $\mathrm{Var}[Z^2] \le 2F_2^2$ — a standard deviation of the same order as the answer. Nothing about that improves as the stream lengthens: it is a relative variance and it is constant.

Two mechanisms, doing two different jobs #

The repair is the construction this site measured one field ago, and the reason it comes in two halves is that a mean and a median fail differently.

Averaging $s$ independent registers divides the variance by $s$. That is what an average of independent things does, and it is the only reason more state helps at all. It moves the typical error and does nothing to the shape of the tail.

Taking the median of $g$ such averages cuts the tail. For the median of $g$ independent estimates to be far out, more than half of them must be far out, and the probability of that falls exponentially in $g$ while each estimate’s own failure probability stays put.

The product $s \cdot g$ is the number of registers, and it can be split between the two mechanisms in any proportion. Which split is right depends on whether the question is “how wrong is a typical answer” or “how often is an answer badly wrong”, and those are different questions with different answers.

What it costs, measured #

At sixteen registers per group and five groups — eighty registers, 2,560 bits — the estimator sits at 12.3% root-mean-square error over twenty-four draws. At 640 registers and 20,480 bits it is at 4.3%. The exact method on the same stream is 92,184 bits.

Four halvings of the error for sixteen times the state, which is the $1/\sqrt{m}$ law again and is the shape every estimator in this field climbs.

The state falls and the work per item rises #

The plate above has bits on its horizontal axis and that is not the only resource being spent.

Every arrival is shown to every register. At 640 registers that is 640 hash evaluations per item, and over a stream of 60,000 items it is 38.4 million — against a Count-Min sketch’s four per item, or 240,000 for the same stream. The two structures hold comparable numbers of bits and differ by a factor of a hundred and sixty in the work they do to fill them.

This is the same two-counts situation the site opened with, one field along: comparisons and cache misses rank algorithms differently, and here bits and hash evaluations do. A plot of accuracy against state is an honest plot and it is not the whole account, which is why Summary counts hashes beside updates and why the number appears in this section rather than being left for a reader to infer.

The repair is structural rather than a matter of tuning, and it is Count-Sketch: hash each key to one register out of $w$ rather than showing it to all of them, and the work per item drops to the number of rows while the variance argument survives nearly intact. That is three essays on from here, and it is the reason nobody runs the plain estimator above in production.

What the estimator does not answer #

It gives $F_2$ and it gives nothing else. In particular it will not answer a question about any individual key: there is no way to interrogate $Z$ about $x$, because $Z$ is one number and every key contributed to it.

That is not a defect to be repaired but the reason the structure is so small. A Count-Min sketch answers per-key questions and costs a table; this costs a register and answers one question about the whole vector. The state a summary needs is decided by the set of questions it must answer, and it is worth knowing which of the two a structure is before comparing their sizes.

There is a bridge between them, and it is in the next essay but one: a Count-Sketch is a table of these registers with a hash deciding which register each key lands in, and the same table answers both kinds of question.

The model, stated #

Every number above is a measurement in the cash-register model: one pass, every update an insertion of one, nothing expires, and the hash family behaves as its analysis assumes. The previous phase of this field measured a dozen structures and never wrote that sentence down, and the four essays after this one are what happens when each of its clauses is removed.

The first clause is enforced rather than described, as it was before: the update sequence is wrapped so that a second iteration throws, and every summary here is fed through the wrapper. The last clause is not an assumption this site is willing to leave standing, and the next essay measures what it is actually worth.

Why the bound is loose, and by how much #

$\mathrm{Var}[Z^2] \le 2F_2^2$ gives a relative standard deviation of at most $\sqrt{2}$ for one register, so the average of $s$ of them should be within $\sqrt{2/s}$. At sixteen registers that is 35%; the measured spread of that configuration is 22%.

The bound is an upper bound and it is loose here by a factor of 1.6, for a reason that is visible in the algebra. The variance term is $\sum_{x \neq y} f_x^2 f_y^2$ multiplied by a constant, and it is largest when the mass is spread evenly across keys. This stream is skewed — its top key carries 17% of the items — so most pairs $(x, y)$ contribute far less than the worst case allows.

That is the fourth time this site has recorded the same shape: a permitted failure rate that nothing breached, a probe formula whose independence assumption is false and whose prediction holds, and a bound with a precondition nobody checks. A bound is a statement about the worst input, the input at hand is not the worst one, and the gap between them is a measurement rather than a disappointment.

The number a system actually wants #

$F_2$ is a large integer whose magnitude means nothing on its own — 153,983,342 is not a quantity anybody has intuition about. Divided into the square of the stream length it becomes a number that is immediately useful, and it is the form the third reading above should be quoted in.

$$\frac{F_1^2}{F_2} \;=\; \frac{60{,}000^2}{153{,}983{,}342} \;=\; 23.4$$

That is the effective number of keys: the number of equally-frequent keys a stream would need to have this much concentration. This stream has 2,004 distinct keys and behaves, for every purpose that depends on mass rather than on identity, like a stream of twenty-three.

The quantity is the reciprocal of the index of coincidence, it is Simpson’s index in ecology and the inverse participation ratio in physics, and it is what makes $F_2$ actionable. Two consequences follow directly and neither needs any further measurement.

A hash partition over more than twenty-three workers cannot balance this stream. The heaviest key alone carries 17% of the items, so whichever worker it lands on receives at least 17% of the load however many workers there are — and the effective key count says the whole distribution behaves like twenty-three units of mass, so splitting it sixty-four ways leaves most workers nearly idle and a few carrying everything. Sizing a partitioned pipeline from $F_0$ — two thousand distinct keys, so surely sixty-four workers is fine — is sizing from the wrong moment.

And the join estimate follows from the same number. A self-join produces $F_2$ pairs, so a plan that assumes uniformity would predict $F_1^2/F_0 = 1.8$ million pairs and the truth is 154 million — eighty-six times more. A query planner that got that wrong by eighty-six times has chosen the wrong join order and will find out during the query.

So the useful output of this estimator is a ratio and not a sum, and the ratio is available from two quantities the pipeline is almost certainly measuring anyway: the item count, which is a counter, and $F_2$, which is this essay.

And how accurate it has to be #

Having the ratio also settles how much state to spend, which the accuracy sweep on its own does not.

The decisions above are decisions about an order of magnitude. Whether the effective key count is 23 or 27 changes nothing about how many workers to provision; whether it is 23 or 230 changes everything. A relative error of 17.5% on $F_2$ — the cheapest row in the table, 1,280 bits — propagates to about the same relative error on the ratio, which distinguishes 23 from 230 with enormous margin and distinguishes 23 from 27 not at all.

So the cheap configuration is the right one for this use, and the expensive one is buying resolution that no downstream decision consumes. That is the reverse of the usual reading of an accuracy sweep, where the rightmost point looks like the good one.

The general form is the question this collection keeps arriving at from different directions: what decision is the number for, and what is the smallest difference that would change it? Asked that way the sizing is arithmetic. Asked as “how accurate should the sketch be”, it has no answer, and the answer people give is whatever their memory budget allowed.

The honest limit #

Two things are worth saying plainly about what has been established here.

Unbiasedness was asserted and is checked, and the check is weak. The mean of two hundred single-register estimates was 10.7% high; the standard error of a mean of two hundred draws from a distribution with a relative standard deviation of one is 7%. So the measurement is consistent with the estimator being unbiased and would also be consistent with a small bias. The gate takes four hundred draws of a low-variance configuration instead, where the same test is sharper by a factor of five — and even that could not detect a bias of one part in a thousand.

The variance claim is where the interesting failure lives, and it is not tested by any of the above. Every number in this essay came from a family of a stated degree of independence, and the reason that phrase is in the caption of every plot is that the estimator’s mean and its variance consume different amounts of the same resource. The mean survives on very little. The variance does not, and a family that is too weak produces an estimator that is still centred on the right answer and whose error stops falling when it is given more registers.

That is the next essay, and it is the one where the resource being spent is finally measured rather than named.