A list that gives back its places

A share of a list of equals let the stream choose how many heavy keys an estimator of $F_3 = \sum f_x^3$ should count. The estimator is the one the keys worth counting before sampling built: a Count-Sketch watches every arrival, a list keeps the keys the sketch ranks heaviest and counts each exactly from the moment it joins, and copies of the sampling estimator of the moments past the second cover the rest of the stream. The best length of the list moves with the stream’s skew — one candidate on the steepest streams, sixteen at Zipf 0.5 — so the earlier page kept a long list of 64 and, at the end of the pass, counted in the heavy part only the candidates holding at least a share of the moment the list itself held; the rest went back to the sampled part. The share chose well: 1.1 candidates kept on average at Zipf 2, 5.5 at Zipf 0.5. But the list’s 64 places were paid for through the whole pass, 192 words, four times the best estimator’s whole state on the steepest streams.

Its closing section proposed giving the places back as the pass goes. Each time a candidate is replaced or its count grows, the list knows its own total, $\sum \hat f^3$ over its candidates; a candidate whose cube falls below a share of that total could be dropped there and then. The list would hold, at any moment, only the candidates currently a large share of it, and its memory would be its peak rather than its capacity. The proposal predicted that on Zipf 1 and steeper the peak stays under four candidates, bringing the words within a fifth of the best fixed list, and that at Zipf 0.5 the peak is about ten, keeping most of the earlier win. It named the way it could fail, early in the pass: before many arrivals the sketch’s estimates are small and close together, every candidate is a large share of a small list, and the list may grow to its limit before any key has had time to stand out.

The list that gives back #

Everything but the list is the earlier pages’: 60,000 arrivals over 2,048 keys at Zipf exponents from 0 to 2, a Count-Sketch of depth five at the width that makes each estimator smallest, candidates counted from entry, and copies of the sampling estimator enough for a relative standard deviation of 10%. The sampled part’s variance is computed exactly given the list, the heavy part’s error averaged over sixteen sketch seeds, and every estimator is charged in words: five a sketch column, three a counted candidate, two a copy.

The new list keeps its total as values change. After every change, its smallest candidate is dropped while that candidate’s cube is under a share θ of the total; an arriving key joins a list with room only if its estimate’s cube would be at least θ of the total with it included; a list at its cap of 64 replaces its smallest candidate, as before, when an arriving key’s estimate exceeds it. A candidate dropped and later re-admitted starts again from the sketch’s estimate, which is the Count-Sketch’s signed median and so may be under the truth as well as over it, the property a sketch that is allowed to be under traded for accuracy; a count that is never under is the one-sided alternative it was traded against. The list is charged three words for each candidate at its largest peak over the sixteen seeds. Three shares were run, 0.01, 0.03 and 0.1. At a share of nought the list gives nothing back and is the fixed list of its cap, which the measurement requires.

The peak comes first #

The list’s peak is set before any key has stood out: at a share of 0.03 the Zipf 1 list holds nineteen candidates after its twenty-fifth arrival and three at the end of 60,000; the Zipf 0.5 list holds thirty-three after its fiftieth and seven at the end. The proposal’s failure arrives at the first opportunity. Twenty-five arrivals over 2,048 keys are twenty-five different keys, nearly, each with an estimate near one, and a list whose total is nineteen ones is a list in which every candidate holds a nineteenth, more than 0.03. Every one of them is entitled to its place.

Then the stream does what the proposal expected. Within a few hundred arrivals the heavy keys of a Zipf 1 stream have estimates in the tens, their cubes in the thousands, and the light candidates fall below three per cent of a total those cubes dominate. The list shrinks to two or three and stays there for the remaining 59,000 arrivals, which is exactly the length the earlier page found best. The list’s length at the end of the pass is right. Its length at the start of the pass is what it pays for.

A bound that is not the stream’s #

