A share of a list of equals

The keys worth counting before sampling cut the state needed to estimate $F_3 = \sum f_x^3$, the third frequency moment of a stream, by doing two things at once. A Count-Sketch watched every arrival, and a list of $K$ candidates kept the keys the sketch ranked heaviest, each counted exactly from the moment it joined. At the end the heavy part was summed from the counts, and the sampling estimator of the moments past the second, run over the whole stream, estimated the rest: a copy that had picked a position whose key ended up on the list reported nothing, and the others reported as before. On the stream built to be worst for the plain sampler, the state for ten per cent fell from 23,598 words to under a thousand.

The best $K$ moved with the stream. On the steepest streams one candidate was best, at Zipf 0.5 sixteen, and on a flat stream no list at all: the plain sampler beat every list there. That essay’s closing section noticed why. 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 stream’s exponent could choose $K$; one that did not would provision for the worst. So it proposed letting the stream decide. Keep the list long, and at the end count a candidate in the heavy part only if its contribution exceeds a stated share of the moment, returning the rest to the sampled part. It predicted that one share would come within a few per cent of the best fixed $K$ on every exponent, and named the failure: the flat stream, where the list’s cost is in a sketch that must be wide enough to rank the candidates at all.

A share of the list’s own moment #

The streams are the earlier essay’s: 60,000 arrivals over 2,048 keys, Zipf exponents from 0, flat, to 2. The sketch has depth five and a width chosen for each design to make it smallest. Every candidate is counted from entry, three words a candidate: the key, the sketch’s estimate when it joined, and the count since. A copy of the sampler is two words, a sketch column five.

The share has to be a share of something known at the end of the pass. $F_3$ itself is not: it is what the estimator is for. So the share is taken of the list’s own total, $\sum \hat f^3$ over every candidate, which is in hand when the pass ends. A candidate whose $\hat f^3$ is at least that share of the total is counted in the heavy part and its key is excluded from the sampled part. A candidate below it is returned: its copies report as any light key’s do, and its count is ignored.

The sketch’s estimates matter twice here: they decide which keys join the list, and the entry estimate is added to each candidate’s count. The sketch is a Count-Sketch, whose error falls on both sides of the truth, the trade a sketch that is allowed to be under measured. A Count-Min sketch, never under on any key as a count that is never under showed, would inflate every candidate’s entry by the weight of the keys it collides with, and on a flat stream every candidate would look heavier than it is by about the same amount.

The rest of the method is unchanged. Given the list, the sampled part’s variance is computed exactly from the frequencies, and the heavy part’s error is averaged over sixteen sketch seeds. A design’s state is the fewest words, over sketch widths, that reach a relative standard deviation of 10%. A share of nought keeps the whole list and costs exactly what a fixed list of the same length costs, to the last word, which is the check that the threshold changed nothing else.

The words, stream by stream #

A list of sixty-four candidates cut at 3% of its own moment needs 274 words on the steepest stream, where one fixed candidate needs 45, and 1,730 on a flat stream, where the plain sampler needs 206. It comes within a few per cent of the best at no exponent but one. At Zipf 0.5 it needs 1,304 words against the best fixed list’s 1,526, beating it by 15%, and that case has its own section below.

A shorter list does better on the steep streams and worse on the flat ones. Eight candidates cut at 1% need 106 words at Zipf 2, twice the best, and 358 at Zipf 0.75, exactly the best. On the flat stream they need 5,504, twenty-seven times the plain sampler. The proposal’s single knob turned out to be two knobs, the share and the list’s length, and neither setting of the pair is good everywhere.

The share does choose #

At a share of 3%, the list keeps 5.5 candidates at Zipf 0.5, 2.8 at Zipf 1 and 1.1 at Zipf 2: the number of keys worth counting falls with the skew, as the proposal reasoned it should. The selection itself works. The keys whose cubes hold a large share of what the list holds are the keys whose reports dominate the sampler’s variance, and on a skewed stream they are few and they stand out.

A share is the oldest kind of threshold for heavy keys. The items that survive k counters measured Misra-Gries, which keeps every key whose frequency exceeds a share of the stream’s length, one over the number of counters, with no hashing at all. The share here is of a different quantity, cubes of estimated frequencies, and of a different total, the list’s rather than the stream’s, and both changes are forced. A moment is dominated by cubes, so a key’s share of the moment is what matters; and the stream’s $F_3$ is the unknown.

The share’s choice and the best fixed list’s length do not agree exactly, and they need not. At Zipf 1 the best fixed list is one candidate and the share keeps three; at Zipf 0.5 the best fixed list is sixteen and the share keeps five. The share keeps what holds 3% of the list, which is a statement about the keys; the best fixed length is whatever makes the whole estimator smallest, which also depends on the sketch’s error on every counted key, cubed, as the earlier essay found. The two criteria point the same way and land in different places.

On the flat stream the share keeps 1.5 candidates at 3% and the whole list at 1%. Neither number means what it means on the skewed streams.

No length fits every stream #

At a share of 3%, every list length costs at least eight times the best on some exponent: eight candidates lose twenty-seven times over on the flat stream, sixty-four lose eight times over there and six times over on the steep ones. The prediction was within a few per cent on every exponent. Between Zipf 0.5 and Zipf 1 the shorter lists come close, within 2% to 38%; outside that range none does.

The two ends fail for different reasons, which is why no compromise length fixes both. On the steep streams the list’s own words are the cost. The best estimator there is one candidate, a sketch eight columns wide and a copy or two, 45 to 51 words. A list of eight is already twenty-four words; a list of sixty-four is 192. The share can return every candidate but one to the sampled part, and it does, but the words were spent holding them through the pass. On the flat stream the cost is the sketch, and it has nothing to do with how many candidates are kept, which the next plate shows.

