The keys worth counting before sampling

The moments past the second measured the estimator Alon, Matias and Szegedy wrote for the third and higher frequency moments, $F_k = \sum_x f_x^k$. Pick one position of the stream at random, count how often its key comes again from there to the end, call it $r$, and report $m(r^k - (r-1)^k)$, where $m$ is the stream’s length. Over the $f_x$ positions of a key the reports telescope to $m f_x^k$, so the estimate is exactly unbiased on every stream. Its variance is a sum over the stream and can be computed rather than sampled. On a stream of 60,000 arrivals over 2,048 keys, ten per cent on $F_3$ took 103 copies on a flat stream and 2,630 on a moderately skewed one. On the stream built to be worst for it, 11,799 copies were needed.

Its closing section named where the copies go. On the moderately skewed stream most positions belong to keys whose reports are a tenth of the moment or less, and each of those copies contributes almost nothing. The remedy it proposed was the one the better algorithms use. Find the heavy keys 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. It predicted that on the worst stream the heavy key would be found and removed, leaving singletons the sampler gets almost exactly. It asked at what size of stream the sketch’s own cost stops being worth paying.

The remedy works, and on the worst stream it works exactly as predicted. The answer to the question is not a size.

What a list of heavy keys could hold #

Before any sketch is built, the frequencies themselves say how much there is to find. If a few keys hold most of $F_3$, then removing them leaves a remainder the sampler can handle. If they do not, a list of candidates has nothing to be a list of.

On a flat stream the 64 most frequent keys hold 9% of $F_3$; at a Zipf exponent of one the single most frequent key holds 83% of it. Cubing magnifies every difference in frequency, so the third moment is more concentrated than the stream is. At the exponent the earlier page found hardest for the sampler, 0.5, the top key holds 32% and the top eight hold 71%. That exponent is hard for the sampler for the same reason it is promising here. The moment is concentrated enough that a few keys dominate it, but those keys are a small share of the stream’s positions, so a copy rarely lands on them. When one does, its report is enormous, and that is the variance. A copy that lands on a heavy key reports a number far larger than the moment it is estimating, and one such report in a hundred copies moves the whole average.

The flat stream shows the other side. Its moment is spread over two thousand keys in nearly equal shares, and no list short enough to be cheap holds a useful part of it. The sampler was already cheap there, 103 copies, because a flat stream’s positions all look alike. The skew a few counters cannot repair found the same division in a join estimate: a few counters fix the extreme skews and help nothing in the middle. The difference here is that the middle is where the list helps most.

The estimator, and two ways to read a candidate #

The estimator makes one pass and keeps three things. A Count-Sketch of depth five and width $w$ sees every arrival. Beside it is a list of $K$ candidates: an arriving key whose sketch estimate beats the smallest candidate’s value takes its place. And $c$ copies of the sampling estimator run over the whole stream, because in one pass nobody knows which keys will turn out heavy. At the end, a copy whose key is on the list reports nothing, and the others report as before. The copies then estimate $F_L$, the moment of the keys not on the list, without bias however the list came out, and the heavy part is added from the list.

The heavy part can be read in two ways. Read off the sketch, a candidate’s frequency is the sketch’s estimate at the end of the stream. Counted from entry, a candidate is counted exactly from the moment it joins the list. Its frequency is then the sketch’s estimate on entry plus the arrivals since, so only the arrivals before it was listed carry the sketch’s error. The second costs one more word a candidate. It is the arrangement a count that is never under would have recommended for a key known to matter: once a key is worth asking about, stop asking the table and count it. State is counted in words: a sketch cell is one, a copy two (a key and its count), a candidate two or three.

Only the sketch’s hashing is random. Given the list a pass produces, the sampling part’s variance is exact, as it was on the earlier page. The error of the heavy part is averaged over sixteen sketch seeds, and the two add without a cross term, since the sampling part is unbiased given the list. The width and number of copies are then chosen to make the whole estimator’s relative standard deviation ten per cent in the fewest words.