A list that keeps only candidates holding a share θ of its total can never hold more than one over θ of them, and on every stream flatter than Zipf 1 it reaches that bound: at Zipf 0.5 the peaks are 33 at a share of 0.03 and 10 at 0.1, and 64, the cap, at 0.01. The bound is arithmetic — if every candidate’s cube is at least θ of the sum of all of them, there are at most 1/θ — and on the flatter streams the early arrivals fill it, because at the start of any stream every candidate is nearly equal. The peak is therefore a property of the share, not of the stream. Only the steep streams escape it, because their heavy keys stand out within the first few dozen arrivals: at Zipf 2 the peak is three at a share of 0.03, and at Zipf 1.5 four.

The proposal’s prediction of a peak under four on Zipf 1 and steeper holds only at Zipf 1.5 and 2, and there only at the larger shares. On Zipf 1 the peak is six even at the largest share, and nineteen at 0.03. Its prediction for Zipf 0.5 — a peak of about ten — holds at a share of 0.1, which is where the bound puts it.

What it costs, charged at the peak #

Charged its peak, the list that gives back its places is cheaper than the list cut at the end on every stream from Zipf 0.75 up — 208 words against 364 at Zipf 1, 88 against 274 at Zipf 2 — and dearer than the best fixed list everywhere: 159 at Zipf 1, 45 at Zipf 2. The proposal’s target, within a fifth of the best fixed list, misses by 31% at Zipf 1 and by nearly double at Zipf 2. And at Zipf 0.5, the one stream where the end-of-pass cut beat every fixed list, the list that gives back is the dearest of the three lists, 1,785 words at its best share against the cut’s 1,304.

At the steepest stream the comparison is closest to fair and still lost. At Zipf 2 the list’s peak is two candidates and its final length one, the fixed list’s length; the difference is that the giving-back list’s best sketch is twice as wide, sixteen columns to eight. A list that drops and re-admits candidates hands some of their counting back to the sketch, whose estimate a re-admitted candidate starts from, and a narrow sketch’s estimate is a worse start than a count kept from the first arrival.

Every share, against the best of the others #

No share brings the list within a fifth of the best of the plain sampler and the best fixed list on any stream; the closest are a share of 0.03 at Zipf 0.5 and 0.75, 17% over each, and a share of 0.1 at Zipf 1, 31% over. The larger share is better on the steep streams, because it holds the early peak to ten and the stream’s heavy keys pass it easily. At Zipf 1 its list ends the pass with two candidates where the smaller shares end with three and six, and the difference in words between the shares there — 249, 239 and 208 — is mostly the difference in their peaks, 27, 19 and 6 candidates. The smaller share is better at Zipf 0.5, because there the keys worth counting are many and each holds a small part of the moment, and a share of a tenth would turn most of them away. Neither is best on both, which is the earlier page’s finding about the end-of-pass share again: the share that selects well depends on the skew, and the skew is what the list was meant to discover.

On the flat stream and at Zipf 0.25 every list loses to sampling every position, the best fixed list by nearly a factor of three and the lists here by eight or more, as the earlier pages found for every list: there are no heavy keys to count, a sketch wide enough to rank keys that are all alike costs more than all the copies it saves, and the estimate that squares the stream is the reminder that a moment of a flat stream is cheap to estimate directly. The share was never going to help there; what it adds on the flat stream is a peak at its bound, ten or thirty-three candidates for keys none of which is heavy.

Where the words go #

At Zipf 1 the list given back costs eighteen words of candidates at its peak, against three for the best fixed list and 192 for the list cut at the end; at Zipf 0.5 its peak is thirty-three candidates, ninety-nine words, and its sketch and copies cost 1,686 words against the cut list’s 1,112. On the steep stream the saving the proposal wanted is there and is most of the difference: the list’s own words fall from 192 to 18, and the sketch and copies are about what the cut list needed.

