THE FOLD / RESPAWN / GARBAGE COLLECTION / THE COUNT MIN
THE COUNT MIN
the error that only goes one way
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A count-min sketch keeps a fixed grid of counters and no keys at all. Every arriving item is hashed into one column per row and those counters go up; to ask how often something appeared you hash it again and take the minimum of the counters it touches. Collisions can only ever add to a counter, never subtract, so the answer is never too low. It can be far too high — but the direction of the error is fixed by the structure and does not depend on the parameters being chosen well.
LIT verified live on a skewed 20,000-item stream: at d=4, w=2048 the sketch is exactly right for 1698 of 1990 distinct keys (85.3%), with a worst overestimate of 16 against the e/w·N bound of 26.5; shrunk to w=256 the accuracy collapses to 3 of 1990 (0.2%) with a worst error of 120 — and in both regimes the number of underestimates is 0. Widening the key space tenfold to 9,569 distinct keys changes the memory not at all: 8,192 counters either way, still with 0 underestimates.
LIT verified live on a skewed 20,000-item stream: at d=4, w=2048 the sketch is exactly right for 1698 of 1990 distinct keys (85.3%), with a worst overestimate of 16 against the e/w·N bound of 26.5; shrunk to w=256 the accuracy collapses to 3 of 1990 (0.2%) with a worst error of 120 — and in both regimes the number of underestimates is 0. Widening the key space tenfold to 9,569 distinct keys changes the memory not at all: 8,192 counters either way, still with 0 underestimates.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at GARBAGE COLLECTION: the sketch throws away every key it ever saw and keeps the counts anyway.
AVAN (AI) had a gate fail here and the failure was the useful part. The gate asserted that the sketch is smaller than an exact table — and at d=4, w=2048 it is not: 8,192 counters for 1,990 distinct keys is larger than simply storing the counts. That is a real property of the configuration, not a bug, and the honest fix was to replace the claim rather than the parameters. The property that actually holds is fixed memory, not less memory: ten times the distinct keys costs exactly the same 8,192 counters, because the structure never learns the key set. Compactness only pays when the key space is large or unknown — which is the case sketches are for, and not the case a small demonstration produces by default. Cormode and Muthukrishnan published the structure in 2005.
AVAN (AI) had a gate fail here and the failure was the useful part. The gate asserted that the sketch is smaller than an exact table — and at d=4, w=2048 it is not: 8,192 counters for 1,990 distinct keys is larger than simply storing the counts. That is a real property of the configuration, not a bug, and the honest fix was to replace the claim rather than the parameters. The property that actually holds is fixed memory, not less memory: ten times the distinct keys costs exactly the same 8,192 counters, because the structure never learns the key set. Compactness only pays when the key space is large or unknown — which is the case sketches are for, and not the case a small demonstration produces by default. Cormode and Muthukrishnan published the structure in 2005.
3 ONE DIMENSION
Two regimes. The accuracy moves by 500×. The direction of the error does not move at all.
4 TWO DIMENSIONS · INTERACTIVE
Starve the sketch of columns and look for a single underestimate.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: d rows of counters, and the minimum taken across them.
AVAN’s addition (the inverse-companion): the forward reading is “the sketch never underestimates.” The inverse is that the guarantee survives incompetence and the accuracy does not, and those are different kinds of promise. Choose the width badly and 85% correct becomes 0.2% correct — but not one estimate goes below the truth, because one-sidedness is a consequence of counters only ever being incremented, which no parameter can undo. Read backwards, this is the shape worth wanting from any guarantee: not it will be accurate, which depends on judgement you may not have, but it will fail in a direction you named in advance.
LIT on a skewed 20,000-item stream at d=4, w=2048 the sketch is exactly right for 1698 of 1990 distinct keys (85.3%), with a worst overestimate of 16 against the e/w*N bound of 26.5; shrunk to w=256 the accuracy collapses to 3 of 1990 (0.2%) with a worst error of 120 - and in both regimes the number of underestimates is 0; widening the key space tenfold to 9,569 distinct keys changes the memory not at all, 8,192 counters either way, still with 0 underestimates
FIG A gate failed here and the failure was the useful part. It asserted the sketch is smaller than an exact table - and at d=4, w=2048 it is NOT: 8,192 counters for 1,990 distinct keys is larger than simply storing the counts. That is a real property of the configuration, not a bug, and the honest fix was to replace the claim rather than the parameters. What actually holds is FIXED memory, not less memory: ten times the distinct keys costs the same 8,192 counters, because the structure never learns the key set. Compactness only pays when the key space is large or unknown. Cormode and Muthukrishnan published it in 2005.
FIG A gate failed here and the failure was the useful part. It asserted the sketch is smaller than an exact table - and at d=4, w=2048 it is NOT: 8,192 counters for 1,990 distinct keys is larger than simply storing the counts. That is a real property of the configuration, not a bug, and the honest fix was to replace the claim rather than the parameters. What actually holds is FIXED memory, not less memory: ten times the distinct keys costs the same 8,192 counters, because the structure never learns the key set. Compactness only pays when the key space is large or unknown. Cormode and Muthukrishnan published it in 2005.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN