A list that waits before it admits

A list that gives back its places is the latest step in a strand about estimating the third frequency moment of a stream — the sum of every key’s count cubed — in as few words as a 10% error allows. The moments past the second found that the sampling estimator for it wastes most of its copies on light keys, and the keys worth counting before sampling built the repair: a Count-Sketch beside the stream, a short list of candidate heavy keys counted exactly once they join it, and sampling only for the rest. A share of a list of equals then let the list’s length follow the stream, keeping only candidates that held a share of the list’s own moment.

The latest version gives places back during the pass. A candidate whose cube falls under a share θ of the list’s total is dropped at once; a new key joins only if its cube would be at least that share. It ends the pass the right length — three candidates on Zipf 1 — but a list’s memory is the most it ever held, and it held the most at the start. On Zipf 1 at a share of 0.03 the list reached nineteen candidates by about the twenty-fifth arrival, when no key had yet stood out and a dozen light keys each had a large share of a small total.

That essay’s closing section proposed the obvious remedy, with two parts. Wait: admit nobody until the sketch has seen $W$ arrivals, enough to rank keys at all. Admit by the stream: after the warm-up, let a key join only if its estimate is at least a share $\varphi$ of the arrivals so far — the rule the items that survive k counters and the other counter summaries use — rather than a share of the list. Keep dropping by the list’s own share, as before. It predicted that a warm-up of 500 would bring Zipf 1’s peak from nineteen to three and its words to 190 or under, within a fifth of the best fixed list; that Zipf 0.5’s peak would fall to about ten and recover the end-of-pass cut’s 1,304 words; and it named a risk at the steep end, where the heaviest key’s first 500 arrivals would be counted only by the sketch.

The same estimator, two admissions #

Everything but the admission is the earlier essays’. Sixty thousand arrivals over 2,048 keys at Zipf exponents from 0 to 2; a Count-Sketch of depth five at whichever width makes each estimator cheapest; candidates counted exactly from the moment they join, so a key’s arrivals before it joins are known only through the sketch; copies of the sampling estimator, enough for a relative standard deviation of 10%. The list drops a candidate whose cube is under 3% of its total. Every estimator is charged in words — five a sketch column, three a counted candidate at the list’s largest peak over sixteen sketch seeds, two a copy.

The waiting list admits nobody for the first $W$ arrivals, for $W$ from 100 to 5,000, and after that admits a key only when its sketch estimate is at least $\varphi$ times the arrivals seen so far, at 0.1%, 0.3% and 1%. The plates use 0.3% unless they say otherwise; on every stream but the flattest, 0.1% and 0.3% admit the same keys.

On Zipf 1 the waiting list costs 197 words, against 239 for the list that admits at once and 159 for the best fixed list. On Zipf 0.75 it costs 380 against 419, within 6% of the best fixed list’s 358. On the steeper streams it changes little: 171 against 174 at Zipf 1.5, 88 against 91 at Zipf 2. On Zipf 0.5 it costs 1,748 against 1,785, and the end-of-pass cut, at 1,304, stays out of reach.

So the prediction comes close at Zipf 1 and misses at Zipf 0.5. And at the flat end the plate shows something the proposal did not ask about: with a warm-up of 5,000 the list never admits anybody on streams of Zipf 0.25 or flatter, the estimator is then the plain sampler alone, and the plain sampler — 206 words on a flat stream, 676 at Zipf 0.25 — is the cheapest estimator there by a wide margin.

Where the peak went #

Admitting by a share of the stream from the very first arrival already takes the edge off: on this seed the list reaches twelve candidates in the first few hundred arrivals rather than nineteen, because a key must now be 0.3% of everything seen, which is one arrival in the first 333 and so admits nearly anything early but not everything. With a warm-up of 500 the list never holds more than three, and with 2,000 the same three.

The trace shows why the length of the warm-up hardly matters once it is past a hundred or so. On Zipf 1 over 2,048 keys the heaviest key has about 12% of the arrivals and the next few 6%, 4% and 3%. After a hundred arrivals those keys have already separated from the rest, the sketch ranks them correctly, and the share of the stream admits them and nobody else. Waiting longer only delays when they start being counted exactly.