A list of equals #

On the flat stream the list’s sixty-four candidates each hold between 1.2% and 3.2% of the list’s moment, so a share of 1% keeps all of them and a share of 3% keeps the two the sketch happened to rank highest; together they hold 4.1% of $F_3$. A share of the list’s moment is a share of a list of equals. It cannot say that no candidate is heavy, because it only compares candidates with one another, and on a flat stream they are all alike.

The flat stream is the case every sketch in this line has found hardest, for a reason the skew a few counters cannot repair put plainly: when no key stands out, there is nothing for a few counters to hold that the rest of the stream does not hold as well. The second moment escaped the problem altogether. The estimate that squares the stream needed no list, because the tug-of-war estimator’s variance is bounded by the square of the moment it estimates on every stream; past the second moment no estimator of that kind exists, which is why there is a list to size at all.

What a share would need to say is that the list holds little of the moment. That is a comparison with $F_3$, which the list does not know; the sampled part’s estimate does, but only at the end, and as an estimate. On Zipf 1 the same plate shows the opposite shape: the first candidate holds 83% of the list and the list holds all of $F_3$, so a share of the list is very nearly a share of the moment. The proposal’s statement of the rule, a share of the estimated moment, was the right one. The version that can be computed without the sampled part is right only where the list is the moment.

The predicted failure is real, and it is not quite the one named. The flat stream’s cost is in the sketch, as predicted. A candidate counted from entry carries the sketch’s estimate of its arrivals before it joined, and on a flat stream that estimate is noise of the same size as the candidate’s frequency. To keep the heavy part’s error inside ten per cent, the sketch must be wide, 256 columns for the share of 3%, 1,280 words. But the plain sampler needs no sketch and only 103 copies on a flat stream, 206 words. Any design that counts a candidate on a flat stream pays for a sketch it did not need, whatever the share.

Where the words go #

At Zipf 2 the chosen list spends 192 of its 274 words holding candidates it returns, and the best fixed list spends 3. The sketch and the copies are almost the same in both; the difference is the list. At Zipf 1 and 1.5 the same is true: the copies fall to a handful, the sketch to under 200 words, and the list’s 192 words are most of the state.

At the flat end the list is a smaller part of a larger problem. The chosen list’s sketch is twice as wide as the best fixed list’s, because counting even one or two candidates there requires their entry estimates to be good, and the best fixed list’s one candidate already costs 640 words of sketch against the plain sampler’s nothing. On the flat stream and at Zipf 0.25 the best estimator has no list and no sketch at all, which the keys worth counting before sampling found and this design cannot find, since it has a list by construction.

The one exponent where choosing wins #

At Zipf 0.5 a list of sixty-four cut at 3% keeps 5.5 candidates and needs 1,304 words, under every fixed list; the best fixed list, sixteen candidates, needs 1,526. It wins even though it pays 192 words for its list where the fixed list of sixteen pays 48.

The parts say where the win comes from. The chosen list runs with a sketch of 128 columns, 640 words; the best fixed list needs 256, 1,280 words. A fixed list of four or eight, at any width, needs at least 1,530 words, and the chosen list needs 1,304. Why a list cut by a share tolerates a sketch half as wide was not measured. One possibility is that the share drops exactly the candidates whose entry estimates the narrow sketch inflated, since an inflated estimate makes a light key look heavy only up to a point, and the share is set against keys that really are heavy. Another is that the number kept varies from pass to pass, and a fixed list cannot. The plate shows the effect, not the cause.

This is the one setting where the stream-chosen list does what the proposal hoped, and it is the setting the proposal was built around: the exponent where the best fixed length was largest and furthest from the others.

What the counts depend on #

Exact variance, sampled sketches. The sampled part’s variance is computed from the stream’s frequencies, so a copy count is exact for its list. The heavy part’s error is averaged over sixteen seeds of the sketch’s hashing, and the list it leaves differs by seed; the words reported are for the mean.

A sketch of depth five. Only the width is chosen for each design; the depth stays at five rows, as in the earlier essay. A deeper sketch would make entry estimates better at more words a column, and would move the flat stream’s numbers most, since that is where the sketch is most of the state.

One stream an exponent. Each exponent is one stream of 60,000 arrivals. The pass that was never a parameter and the earlier essays used the same streams, so the comparisons are like with like, but a different draw would move the words by some per cent.

The share of the list, not of the moment. The rule measured is the one computable at the end of the pass. A rule using the sampled part’s estimate of $F_3$ would see that the flat stream’s list holds a twenty-fifth of the moment; it was not built, because its decision would depend on an estimate whose variance depends on the decision.

Still open: a list that gives back its places as it goes #

The list’s words were spent holding candidates through the pass, and the share returned them only at the end. A list could give back its places during the pass instead. Each time a candidate is replaced or its count updated, the list knows its own total; a candidate whose cube falls below a share of that total could be dropped there and then, and its three words freed. The list would then hold, at any moment, only the candidates that are currently a large share of the list, and its length would follow the stream.

That turns the list’s memory from a fixed cost into a peak. The measurement that follows runs the list with that rule at shares of 1%, 3% and 10%, records the largest number of candidates it ever held, and charges that peak in words. The prediction is that on Zipf 1 and steeper the peak stays under four candidates, which would bring the words within 20% of the best fixed list there, and that at Zipf 0.5 the peak is about ten, keeping most of this essay’s win. 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; then the peak is the cap, and nothing is saved. On the flat stream it changes nothing, because a list of equals stays a list of equals, and the share of the list will never learn that the list itself is small.