The moments past the second

The estimate that squares the stream estimated the second frequency moment, $F_2 = \sum_x f_x^2$, with one register. Each key gets a random sign, the register adds up the signed arrivals, and the estimate is the register squared. The cross terms between different keys cancel in expectation because the signs are independent, and what survives is exactly $\sum_x f_x^2$.

The other two questions a stream answers cheaply have their own instruments: its length needs a counter, and its number of distinct keys a bank of registers reading leading zeros. Nothing like the sign trick works for the third moment. Cubing a signed sum leaves cross terms of the form $f_x^2 f_y$, and no choice of signs makes them vanish in expectation while keeping $\sum f_x^3$. The moments past the second have no one-register trick, and they are not exotic: $F_3$ measures how concentrated a stream is more sharply than $F_2$ does, and the high moments are what a skew estimate for load balancing is built from.

Alon, Matias and Szegedy gave a different estimator in the same 1996 paper that introduced the sign trick, and it works for every $k$. It is older in spirit and simpler. This page computes exactly what it costs.

Pick a position, count what follows #

Choose one position of the stream uniformly at random. Count how many times the key at that position occurs from there to the end, including itself, and call it $r$. Report

$$X = m\,(r^k - (r-1)^k),$$

where $m$ is the length of the stream. In a stream processor the position is chosen by reservoir sampling and $r$ is a counter that restarts when the sample is replaced, so one copy holds one key and one count.

The reports telescope. A key of frequency $f$ occupies $f$ positions, whose $r$ values run $f, f-1, \ldots, 1$, and the differences $r^k - (r-1)^k$ over that run add up to $f^k$. Each position is chosen with probability $1/m$ and reports $m$ times its difference, so the key contributes exactly $f^k$ to the mean. Summed over keys the mean is $F_k$ — for every $k$, on every stream, with no assumption about hashing or independence at all.

The plate also shows where the trouble will be. A key’s first position carries most of its weight: 91 of the 216 for a key seen six times, and for a key seen a thousand times, the first position alone reports $3 \times 10^6$ stream lengths out of a total of $10^9$. Whether the estimator is good depends on how often the rare, heavy reports come up, and that is a property of the stream, not of the estimator.

Its variance is a sum over the stream #

Because the report is a fixed function of the position chosen, the estimator’s whole distribution is the list of $m$ values it would report, one per position, each with probability $1/m$. Its mean and variance are sums over that list, and they can be computed exactly for any stream without drawing a single position.

What follows uses streams of 60,000 items over 2,048 keys, drawn from a Zipf distribution with exponent $s$. At $s = 0$ the stream is flat. At $s = 1.1$ it is the stream the estimate that squares the stream measured, eighty-six times more concentrated than a flat one.

Every curve on the plate has mean exactly one, and they could hardly look less alike. On the flat stream the reports are spread fairly evenly around the moment. At $s = 0.5$, nine positions in ten report less than the truth and a few report tens of times it. At $s = 1.1$ the median position reports half a per cent of the truth, and the mean is made almost entirely of the first positions of a handful of heavy keys.

Where the moment lives explains the difference between the two skewed streams. At $s = 1.1$ the most frequent key occurs 10,186 times, holds 86% of $F_3$ by itself, and occupies 17% of the stream’s positions, so a random position lands on it one time in six. At $s = 0.5$ no key is that dominant. The most frequent occurs 618 times and holds 32% of $F_3$, and it takes the three heaviest keys to make half the moment — keys that occupy only 2.4% of the positions. Half of what the estimator has to find sits in one position in forty, spread across three keys whose early positions report very different amounts. That is the hard case: a moment concentrated in few positions, but not concentrated enough to be in one key.

A single copy of this estimator is therefore almost always an underestimate and occasionally a large overestimate. That shape is what the estimate that is a median of means was built for. Averaging copies narrows the spread, and taking a median of several averages protects against the rare average that caught a heavy report.

The cost depends on the skew, and not in the obvious direction #

The relative variance, the variance of one copy divided by the square of the moment, is the number of copies needed for a relative standard deviation of one, and every copy count below scales from it.

Every moment is cheapest at the two ends of the skew and dearest in the middle. The same exponent was the hard case in the skew a few counters cannot repair, for a different reason: there a series stopped converging at exactly one half. On a flat stream the relative variance for $F_3$ is 1.02. At $s = 0.5$ it is 26. At $s = 2$ it is back below 2.

