One pass, and no room

A second sketch as the witness

A list of heavy candidates admitted on a Count-Sketch's estimates needed thirty-two columns on Zipf 1, and asking the same sketch twice could not make sixteen enough, because a light key's error is fixed by its hashes. Split the columns into two sketches with their own hashes and admit a key only when both put it over the bar: at the same thirty-two columns the list's error falls from 7.9% of the moment to 0.8%, and the estimate needs 183 words against 197. Two sketches of eight columns — eighty words of sketch, predicted infeasible — run Zipf 1 in 149, under the 159 of the best list that decides nothing, which neither the waiting list nor a second look had reached. The named risk arrived: two witnesses leave nearly three times as many heavy keys off the list. It did not matter, because a heavy key left off is counted by the sampler, and a light key let on is counted wrong.

The estimator this strand has been building, from the estimate that squares the stream upward, 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, and 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 light rest. A list that gives back its places let the list’s length follow the stream, and a list that waits before it admits stopped that list filling in the first few dozen arrivals: no key joins until the sketch has seen a hundred, and after that a key joins only when its estimate is at least 0.3% of the arrivals so far. On Zipf 1 that list cost 197 words, 160 of them a sketch of thirty-two columns and five rows, where the best list that decides nothing — one candidate, kept whatever arrives — ran on sixteen columns and cost 159.

A second look at the same sketch tried to make sixteen columns enough by asking the sketch again, thousands of arrivals later, before admitting a key. It found the second look repeats the first. A light key that the sketch overrates is overrated because one of its five cells is shared with a heavier key, the median of its five readings lands on that heavier key’s count, and that count only grows; asked again later, the sketch overrates it again. Counting the key exactly for a thousand arrivals before admitting it was an independent witness and did let sixteen columns decide — but at 615 words, because every light key the sketch overrates must be counted while it is tested.

That essay’s closing section named the witness between them: a second Count-Sketch, with its own hash functions, independent of the first and costing a fixed amount however many keys it is asked about. Split the thirty-two columns into two sketches of sixteen; update both at every arrival; admit a key only when both estimates clear the bar, and enter it at the lower of the two. The prediction was that a light key sharing a heavy key’s cell 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%, bringing Zipf 1 under 185 words — and that two sketches of eight columns, 80 words, stay infeasible, since at eight columns each sketch alone overrates hundreds of keys. The risk: two witnesses that must agree refuse a key at the bar whenever either underrates it.

Two witnesses of half the width

Everything is the earlier essays’ except the sketch. Sixty thousand arrivals over 2,048 keys at Zipf exponents from 0 to 2; 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; enough copies of the sampling estimator for the light part 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 seeds, two a copy — and every design is run at whichever width makes it cheapest.

The pair takes the same number of columns as one sketch and divides them — each sketch, like a sketch that is allowed to be under, asked about a bar rather than for an estimate: thirty-two columns in all is two sketches of sixteen, five rows each, so the sketch costs the same 160 words either way. Each sketch has its own hashes, drawn from a different seed. A key not on the list is admitted only when the lower of its two estimates clears the bar, and that lower estimate is the value it enters at; once on the list it is counted exactly, as before, and neither sketch is consulted again. There is no wait and no second look; independence is the only thing added.

The hero plate is where the words go on Zipf 1. One sketch of thirty-two columns spends 160 words of sketch, 15 of list and 22 of copies, 197 in all. Two sketches of sixteen spend the same 160 and 15, and 8 of copies: 183. Two sketches of eight spend 80 of sketch, 27 of list and 42 of copies: 149, under the best fixed list’s 159. Probation, the last essay’s independent witness, spends 512 words on the counters it holds while it tests.

Half the columns, a tenth of the error

