A second look at the same sketch

The estimator this strand has been building measures the third frequency moment of a stream — the sum, over every key, of its count cubed — to within 10% in as few words of memory as it can. The moments past the second showed that sampling alone wastes most of its copies on light keys. The keys worth counting before sampling put a Count-Sketch beside the stream and a short list of heavy candidates counted exactly once they join, and sampled only the rest. A share of a list of equals and a list that gives back its places let the list’s length follow the stream, and a list that waits before it admits stopped it filling up in the first few dozen arrivals: no key joins until the sketch has seen a warm-up’s worth of the stream, and after that a key joins only when its sketch estimate is at least 0.3% of the arrivals so far.

That list ended the strand’s last measurement at 197 words on Zipf 1, and its plates said where the words were. A hundred and sixty of them were the sketch, thirty-two columns of five rows. The best fixed list, which keeps a single candidate and decides nothing, costs 159 words in all and runs on sixteen columns. The difference is not what the list measures but what it decides: a list that admits keys on the sketch’s say-so needs the sketch to say the right thing, and on Zipf 1 that takes twice the columns.

The closing proposal was to make the decision reliable on the smaller sketch by asking twice. A key whose estimate clears the bar is not admitted at once; it must clear it again at an arrival at least $G$ later, with no failed check between. The prediction was that on Zipf 1 the list would then run on sixteen columns — about 80 words of sketch, 15 of list and 22 of copies, under 120 in all — a quarter under the best fixed list.

Asking again, and asking someone else #

Everything is the earlier essay’s except the check before admission. Sixty thousand arrivals over 2,048 keys at Zipf exponents from 0 to 2; a Count-Sketch of five rows at whichever width makes each estimator cheapest; a warm-up of 100 arrivals; admission at 0.3% of the arrivals so far; a candidate dropped when its cube falls under 3% of the list’s total; candidates counted exactly from the moment they join, entering at the sketch’s estimate; enough copies of the sampling estimator to bring the whole to a relative standard deviation of 10%. Every estimator is charged in words: five a sketch column, three a candidate at the list’s largest peak over sixteen sketch seeds, two a copy.

The second look adds the gap. The first time a key’s estimate clears the bar, the time is noted; the key joins only when it arrives again at least $G$ arrivals later and clears the bar again, and a failed check in between forgets the note. Gaps of 250, 1,000 and 4,000 arrivals are run, and a gap of nought is the waiting list itself — which is checked to give the waiting list’s answer exactly.

The second look turned out to be the wrong kind of question, for a reason the plates below show, so a third rule is run beside it. Probation asks someone other than the sketch. A key that clears the bar is put on a probation list and counted exactly from that moment; after $G$ arrivals, the next time it arrives, it joins only if it arrived at least $0.003\,G$ times during the probation — three times in 1,000 — which is the bar asked of an exact count instead of an estimate. A key under test costs two words, its name and its count, and the probation is charged its largest peak like the list.

On Zipf 1 the second look costs 185 words at a gap of 4,000 and 189 at the two shorter gaps, against 197 for one look — and in every case at thirty-two columns, the width the prediction meant to halve. The small saving is all in the copies, which fall from eleven to five because a few light keys that one look admitted are kept out; the sketch does not change. On the other streams the second look moves the words by a few per cent at most: 1,605 against 1,766 on Zipf 0.5, 384 against 380 on Zipf 0.75, 171 against 171 at Zipf 1.5 and 85 against 88 at Zipf 2.

Probation is the line that does run on sixteen columns on Zipf 1, and it costs 615 words. The prediction of under 120 is missed by a factor of five by the rule that reaches the predicted width, and missed in width by the rule it named.

What a second look sees #

The prediction treated the sketch’s error as noise: an estimate that is too high at one arrival, by bad luck, ought to be less too high a thousand arrivals later, so that two looks agree on a light key only rarely. A Count-Sketch’s error is not that kind of error.

These are the three light keys still on the list at the end of one sixteen-column pass with a gap of 1,000. One arrives 21 times in the whole stream, one four times, one 75 times. The sketch puts them at 7,171, 3,390 and 3,684 by the end, and at every check along the way their estimates sit well above the bar and climb in a straight line.

The straight line gives the cause away. The first key’s estimate ends at 7,171, and the heaviest key in the stream arrives 7,359 times; the third’s ends at 3,684, near the second-heaviest key’s 3,738. A Count-Sketch estimates a key as the median, over its five rows, of the signed counter its key hashes to. With sixteen counters a row and a handful of keys holding most of the stream, a light key that shares a counter with the heaviest key in three rows of five — with the sign that adds rather than cancels — has a median that is the heaviest key’s count, plus a little. Its estimate is another key’s count, read through a shared cell.