On the Zipf 0.5 stream, the best estimator reading candidates off the sketch needs 3,282 words; counting them from entry, 1,526. Both beat the plain sampler’s 5,260, but reading the sketch saves 38% of its words where counting saves 71%. The reason is the power. A key’s contribution to $F_3$ is $f^3$, and an error $\delta$ in its estimated frequency becomes an error of about $3f^2\delta$ in the contribution. That is three times the relative error, applied to a term that holds a third of the moment. A sketch accurate enough to give the heaviest key’s frequency to within 1% gives its contribution to within 3%, and the widths that achieve that are expensive. Counting from entry leaves only the first few arrivals of each heavy key to the sketch, when its count was small and its error mattered less.

The number of candidates behaves the same way in both. One candidate removes only the top key’s third of the moment, and the copies left must still cover a stream whose next few keys dominate what is left. Past a handful, each extra candidate removes a key that holds less, while the sketch must grow to tell it from its neighbours. Counted from entry, the bill is nearly flat from eight to sixteen candidates and rises after.

The bill, part by part #

A single setting shows how the three parts of the state pull against one another. With four candidates counted from entry on the Zipf 0.5 stream, only the sketch’s width is left to choose.

Below a width of 128 no number of copies helps: the sketch’s error on the four candidates is already more than the whole estimator is allowed. At width 64 the heavy part alone is 32% out. Copies cannot repair that, because they estimate only the keys that are not on the list. At width 128 the heavy part is 9% out, which leaves almost nothing of the 10% for the sampling part, and 1,819 copies are needed to fit inside what remains. Doubling the width to 256 brings the heavy part to 2% and the copies to 241. Past that, the copies level off at 214 — what the remainder’s spread needs when the heavy part is nearly exact — and the sketch keeps doubling.

The narrowest usable sketch is set by the heavy part’s error, and the best one lies just past it. That is where the copies’ cliff flattens and before the sketch’s own cost takes over. The items that survive k counters found that a deterministic summary of $k$ counters beats a randomised sketch of the same state on the questions both are asked. The error that bounds a heavy-key estimate there, a share of the whole stream, would bound this one too if Misra–Gries replaced the sketch. The difference would be in the sign: its counts are never above the truth, so it would always under-report the heavy part.

Where it pays, and where it cannot #

The sweep over the exponent puts the two estimators side by side on every shape of stream the earlier page measured.

The list costs more than it saves on a flat stream (985 words against 206) and at Zipf 0.25 (1,889 against 676), and saves at every exponent from 0.5 upwards: 3.4 times at 0.5, eleven times at 0.75, twelve at 1, and eight at 2. The two curves cross between 0.25 and 0.5, which is where the top key’s share of $F_3$ rises from a few per cent to a third. Below the crossing, the sketch is paying to find keys that are not there. Even its smallest useful width, 128 cells, is 640 words, more than three times the plain sampler’s whole state on the flat stream.

The shape of the saving is the useful part. The plain sampler’s curve peaks in the middle, where the earlier page found every moment dearest, and the hybrid’s curve has no peak there. It falls from 0.25 onward and is below 200 words from Zipf 1. The heavy keys that made the middle expensive are exactly the ones the list catches, and what they leave behind is a remainder the sampler handles as cheaply as it handles a flat stream.

At the highly skewed end, Zipf 1.5 and 2, the plain sampler was already cheap: one key holds nearly the whole moment, and nearly every position belongs to it. The hybrid is cheaper still. One candidate counted from entry holds 98% of $F_3$ almost exactly, and one to four copies cover the rest. A sketch of width eight is enough to find a key that holds half the stream.

The stream built to be worst #

The earlier page found the plain sampler’s worst stream of one simple shape. It is $n - 1$ keys seen once and one key seen $h$ times, with $h$ near $1.7\,n^{1/3}$: frequent enough to dominate $F_3$, rare enough that a random position almost never lands on its first occurrence. On that stream the sampler needed a quarter of its published guarantee, and the guarantee grows as $n^{2/3}$ for $F_3$.

At 2,048 keys the plain sampler needs 23,598 words and the hybrid, counting its one candidate from entry, needs 940 — and one copy. The prediction held exactly. The heavy key is found, and once it is removed the remainder is 2,047 keys seen once each. Every copy that lands on the remainder reports $m$, so the sampling part’s variance comes only from the copies that land on the listed key and report nothing. That is a share of $h/m$, about 1%. One copy gives the remainder’s moment to within about a tenth of itself, and the remainder is a sixth of $F_3$, so that is under 2% of the whole. The heavy key’s count, known almost exactly, carries the other five sixths.