Split into two independent sketches, the same columns judge far better: the list's error on Zipf 1 is 0.8% of F3 at 32 columns against one sketch's 7.9%, and 8.2% at 16 against 47.4%; from 64 columns both are about a tenth of a per centThe root-mean-square error of the list's heavy part, as a share of F3, over sixteen seeds on Zipf 1, at each total number of columns: one sketch: 8 297.0%, 16 47.4%, 32 7.9%, 64 0.1%, 128 0.1%; two sketches, half each: 8 62.9%, 16 8.2%, 32 0.8%, 64 0.1%, 128 0.1%.0.1%1%10%100%columns of sketch in all (log scale)list's error, share of F3 (log scale)8163264128one sketchtwo sketches, half eachZipf 1, sixteen seedslist error, log scale
Fig. 1 The root-mean-square error of the list’s part of the estimate, as a share of the third moment, over sixteen seeds on Zipf 1, against the columns of sketch in all, for one sketch and for two sketches of half the columns each. At 32 columns: 7.9% and 0.8%. At 16: 47.4% and 8.2%.

Split into two independent sketches, the same columns judge far better: the list’s error on Zipf 1 is 0.8% of the moment at 32 columns against one sketch’s 7.9%, and 8.2% at 16 against 47.4%; from 64 columns both are about a tenth of a per cent. The first prediction holds by a factor of ten. The plate’s two curves are the same columns arranged two ways, and at every width below 64 the arrangement as two witnesses is between four and ten times more accurate.

The mechanism is the one the last essay found, turned round. A light key is overrated when one of its cells is shared with a heavy key, so its estimate reads the heavy key’s count; the sharing is a property of the hashes, which is why asking the same sketch again was useless. With two sketches, an overrated key must be overrated in both, which means sharing a heavy key’s cell under two independent sets of hashes. A sketch of sixteen columns overrates a light key with some small probability; two of them together overrate it with about the square of that probability, and taking the lower estimate as the entry value means the key enters at a count the more honest of the two witnesses gave.

The price is that each witness has half the columns. A sketch of eight columns is a poor estimator on its own — the earlier essay’s sketch at eight columns misjudged keys so badly that its list’s error was nearly three times the moment itself — but what the pair asks of each sketch is not an estimate. It asks whether a key is over a bar, and a key that two poor witnesses independently put over the bar is far likelier to be there than a key one good witness does.

The keys the pair lets in and keeps out

The risk arrived and did not matter: at 32 columns two sketches let 375 light keys onto the list at some point against one sketch's 706, and leave 11.1 of the 42 heavy keys out of it for the whole stream against 4.1 — keys the light-part sampler then countsZipf 1, averaged over sixteen seeds: light keys (under 0.003 of the stream) ever admitted to the list, and heavy keys (at least 0.003) never admitted, for one sketch and for two sketches of half the columns each: 16 columns, one sketch: 876.1 light in, 6.6 heavy out; 16 columns, two: 471.1 light in, 15.0 heavy out; 32 columns, one sketch: 705.9 light in, 4.1 heavy out; 32 columns, two: 374.8 light in, 11.1 heavy out; 64 columns, one sketch: 462.8 light in, 1.4 heavy out; 64 columns, two: 247.2 light in, 6.3 heavy out; 128 columns, one sketch: 255.4 light in, 1.0 heavy out; 128 columns, two: 155.6 light in, 2.7 heavy out.light keys ever on the listheavy keys never on it, of 4216 columns, one sketch8766.616 columns, two of 847115.032 columns, one sketch7064.132 columns, two of 1637511.164 columns, one sketch4631.464 columns, two of 322476.3128 columns, one sketch2551.0128 columns, two of 641562.7Zipf 1, sixteen seedskeys
Fig. 2 On Zipf 1, averaged over sixteen seeds: light keys ever admitted to the list, and heavy keys — at least 0.3% of the stream — never admitted, for one sketch and two sketches at 16, 32, 64 and 128 columns in all. At 32 columns: 706 light in and 4.1 heavy out for one sketch; 375 and 11.1 for two.

