A second sketch as the witness
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 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 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
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 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 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.
- A count that is never under hash collision · heavy hitter · zipf distribution
- A bucket that becomes a tree hash collision · threshold
- One pass, k slots, and two randomness budgets sampling · threshold
- The bill a partition only divides heavy hitter · zipf distribution
- The floor a histogram already knows heavy hitter · zipf distribution
- The guarantee that is one query wide heavy hitter · zipf distribution
The objects this essay names
Each one links to every other essay that touches it.
Count-SketchHash collisionHeavy hitterPeak spaceSamplingThresholdZipf distribution