How count-min sketches work – frequencies, but without the actual data (www.instantdb.com)

The post demonstrates a compact, from-scratch JavaScript implementation of Count‑Min Sketches inside Instant (a tiny sync engine), centered around a playful demo: a 50 KB sketch that approximates word counts for a 23 MB P. G. Wodehouse corpus with ~3.7M words, claiming ~0.05% error at 99% confidence. It shows why sketches matter: they give fixed-size, high-speed frequency estimates for massive vocabularies and streams — useful for detecting common passwords, estimating link views, and guiding database query planners (Instant uses sketches to pick indexes and join orders). Technically, a Count‑Min Sketch is a rows × columns matrix of counters (the author uses a flat Uint32Array for cache efficiency), with one independent hash per row. To add an item you hash it in every row and increment the mapped bucket; to query you take the minimum count across rows, which bounds overestimation caused by collisions. Columns trade off per-item error (ε), rows trade off confidence (δ) — more columns reduce collision bias, more rows reduce the chance all hashes collide badly. The post also covers practical bits: simple stemming for better aggregation, why a flat array helps CPU caches, and pragmatic serialization (JSON.stringify + zstd proved efficient in tests). Overall, it’s a clear, runnable walkthrough of a probabilistic structure that delivers “frequencies without the data.”