The risk the proposal named arrived, and did not matter: at 32 columns two sketches let 375 light keys onto the list at some point against one sketch’s 706, and leave 11.1 of the 42 heavy keys off it for the whole stream against 4.1. A witness that must agree with another refuses whenever either underrates, and the pair underrates a key at the bar about as often as either sketch does, twice; so the heavy keys near the bar, the marginal ones, are more often kept off. At every width the pair leaves out between two and four and a half times as many heavy keys as one sketch.

That should have cost accuracy, and the previous plate shows it did not. The asymmetry is in what each mistake costs the estimate. A light key let onto the list enters at an overrated count and is then counted exactly, so the list carries a wrong cube for it — the error the list’s part of the estimate measures. A heavy key kept off the list is not lost: it is part of the stream the sampling estimator covers, and the sampler estimates its contribution without bias, at the price of some variance. The pair trades the first kind of mistake for the second, and at 0.3% of the stream the heavy keys it keeps off are the lightest of the heavy, the ones whose cubes the sampler can carry.

The copies show the trade being paid. At 32 columns the pair needs four copies of the sampler against one sketch’s eleven, because its list’s error is so much smaller that the 10% budget leaves more room for the sampler’s variance. At 16 columns in all it needs twenty-one, because it keeps fifteen heavy keys out and the sampler’s variance grows with them; that is still cheaper than one sketch at 16 columns, which cannot reach 10% at any number of copies.

What the second sketch refuses

What the second sketch refuses: at 32 columns, 1,163 light keys that one of the two sketches put over the bar at some arrival were refused by the other, against 30.7 heavy keys — 9.6 of which were never admitted at allZipf 1, sixteen seeds, two sketches of half the columns each: keys that one sketch's estimate put over the bar at some arrival while the other's did not, by whether the key is light or heavy, and the heavy ones never admitted later: 16 columns: 1198.9 light, 31.1 heavy (12.8 never admitted); 32 columns: 1162.9 light, 30.7 heavy (9.6 never admitted); 64 columns: 1031.6 light, 27.2 heavy (5.3 never admitted).light keys refusedheavy keys refused16 columns1,199 · 31.132 columns1,163 · 30.764 columns1,032 · 27.2Zipf 1, two sketcheskeys refused
Fig. 3 For two sketches of half the columns each on Zipf 1: keys that one sketch’s estimate put over the bar at some arrival while the other’s did not, light or heavy, and the heavy ones never admitted later. At 32 columns: 1,163 light keys refused and 30.7 heavy, of which 9.6 never joined.

At 32 columns, 1,163 light keys that one of the two sketches put over the bar at some arrival were refused by the other, against 30.7 heavy keys — 9.6 of which were never admitted at all. The plate is the pair’s decisions read off directly. Each refusal is a moment when the two witnesses disagreed about a key, and nearly all of them, 97%, were about a key that is in fact light. The second sketch is doing what the proposal wanted: catching the light keys whose single-sketch estimate was another key’s count.

The heavy refusals are the risk, and the plate shows its size. About thirty of the 42 heavy keys were refused at some arrival, which is to say that most heavy keys are near the bar at some point early in the stream, where the bar is low and their counts are small. Most of those were admitted later, when their counts had grown past both sketches’ errors; nine or ten were not, at 32 columns, because they hover near 0.3% of the stream for its whole length. Those are the keys the sampler covers.

The ratio barely changes with width. At 16 columns in all the pair refuses 1,199 light keys and 31 heavy; at 64, 1,032 and 27. A wider pair admits fewer light keys in the first place, so it has fewer to refuse, but it disagrees about heavy keys at almost the same rate, because those disagreements are about counts near the bar, which no width removes.

Where the columns go

Words for 10% on Zipf 1 against the columns: one sketch is infeasible below 32 columns and cheapest there at 197; two sketches are feasible from 16 columns in all, cheapest there at 149, and the two curves meet from 64 columns, where the sketch itself is most of the wordsWords a 10% estimate of F3 needs on Zipf 1 at each total number of columns, for one Count-Sketch and for two of half the columns each with independent hashes (infeasible where the list's own error exceeds 10%): one sketch: 8 infeasible, 16 infeasible, 32 197, 64 338, 128 656; two sketches: 8 infeasible, 16 149, 32 183, 64 340, 128 657.200400800columns of sketch in all (log scale)words for 10% (log scale)8163264128×××two sketchesone sketch× infeasibleZipf 1, F3 to 10%words, log scale
Fig. 4 Words a 10% estimate needs on Zipf 1 against the columns of sketch in all, for one sketch and for two of half the columns each; × marks a width at which the list’s own error exceeds 10%. One sketch: infeasible at 8 and 16, 197 at 32. Two: infeasible at 8, 149 at 16, 183 at 32.

Words for 10% on Zipf 1 against the columns: one sketch is infeasible below 32 columns and cheapest there, at 197; two sketches are feasible from 16 columns in all and cheapest there, at 149; the two curves meet from 64 columns, where the sketch is most of the words. The proposal’s second prediction fails in the direction the strand had been trying to reach. Two sketches of eight columns, eighty words of sketch, were expected to be infeasible, on the reasoning that each would overrate hundreds of keys. Each does — the pair at that width lets 471 light keys onto the list at some point — but they overrate different keys, and the list’s error is 8.2% of the moment, inside the 10% budget with room left for twenty-one copies of the sampler.

At four columns each, eight in all, the pair fails too: its list’s error is 63% of the moment, and no number of copies brings that under 10%. The witnesses are then so poor that agreement between them is no longer rare. Somewhere between four and eight columns a sketch stops being worth asking.

From 64 columns up the arrangement does not matter. One sketch at 64 columns has a list error of a tenth of a per cent, the pair the same, and both cost about 340 words, nearly all of it sketch. Independence is worth most where the columns are scarce, which is exactly where the strand had been stuck: the waiting list needed thirty-two columns to decide, the second look could not make sixteen decide, and two sketches of eight decide well enough.

Every exponent

Across the exponents, two sketches beat the waiting list at 7 of 7 and the best fixed list at Zipf 0, 0.25, 0.5, 0.75, 1; on the flat stream the plain sampler still needs the fewest words, and at Zipf 1.5 and 2 the best fixed list keeps a few words' leadWords a 10% estimate of F3 needs on 60,000 arrivals over 2,048 keys at each Zipf exponent, each design at its cheapest setting: Zipf 0: plain sampler 206, best fixed list 985, waiting list 2,856, two sketches 690 (pair at 64 columns). Zipf 0.25: plain sampler 676, best fixed list 1,889, waiting list 3,271, two sketches 1,342 (pair at 128 columns). Zipf 0.5: plain sampler 5,260, best fixed list 1,526, waiting list 1,766, two sketches 1,064 (pair at 128 columns). Zipf 0.75: plain sampler 3,930, best fixed list 358, waiting list 380, two sketches 259 (pair at 32 columns). Zipf 1: plain sampler 1,882, best fixed list 159, waiting list 197, two sketches 149 (pair at 16 columns). Zipf 1.5: plain sampler 632, best fixed list 51, waiting list 171, two sketches 65 (pair at 8 columns). Zipf 2: plain sampler 372, best fixed list 45, waiting list 88, two sketches 48 (pair at 8 columns).1003001,0003,00000.2500.5000.75011.502Zipf exponent of the streamwords for 10% (log scale)plain samplerwaiting listtwo sketchesbest fixed list60,000 arrivals, 2,048 keys, F3words, log scale
Fig. 5 Words a 10% estimate needs at each Zipf exponent, each design at its cheapest setting: the plain sampler, the best fixed list, the waiting list and two sketches. Zipf 1: 1,882, 159, 197 and 149. Zipf 0.5: 5,260, 1,526, 1,766 and 1,064. Zipf 2: 372, 45, 88 and 48.

Across the exponents, two sketches beat the waiting list at all seven and the best fixed list at Zipf 0 to 1; on the flat stream the plain sampler still needs the fewest words, and at Zipf 1.5 and 2 the best fixed list keeps a lead of three to fourteen words. Neither the waiting list nor either kind of second look beat the best fixed list at any exponent; the pair beats it from the flat stream to Zipf 1, by between 6% at Zipf 1 and about 30% from Zipf 0 to 0.75. That is where the list’s decisions matter most: streams with many keys near the bar, where a sketch’s errors decide who is counted.

At the two ends the pair has nothing to decide. On a steep stream a single key dominates the moment, every design finds it at once, and the fixed list of one candidate wastes nothing; the pair’s best there runs on eight columns in all and still pays for a second sketch it hardly needs. On the flat stream no key is heavy and the plain sampler, with no sketch and no list, is cheapest of everything at 206 words. A share of a list of equals found the best fixed list itself changing shape across this range — one candidate on steep streams, sixteen at Zipf 0.5 — and the pair’s advantage follows the same line: a list is worth deciding about only when some keys are heavy and none dominates.

Width or independence

The question the proposal closed on was whether a decision needs width or independence — whether thirty-two columns are worth more as one sketch or as two witnesses. On these streams it is independence, by a wide margin, wherever the columns are fewer than sixty-four. The earlier essay showed why repetition is worthless: asking the same witness twice gets the same answer. This one shows that a second witness is worth more than a better first one, because the errors a sketch makes are collisions, and collisions under independent hashes are independent events.

That is the same observation that makes a Count-Sketch work in the first place. A sketch takes the median of five rows because five independent rows rarely collide on the same heavy key; the estimate that is a median of means measured what such a median buys by counting its failures. The pair extends the idea from rows to whole sketches, and asks for agreement rather than a median: the lower of two medians, each over five rows. The median protects an estimate; the agreement protects a decision, and the list needed a decision protected more than it needed an estimate made more exact.

What independence does not buy is any help with the marginal keys. Two witnesses refuse keys near the bar more often than one, and the estimate pays for those keys in sampler copies. Here the copies were cheap enough; on a stream whose heavy keys all sat near the bar, the trade could go the other way.

What the measurement leaves out

One stream length, one alphabet, one moment. Sixty thousand arrivals over 2,048 keys, the third moment, a 10% target. A longer stream lets the bar rise further above the sketch’s errors and would help both designs.

Two witnesses, never three. The pair splits its columns in two; three sketches of a third each, or two of unequal widths, were not measured.

Entry at the lower estimate. The pair enters a key at its lower reading; the mean of the two, or the first sketch’s, were not tried.

Still open: a witness that is only asked

The pair spends half its columns on the second sketch, and that sketch is used for one thing: to veto keys the first wants to admit. It never estimates anything the list keeps. A witness that is only asked whether a key is over the bar need not be a Count-Sketch at all; it needs one-sided error in the right direction and nothing else. A count-min sketch of the same words gives an estimate that is never under a key’s count, so a key it puts under the bar is certainly under it; or the second witness can be a narrower Count-Sketch than the first, since it is asked a yes-or-no question.

The measurement that follows keeps the first sketch at sixteen columns and varies the second — a Count-Sketch of four, eight and sixteen columns, a count-min of the same words — charging every word, on the same streams. The prediction is that on Zipf 1 a second Count-Sketch of eight columns beside a first of sixteen reaches the pair’s 0.8% list error for 120 words of sketch, and the whole estimate under 145 words; and that a count-min witness does worse, because a key it overrates it never vetoes, and overrating is the only mistake the witness exists to catch. It could fail on the narrow witness: a sketch of four columns agrees with almost anything, and if the useful width of a witness is the same as the width of the sketch it checks, the pair’s symmetry is already the cheapest arrangement. The question is how little a witness has to know to be worth asking.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

The objects this essay names

Each one links to every other essay that touches it.

Count-SketchHash collisionHeavy hitterPeak spaceSamplingThresholdZipf distribution