A flat stream is cheap because every key looks the same. The estimator is then sampling one key’s run, and a run of length $f$ has the same shape whichever key it belongs to. For large $f$ the relative variance tends to $k^2/(2k-1) - 1$: 0.33 for $F_2$, 0.8 for $F_3$, 1.29 for $F_4$. A stream dominated by one key is cheap for the mirror-image reason: nearly every position belongs to that key, and again one run is being sampled.

In between, the stream is a mixture of keys of very different weights, and the estimator’s value depends on which kind of key it lands on. Exactly, to leading order, the relative variance is

$$\frac{k^2}{2k-1}\cdot\frac{F_1\,F_{2k-1}}{F_k^2} - 1,$$

and the ratio in the middle is a measure of how unequal the frequencies are, as seen by the $k$-th moment. It is one for a flat stream and one for a single-key stream, and at $s = 0.5$ for $k = 3$ it is 15.2. The formula reproduces every value on the plate to two decimal places.

The second moment shows how differently two unbiased estimators can behave on the same stream. On a flat stream the sampling estimator’s relative variance for $F_2$ is 0.38 and the sign estimator’s is 2.00, so sampling is five times better. From $s = 0.5$ upwards it is worse, and at $s = 1.1$ it is three times worse. The sign estimator’s variance, $2(F_2^2 - F_4)$ for four-wise independent signs, is never more than twice the moment squared on any stream. The sampling estimator’s can be far larger, and the next plate says how much larger it can be.

The guarantee, and the stream that earns it #

The published guarantee on one copy’s relative variance is $k \cdot n^{1-1/k}$, where $n$ is the number of distinct keys. It follows from the inequality $F_1 F_{2k-1} \le n^{1-1/k} F_k^2$, which is the frequency ratio in the formula above, bounded over all streams on $n$ keys. At 2,048 keys and $k = 3$ the guarantee is 484: more than eighteen times the worst Zipf stream on the plate above. So the question is whether any stream comes near it.

It does. Take $n - 1$ keys seen once each and one key seen $h$ times. Search over $h$, and the variance is largest when $h$ is about $1.7\, n^{1/k}$ — 43 at 16,384 keys and $k = 3$. At that $h$ the relative variance is 472, a quarter of the guarantee, and it keeps that quarter at every size on the plate. The slopes of the solid and dashed lines are identical.

So the guarantee’s shape is right, and its constant is loose by only a factor of four. The $n^{1-1/k}$ copies the analysis asks for are genuinely needed on some streams. The stream that needs them is not exotic either: a stream of mostly distinct keys with one moderately repeated key is what an event log with one chatty source looks like. What makes it expensive is the size of the heavy key: frequent enough to dominate $F_k$, and rare enough that a random position almost never lands on its first occurrence.

Why that stream, and why a quarter #

The heavy key’s frequency and the factor of four both come out of the formula for the relative variance, so they are predictions rather than fitted numbers.

On the stream of $n - 1$ singletons and one key seen $h$ times, $F_1 \approx n$, $F_{2k-1} \approx h^{2k-1}$ and $F_k \approx n + h^k$. Write $h^k = c\,n$, so that $c$ says how much of the moment the heavy key holds against the singletons. The frequency ratio becomes

$$\frac{F_1 F_{2k-1}}{F_k^2} \approx \frac{c^{\,2-1/k}}{(1+c)^2}\; n^{1-1/k},$$

which grows as $n^{1-1/k}$ whatever $c$ is. That is the guarantee’s growth, and it is why the plate’s two sets of lines are parallel. Maximising over $c$ gives $c = 2k - 1$: the worst heavy key holds $2k - 1$ times as much of the moment as all the singletons together. At $k = 3$ that is a frequency of $(5n)^{1/3} \approx 1.71\,n^{1/3}$, and the search found 1.7.

Putting $c = 5$ back in and multiplying by $k^2/(2k-1)$ gives a relative variance of $0.73\,n^{2/3}$ at $k = 3$, against the guarantee’s $3\,n^{2/3}$ — a ratio of 0.244. The plate measured 0.243 and 0.244. The factor of four between this stream and the guarantee is exact to the arithmetic, and it comes from the one inequality in the analysis that is not tight.

This is the gap that later algorithms closed. The best known space for $F_k$ with $k > 2$ grows as $n^{1-2/k}$ rather than $n^{1-1/k}$ — Indyk and Woodruff’s algorithm, 2005 — and a matching lower bound shows no algorithm can do much better. The sampling estimator is a factor of $n^{1/k}$ off that. At $k = 3$ on 2,048 keys that is the guarantee’s 48,381 copies against $n^{1/3} \times 100 \approx 1{,}300$ for the better algorithms, before their constant factors and logarithmic terms, which this page does not measure.