On the flatter stream the list’s words were never the problem. The cut list paid 192 words for its 64 places and the given-back list 99 for its 33, a saving of 93; the rest of the estimator grew by 574. The given-back list is wrong about which keys to keep in a particular way. A candidate it drops in the first few hundred arrivals and admits again later has lost its exact count for the arrivals in between, and its value is the sketch’s estimate from then on. If many of the keys that end up heavy at Zipf 0.5 were dropped once — and early in the pass no key’s share is safe — then more of the heavy part carries sketch error, and the estimator buys it back with a wider sketch and more copies. That is the likeliest account and it is not separately measured here; what is measured is the 574 words.

What the share was good for #

The proposal turned a fixed cost into a peak, and the plates say what kind of peak a share of the list’s own total produces. It is set by the start of the stream, when every key is equal, and bounded by the share alone, so on any stream without keys that stand out at once it is one over the share. A share is a statement about the list relative to itself; at the start of a stream the list is small and every statement about it is large.

The items that survive k counters kept a fixed number of counters and decremented them all when a new key found none free — the Misra–Gries summary — and its guarantee was in terms of the stream’s length: a key with more than $m/k$ arrivals survives. That threshold is a share of the arrivals so far, not of the summary, and it grows as the stream does. At the twenty-fifth arrival of a stream of 60,000 it admits keys with a third of an arrival; at the end, keys with 900. The share used here does the opposite: it is generous at the start, when the list is small, and strict at the end. The measured peaks are the cost of that direction.

Measured against the earlier pages’ alternatives, the list that gives back is a useful middle setting on steep streams: it is two or three times cheaper than cutting a long list at the end and needs no knowledge of how many keys to keep, which the best fixed list does. It is not the stream choosing the list’s length, because the stream’s early arrivals choose the peak and every stream’s early arrivals look the same.

What these streams leave out #

One kind of stream. Every stream is drawn independently from a fixed Zipf law, so the heavy keys are heavy from the first arrival. A stream whose heavy keys arrive late — a key that becomes popular halfway — would keep candidates it later has to drop and admit late the keys it needs, and the given-back list’s peak might then be set in the middle of the pass. The skew a few counters cannot repair found that how skewed a stream is decides how much a few counters can do; how its skew arrives over time is a second question none of these pages asks.

One cap. The list was capped at 64 candidates, the earlier page’s longest list. At a share of 0.01 the cap is what bounds the peak, not the share.

The sketch’s estimate on re-entry. A re-admitted candidate starts from the sketch’s estimate, as every candidate does. Remembering a dropped candidate’s count elsewhere would remove the re-entry error and cost the memory the drop was meant to save.

Still open: a list that waits before it admits #

The peak is set in the first few dozen arrivals because the share treats a list of near-equal light keys the same as a list of established heavy ones. A list could refuse to admit anyone until the sketch has seen enough of the stream to rank keys at all, and admit only keys whose estimate is a share of the arrivals so far, as the counter summaries do, rather than a share of the list.

The measurement that follows gives the list both: no candidate before a warm-up of $W$ arrivals, from 100 to 5,000, and after it a key joins only if its estimate is at least $\varphi$ times the arrivals seen, with the list still dropping candidates below a share of its own total as here. It charges the warm-up’s cost honestly — the heavy keys’ first $W$ arrivals are counted only by the sketch — and measures the peak, the words and the heavy part’s error on every exponent. The prediction is that a warm-up of 500 arrivals brings the Zipf 1 peak from nineteen to three and the words to within a fifth of the best fixed list, 190 or under, and that at Zipf 0.5 the peak falls to about ten without the re-entry loss, recovering the end-of-pass cut’s 1,304. It could fail at the steep end: on Zipf 2 the heaviest key carries a quarter of the stream, its first 500 arrivals are 125 arrivals counted by the sketch instead of exactly, and the sketch’s error on them may cost more copies than the warm-up saves places. The question is whether the time a list waits can be paid for by the places it does not have to give back, or whether every way of deciding who is heavy early makes the same mistakes as the share, only later.