THE FOLD / GLITCH / OFF BY ONE / THE COUNT-SKETCH
THE COUNT-SKETCH
a frequency estimate the median cleans up
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Count-Sketch estimates how often items appear in a stream using tiny memory — and, unlike its cousin Count-Min, it is unbiased. Each row hashes an item to a bucket and multiplies by a random ±1 sign before adding; the estimate reads that bucket back, times the same sign. Collisions from other items come in with random signs, so on average they cancel — the single-row estimate is correct in expectation. Taking the median across several rows crushes the variance, giving a sharp estimate in a fixed footprint.
LIT verified live: the average single-row estimate of a target’s count converges to its true frequency (unbiased), and the median across rows has far smaller error than any single row (window.__count_sketch). FIG no framing; the signed counters and the median estimate run in-browser.
LIT verified live: the average single-row estimate of a target’s count converges to its true frequency (unbiased), and the median across rows has far smaller error than any single row (window.__count_sketch). FIG no framing; the signed counters and the median estimate run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at off-by-one — a frequency read that is only ever off by a little, its collision noise cancelling to a near-exact count. AVAN (AI) built the instrument: the signed hash counters, the unbiasedness check across many sketches, and the median-of-rows variance reduction.
Credit as content: Moses Charikar, Kevin Chen & Martin Farach-Colton (2002). The weave: David names the off-by-one; I confirm the estimate is unbiased and that the median across rows beats a single one.
Credit as content: Moses Charikar, Kevin Chen & Martin Farach-Colton (2002). The weave: David names the off-by-one; I confirm the estimate is unbiased and that the median across rows beats a single one.
3 ONE DIMENSION
An item hashes to a bucket and adds ±1; the estimate reads that bucket times the item’s sign, so other items’ signs cancel on average.
4 TWO DIMENSIONS · INTERACTIVE
Stream items into several signed sketches; the single-row estimates scatter around the true count, and their median lands on it.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the median estimate, sitting on the true count.
AVAN’s addition (the inverse-companion): don’t fight collisions — sign them so they cancel. The inverse of ‘a collision adds error’ is ‘a random ±1 sign makes collisions cancel in expectation, and the median kills the variance.’ Magenta is a single-row estimate’s scatter; green is the median on target. Sign the noise away.
LIT Genuine Count-Sketch (Moses Charikar, Kevin Chen & Martin Farach-Colton, 2002): signed hash counters give an unbiased frequency estimate; median-of-rows reduces variance. Verified live: the mean single-row estimate converges to the true count (window.__count_sketch.unbiased), and the median-of-15 error is far below a single row's (.medianBeatsSingle).
FIG No framing: the signed counters, the unbiasedness check across many sketches, and the median-of-rows variance reduction all run in-browser. The AVAN inverse is honest — attaching a random ±1 sign so collisions cancel in expectation (and the median kills the variance) rather than treating a collision as pure error is exactly what makes Count-Sketch unbiased; magenta is the single-row scatter, green the median on target. Sign the noise away.
FIG No framing: the signed counters, the unbiasedness check across many sketches, and the median-of-rows variance reduction all run in-browser. The AVAN inverse is honest — attaching a random ±1 sign so collisions cancel in expectation (and the median kills the variance) rather than treating a collision as pure error is exactly what makes Count-Sketch unbiased; magenta is the single-row scatter, green the median on target. Sign the noise away.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of OFF BY ONE · David Lee Wise (ROOT0), with AVAN