What it spends instead of independence #

The independence an estimator spends measured how much independence the sign estimator’s hash family must have. Its mean needs pairwise independence and its variance four-wise, and a family that falls short gives a biased or unstable answer on streams chosen against it.

The sampling estimator needs none of that. Its only randomness is the choice of position, which reservoir sampling makes with one random number per item it considers — the bits counting the coin flips charged it for. The unbiasedness above holds for any stream at all, including one chosen by an adversary who knows everything but the random choices. There is no hash to attack.

What it pays for that is the variance on the plates, and a structural limitation. A sign sketch is linear: its state is a sum of updates, it can be merged with another sketch by adding, and a deletion is an update with a minus sign. The sampling estimator’s state is a position and a count, so two copies cannot be merged into one, and a deletion of an item after its position was sampled has nowhere to go. The two estimators are not rivals on one scale. They differ in what they assume about the stream, and in what they do when the assumption fails.

Copies for ten per cent #

The plate is the practical content of everything above. Each copy holds one key and one counter, about 27 bits at this size. A thousand copies is a few kilobytes, and at that size $F_3$ comes out to ten per cent on the flat and Zipf 1.1 streams. On the moderately skewed stream it takes 2,630 copies, and to be safe on any stream a designer who knows nothing about it must provision the guarantee’s 48,381.

Two gaps on the plate have different meanings, and they should not be confused. The gap between the worst stream and the guarantee, a factor of four, is slack in the analysis. The gap between the Zipf streams and the worst stream, a factor of four to seventeen at $k = 3$, is a property of the data. A system that knows its streams are Zipf-like can provision for that and save most of the memory; a system that promises a bound cannot.

The growth with $k$ is steep in the guarantee and in the worst stream, and mild on the Zipf streams. From $F_3$ to $F_6$ the guarantee rises sevenfold. The flat stream’s requirement rises fivefold, and the Zipf 1.1 stream’s only two and a half times, because on a stream whose heavy keys are very heavy, a higher moment is dominated by fewer keys and becomes easier to sample, not harder.

What drawn copies actually do #

Everything so far has been computed. The last plate draws positions at random, as a stream processor would, and checks the computation against them.

The draws average within two per cent of the truth, as they must, and their standard deviation is 0.335 against the exact 0.320 — four hundred means estimate a spread to within about four per cent, and this one is within five.

What the normal curve does not match is the shape. Even a mean of 256 copies is skewed. Its median sits below the truth, 54% of the means are underestimates, and the right tail runs further than the curve’s. The central limit theorem is working, but slowly, because the positions it averages are themselves so skewed that a few heavy reports decide each mean. This is the case for a median of means rather than a plain mean, and it is the point the words “on average” are not a number made about quicksort. The plain mean is unbiased, but its typical value is low, and a system reading one mean will usually be told the stream is less concentrated than it is.

What is exact and what is not #

The variances on every plate but the last are exact for the streams drawn: sums over the 60,000 positions, with no sampling. The estimator’s mean equals $F_k$ to the precision of the arithmetic on every stream and every $k$ measured. The guarantee holds on every stream measured, and the heavy-among-singletons family comes within a factor of four of it at every size.

What is not measured: the space of the better algorithms is quoted, not built here, and so is the lower bound. The worst stream is the worst of one shape, searched over one parameter. A stream of a different shape could come closer to the guarantee, and the factor of four is a floor on the guarantee’s slack, not its exact value. And every stream is insertions only. The sampling estimator needs positions, and a stream with deletions has no positions to sample from, which is a limitation the sign estimator does not share, since it is linear.

Still open: the estimator that samples keys by their weight #

The sampling estimator wastes its copies on light keys. On the Zipf 0.5 stream most positions report under a tenth of the moment, and each of those copies contributes almost nothing. The fix the better algorithms use is to find the heavy keys first — with a sketch of the kind a sketch that is allowed to be under measured — count them nearly exactly, and sample only the remainder, where no key is heavy enough to dominate.

The measurement that follows builds the simplest version. A Count-Sketch finds every key whose frequency exceeds a threshold, their contributions to $F_k$ are computed from the sketch’s estimates, and the sampling estimator runs on the stream with those keys removed. It sweeps the threshold and asks how the total space — sketch plus copies — compares with the plain sampling estimator on the four streams here and on the worst stream. The prediction is that on the worst stream the heavy key is found and removed, leaving a stream of singletons whose moment the sampler gets almost exactly. The space should then fall from the guarantee’s $n^{1-1/k}$ towards $n^{1-2/k}$, and the question is at what size of stream the sketch’s own cost stops being worth paying.