System design · interactive
Top-K with a count-min sketch
Counting every search term exactly needs memory for every term. A count-min sketch uses a small fixed grid: each item adds to one counter per row, chosen by a different hash. Collisions only ever add, so the smallest of its counters is the best guess, and it never undercounts.
3 rows × 8 counters · stream: cat×9 dog×7 owl×5 fox×3 bee×2 elk×2 ant×1 yak×1 emu×1 gnu×1
bee: counters 12, 12, 11 → min = 11 (true 2, over by 9)
Top 3 by estimate: cat (11), bee (11), dog (7)
Other words landed in all of bee's counters, so even the smallest is inflated. Wider rows mean fewer collisions.
Look up
1 2 3 The least-collided counter is the closest. The error is bounded by width; the chance of a bad estimate by the number of rows.
Never undercounts.
4
In production
Tools and technologies
Sketches power trending lists and heavy-hitter detection.
Not tied to one language — use these names when you search docs or design a system.