Across sizes, the plain sampler grows as $n^{0.67}$, from 3,724 words at 128 keys to 94,322 at 16,384, exactly the guarantee’s exponent. The hybrid counted from entry grows fourfold across the same 128-fold range, from 335 to 1,325 words. The best sketch width wanders from 47 to 264 cells, because what sets it is whether a few of the 32 seeds collide the heavy key badly, and that is a matter of luck at every size. The prediction was a fall to $n^{1-2/k}$, which for $F_3$ is $n^{1/3}$. The measurement is consistent with that — the counted curve’s slope over the whole range is 0.28 — but the fluctuations are as large as the trend, and eight sizes do not settle it. Read off the sketch, the bill stays between 939 and 5,284 words with no trend at all. What is certain is the gap: 25 times at 2,048 keys and 71 at 16,384.

So the question the earlier page asked — at what size the sketch’s cost stops being worth paying — has a plain answer on this stream: at none measured. The sketch pays at 128 keys and pays more at every size above. On the flat stream it does not pay at 2,048 keys. It would not pay at any size either, because a flat stream’s plain sampler needs a fixed hundred copies whatever its length, and no sketch is that cheap. What decides whether the list is worth keeping is whether the moment is concentrated in a few keys, and that is a property of the stream’s frequencies, not of its length.

Where the measurement stops #

One moment, one accuracy. Every number is for $F_3$ to a relative standard deviation of 10%. A higher moment concentrates further, so the list should pay from a lower exponent. But the heavy part’s error is multiplied by $k$, so counting from entry matters more. A tighter accuracy squeezes the heavy part’s share of the error budget and pushes the narrowest usable sketch wider.

Words, not bits. A cell, a key and a count are each a word. The estimate that squares the stream priced the second moment’s sketch in bits, and the comparison there was between structures of one kind; here three kinds share a budget, and a word is the unit all three spend. The earlier page’s copies were about 27 bits at this size, and a sketch cell needs as many bits as the stream is long. Counting in bits would move the curves by constant factors and the crossing very little.

Sixteen sketch seeds, thirty-two on the worst stream. The sampling part is exact given the list. The heavy part’s mean square error is an average over seeds, dominated by the occasional seed that collides a heavy key in most rows. That is why the best widths wander, and why the estimator is sized on the mean square error rather than on the typical seed. A sizing on the typical seed would be smaller and would miss its accuracy on the unlucky ones.

The list is greedy. A key enters when its current estimate beats the smallest candidate’s, and a key evicted early loses its exact count. On the Zipf streams a heavy key is heavy from its first few arrivals and is rarely evicted. On a stream whose heavy keys arrive late — a key that becomes popular halfway through — the counted reading would carry more of the sketch’s error, and the entry estimate would matter more.

The hash families are the earlier pages’ pairwise ones. The independence an estimator spends found the tug-of-war estimator’s variance spends four-wise independence. A Count-Sketch’s median-of-rows guarantee needs only pairwise, and nothing here depends on more.

Still open: a list whose length the stream chooses #

Every estimator here fixes its number of candidates before the stream begins, and the best number moved from one on the steep streams to sixteen at Zipf 0.5. It moved because the right list is the one that removes every key heavy enough to dominate what is left, and how many keys that is depends on the frequencies. A system that knew its streams’ exponent could choose $K$ in advance. One that did not would provision for the worst and pay for candidates it never used on the steep streams.

The measurement that follows lets the stream decide. The list is kept long, and at the end a candidate is counted in the heavy part only if its contribution exceeds a stated share of the estimated moment; the rest are returned to the sampled part by letting their copies report. It asks whether one threshold, stated as a share of $F_3$, reaches within a few per cent of the best fixed $K$ on every exponent. The prediction is that it does, because the best $K$ at each exponent is the list that removes the keys whose reports make the sampler’s variance, and those are the keys with the largest shares of the moment — which is what a threshold on the share selects, stated once for every stream. It could fail on the flat stream, where the list’s cost is in the sketch that must be wide enough to rank the candidates at all. If it does, the threshold would need to govern the sketch’s width as well as the list’s length — the choice the pass that was never a parameter made with a second pass, here made with nothing but the counts already held.