Across the sixteen seeds the largest peak on Zipf 1 falls from 19 with no warm-up to 5 at 100 arrivals, and stays at 5 out to 5,000. On Zipf 2 it falls from 3 to 2. On Zipf 0.5 it falls from 33 to 30 at 100, 20 at 500, 17 at 2,000 and 16 at 5,000 — the one stream where waiting longer keeps paying, because on Zipf 0.5 no key separates quickly: the heaviest holds about 1.1% of the arrivals, the next 0.8% and 0.6%, and the fourteen keys over 0.3% are close enough together that a few hundred arrivals cannot rank them.

The prediction’s three on Zipf 1 is not reached at a share of 0.03, which is the share whose peak was nineteen. At the share of 0.1 that the earlier essay’s headline plate used, the same warm-up takes the peak from six to three, as predicted — and the words from 208 to only 201, because a peak of six was eighteen words of the 208 to begin with. The proposal paired the peak of one setting with the words of another.

Where the words go #

On Zipf 1 the warm-up saves 42 words of list and nothing else moves: the sketch stays at 32 columns, 160 words, and the copies at eleven. The 197 that remain are four fifths sketch. That is why the waiting list cannot reach the best fixed list’s 159: the fixed list’s best is a single candidate beside a sketch of sixteen columns, 80 words, with 38 copies, and it can afford half the sketch because one candidate on Zipf 1 is always the heaviest key, whatever the sketch’s error. A list that decides admission from the sketch’s estimates — of any length, by any share — needs the sketch to rank keys correctly, and that takes 32 columns.

The steep streams say the same thing more starkly. At Zipf 1.5 the waiting list costs 171 words, 160 of them its sketch; the best fixed list costs 51 in all. The peak is three candidates, nine words, and no admission rule could close a gap of 120 words by changing it.

On Zipf 0.5 the warm-up saves 39 words of list and spends six more copies, twelve words, because the candidates it no longer admits early are counted later and their early arrivals carry the sketch’s error into the heavy part. The net is 27 words of 1,775.

The share that decides Zipf 0.5 #

On Zipf 0.5 the admission share stops being neutral. At 0.1% and 0.3% of the stream it refuses nobody the warm-up has not already refused, and the list costs 1,748 words at a peak of 20. At 1% the list holds at most eight candidates, but it catches only 42% of the moment instead of 69%, the sampled part grows, and the copies needed rise from 204 to 759: 2,182 words. A higher bar for admission saves places and spends copies, and on Zipf 0.5 the copies are dearer.

The end-of-pass cut reaches 1,304 on this stream by a different route. It keeps a list of 64 throughout — all the candidates any rule might want, at 192 words — and decides at the end which of them hold a share of the list’s moment, so it catches the heavy part of a stream with no dominant keys without ever having to decide early who is heavy. Every rule that decides during the pass, by the list’s share or by the stream’s, decides on fewer arrivals than the end-of-pass cut does, and on Zipf 0.5 that is the information that matters.

The risk that did not arrive #

The proposal’s named risk was at the steep end. It put the heaviest key on Zipf 2 at a quarter of the stream; over 2,048 keys it is in fact three fifths, so during a warm-up of 500 it arrives about 300 times, and those arrivals are counted only by the sketch rather than exactly. A sketch error of a few in the heaviest key’s count, cubed, could cost more copies than the warm-up saved places.

It does not. The heavy part’s error on Zipf 2 after a warm-up of 500 is four parts in a hundred thousand of the moment, the copies needed stay at one, and the waiting list costs 88 words against 91. The sketch’s estimate of a key with 300 arrivals, in a sketch whose other cells hold a few dozen arrivals each, is off by a few at most, and a few in the key’s final count of about 36,000 is nothing even when cubed against a total of $5 \times 10^{13}$.

What waiting can and cannot do #

The two parts of the proposal did different things, and the plates separate them.