Nothing about that changes with time. The hash functions are fixed for the pass, so the collision is fixed, and the colliding key’s count grows in proportion to the stream; the bar grows in proportion to the stream too, at 0.3% of it, and the heaviest key holds about 12%. Once a light key’s median lands on a heavy key’s counter, its estimate stays forty times above the bar for the rest of the pass. Asking it again in a thousand arrivals, or four thousand, asks the same counters the same question and reads back a larger version of the same wrong answer.

A sketch that is allowed to be under named this when it compared a sketch that can err in both directions with a count that is never under: the errors of a hashed summary are fixed by the hash, not drawn afresh at each query. A second query is evidence only when its error is independent of the first’s, and nothing about a later time makes it so.

How much worse sixteen columns is #

The plate measures only the list’s part of the estimate — the candidates’ entry estimates and exact counts, cubed and summed, against the true cubes of the same keys — because that part has to be inside 10% before any number of sampling copies can bring the whole estimate there. At sixteen columns it is 47% of the moment with one look, 26% with a second look 1,000 arrivals later and 24% at 4,000. No number of copies can repair an error that large; the estimator is simply infeasible at that width, and the cheapest width is the next one up, 32, where the three rules sit at 7.9%, 6.1% and 4.9%.

So the second look does something — it halves the list’s error at sixteen columns — and the something is not enough by a factor of two and a half. The halving comes from keys the two looks see differently, and the earlier plate says which ones those are: a light key whose estimate is high at its first check by a passing fluctuation, which the second check catches. Those exist. The keys that wreck the estimate are the other kind, the ones sitting on a heavy key’s counter, and those are the ones the second look cannot catch.

Probation’s line is a different shape. At sixteen columns its list error is 3.4%, a seventh of the second look’s; at eight columns it is 43% against 212% and more. An exact count of a key’s arrivals during its probation shares nothing with the sketch, so a key the sketch puts at 3,000 because of a collision arrives zero or one times in the 1,000 arrivals it is watched, and is refused. The sketch is still the key’s first evidence, and still sets its entry value, but it is no longer the only evidence on which the key is admitted.

Who gets in and who is kept out #

The plate counts the two mistakes an admission rule can make. On the left, light keys — true counts under 0.3% of the stream — still on the list at the end, where their overrated entry values are cubed into the estimate: 3.44 a pass with one look, 2.81 to 2.63 with a second, and 0.38 on probation. On the right, the 42 keys that do reach 0.3% of the stream and never joined at all.

The right-hand side is where the second look turns out to be worse than doing nothing. A key on the edge of the bar — a count of 200 or 300 in a stream of 60,000 — has an estimate that wanders above and below the bar as the stream goes on, and requiring two checks with no failure between turns every wander below into a restart. One look leaves 6.56 of the 42 out; a second look 250 arrivals later leaves 10.6; 4,000 arrivals later, 14.7. The second look refuses the honest marginal keys, whose estimates fluctuate, more readily than the dishonest light ones, whose estimates do not.

That asymmetry is the whole of the result in one plate. The rule was designed to reject inconsistency, and on a Count-Sketch the keys that deserve rejecting are the consistent ones.

Probation leaves 7.75 heavy keys out, about one more than one look: a key with 200 arrivals in 60,000 expects 3.3 in a probation of 1,000, so about a third of the keys just over the bar fail it by chance. Those are the keys whose cubes matter least. A key at the bar contributes $180^3$ against the heaviest key’s $7{,}359^3$, a part in seventy thousand; missing it costs a little sampling variance, where admitting a light key at 3,000 costs its estimate’s cube, which is about a twentieth of the whole moment on its own.

Where the words go #

The probation does exactly what the prediction wanted of a second look, and the parts plate prices it. At sixteen columns the sketch is 80 words, the list’s peak of five candidates is 15, and the copies fall to four, eight words, because the list now catches the heavy part almost exactly. That is 103 words — under the prediction’s 120, and a third under the best fixed list. Then the probation adds 512.

It adds them because of the same keys that defeat the second look. Every key the sketch overrates clears the bar at its first check after the warm-up, so every one of them is put on probation and held for 1,000 arrivals while its exact count is gathered. On Zipf 1 at sixteen columns that is a great many keys: the light admissions the plate above counts during the pass fall from 876 to 72 under probation, but the probation itself peaked at 256 keys under test at once. The probation list has to be big enough to hold every key the sketch is wrong about while it finds out, and on a small sketch the sketch is wrong about many keys.

A shorter probation is cheaper and less sure. At 250 arrivals the probation peaks at 126 keys and the cheapest width rises back to 32, for 432 words; at 4,000 it peaks near 400 keys, 1,131 words. No length makes the probation cheaper than the sixteen extra columns it is trying to save, because those columns cost 80 words and the shortest probation that makes sixteen columns feasible costs six times that.

The two other ends #

At the flat end the second look does something nobody asked of it. On a stream with no heavy keys at all, the waiting list with its warm-up of 100 admits light keys constantly — 2,856 words on the flat stream, nearly three times the best fixed list’s 985 — and a second look 4,000 arrivals later admits none, so the estimator becomes the plain sampler, which is the cheapest thing on a flat stream at 206 words, and at Zipf 0.25 costs 676 against the waiting list’s 3,271. That is the earlier essay’s finding about a warm-up of 5,000 arriving by another route: on a flat stream no estimate stays above 0.3% of the stream for long, and any rule that demands it stay there long enough leaves the list empty. Probation does less well on flat streams, 1,728 words, because it keeps testing keys that will never pass.

At the steep end nothing changes. On Zipf 1.5 the second look costs 171 words at every gap, as one look did, 160 of them its 32 columns; on Zipf 2 it saves three words of 88. Probation costs 256 and 118. On these streams a heavy key is so far above every light key that one look is already right, and the cost was the sketch all along.

What was being paid for #

The essay before this one ended on a question: whether the sketch an estimator needs is set by what it measures or by what it decides. The plates answer it more sharply than the proposal allowed for.

A sketch used only to measure — to supply entry values for keys that are certainly heavy — can be small, because it is asked about keys that dominate their own counters: the heaviest key’s estimate is off by a few dozen in 7,359 whatever it shares a counter with. A sketch used to decide is asked about every key, and most keys are light, and a light key’s estimate is whatever its counters hold — which, on a narrow sketch, is often somebody else. Deciding is the harder use because it is the use that asks about keys the sketch cannot see.

Two ways of making a narrow sketch decide were tried. Asking it again fails because its errors are fixed by its hash functions, so the second answer repeats the first; it refuses the keys with fluctuating estimates, which are the honest ones near the bar. Asking an exact counter succeeds, and costs one slot for every key the sketch is wrong about, which is the thing a narrow sketch has most of. The widening from sixteen to thirty-two columns that the waiting list chose is, by this measure, the cheapest way to buy the decision: eighty words to halve the number of keys any light key can collide with, against five hundred to test each one.

The skew a few counters cannot repair and the items that survive k counters arrived at the counter-summary version of the same price: a summary that must say which keys are frequent needs room in proportion to the number of keys it must be able to rule out, not to the number it keeps.

What these streams do not say #

One stream length, one universe. Sixty thousand arrivals over 2,048 keys, as in every essay of the strand. On a longer stream the bar is higher in absolute terms and a light key’s chance of sharing a counter with a heavy one is unchanged, so the collision mechanism is the same; how many keys a probation must hold would change with the universe.

One family of hash functions. The sketch’s rows use the pairwise-independent hashes the independence an estimator spends measured. The persistence of an overrated key is a property of any fixed hash function, not of this family, but the share of keys that collide in three of five rows is this width’s and this family’s.

One probation rule. A key is tested once for a fixed number of arrivals and refused if it falls under the bar. Testing only keys whose estimate is far above the bar, or capping the probation list and refusing keys when it is full, were not run; either trades heavy keys missed for slots saved.

Still open: a second sketch as the witness #

The second look failed because it asked the same sketch, and probation succeeded because it asked an exact counter — at a price set by how many keys need asking. Between them is a witness that is independent of the first sketch and costs a fixed amount however many keys it is asked about: a second Count-Sketch with its own hash functions.

The measurement that follows splits the thirty-two columns the waiting list needs into two sketches of sixteen with independent hashes, admits a key only when both put it over the bar, and takes its entry value from the lower of the two. The prediction is that a light key sharing a heavy key’s counters in one sketch almost never does in the other, so the list’s error at the same 160 words of sketch falls below one sketch’s 7.9% and the copies fall with it, bringing Zipf 1 under 185 words — and that two sketches of eight, at 80 words, are still infeasible, since at eight columns each sketch alone overrates hundreds of keys. It could fail on the marginal keys: requiring two independent sketches to agree refuses a key at the bar whenever either sketch underrates it, which may leave out more of the 42 than the second look did. The question is whether a decision needs width or independence — whether thirty-two columns are worth more as one sketch or as two witnesses.