Admitting by a share of the stream is what empties the list on flat streams. A list that admits by a share of itself always admits somebody, because some key is always a large share of a short list of light keys; a list that admits by a share of the stream admits nobody if nobody is heavy. With a long enough warm-up that becomes exact, and the estimator falls back to the plain sampler where the plain sampler is best. No list in the strand before this one could do that.

Waiting is what removes the early peak on skewed streams, and a hundred arrivals is enough wherever a few keys separate quickly. Where none do, on Zipf 0.5, waiting longer keeps helping a little and never helps enough.

Neither part touches what separates the list from the best fixed one, which is the sketch. On Zipf 1 the fixed list’s 159 words are half a sixteen-column sketch and half copies; the waiting list’s 197 are four fifths a sketch twice that size, kept so that admission decisions come out right, with fewer copies because its list catches more of the moment. The cost of deciding is paid in the sketch, not in the list, and no rule about the list can recover it. A rule that chooses candidates from the sketch’s estimates needs a sketch good enough to choose with, and a fixed list of one candidate does not.

Two kinds of evidence about who is heavy #

The strand has now tried three ways for a list to decide who belongs on it, and they differ in what evidence they read.

The fixed list reads only rank: it keeps the K keys whose estimates are largest, whatever those estimates are. It never asks whether a key is heavy in any absolute sense, so it never mistakes a short list of light keys for a list of heavy ones — but it has to be told K, and the right K differs by an order of magnitude across these streams, from one on Zipf 1 to sixteen on Zipf 0.5.

The share of the list, in the last two essays, reads the list against itself. That is what let its length follow the stream without being told, and it is also what made the early peak: at the twenty-fifth arrival a list of light keys is a list of equals, and every equal holds a large share of it.

The share of the stream reads each key against everything seen. It is the evidence the counter summaries have always used — a key is frequent if it is a fixed fraction of the stream — and it is the only one of the three that can conclude that nobody is heavy. Its weakness is the start of the stream, when everything is a large fraction of very little, and the warm-up is exactly the repair for that weakness and no other.

Read that way, the waiting list combines the second and third kinds of evidence, admitting by the stream and dropping by the list. On every stream measured it is at least as cheap as the list it replaced, and on the flat streams it is the first list in the strand that knows to stay empty. The one stream it does not fix, Zipf 0.5, is the one where no kind of evidence available during the pass ranks the keys; a sketch that is allowed to be under and a count that is never under bracket the two errors a sketch can make on such keys, and neither error is small there.

What these streams leave out #

One length, one universe. Sixty thousand arrivals over 2,048 keys, as in every essay of the strand. A longer stream makes a warm-up of fixed length relatively shorter and the early peak relatively less important.

Stationary streams. Each stream’s distribution is fixed from first arrival to last, which is the setting the summary that has to forget set aside. A stream whose heavy keys change mid-pass — a new key becoming heavy late — is where admission by a share of the stream would be tested hardest, since a late key must reach the share of everything before it, and that was not run.

The peak as the price. Every list is charged its largest peak over sixteen seeds, the convention of the earlier essays. A structure that could allocate its list as it grows would be charged less on the seeds whose peaks were small.

Still open: a sketch sized for the decision #

The words plate’s remaining gap is the sketch. On Zipf 1 the waiting list spends 160 of its 197 words on 32 columns, and the reason is that it decides admission from the sketch’s estimates. The best fixed list decides nothing and runs on sixteen.

The measurement that follows asks whether admission can be made reliable on the fixed list’s sixteen columns by requiring a key to clear the share twice, at arrivals some distance apart, before it joins, with admitted keys counted exactly as now. The prediction is that on Zipf 1 the list then runs at about 80 words of sketch, 15 of list and 22 of copies, under 120 words — a quarter under the best fixed list’s 159, because its list catches more of the moment than one candidate does — and on Zipf 0.5 gains nothing, since there the sketch was never the larger part. It could fail on the steep streams, where a wrong admission costs little but a missed one costs a heavy key’s whole cube; a small sketch that misranks the second-heaviest key on Zipf 1.5 once in sixteen seeds would need more copies than every word it saved. The question is whether the sketch an estimator needs is set by what it measures or by what it decides.