Expert · Module 24 · Lesson 2 of 4
Count-min sketch
The count-min sketch compresses a stream into a few rows of counters: an update is a couple of increments, a query reads the smallest counter, and the answer can overshoot by a bounded amount but never undershoot.
By the end you can
- Trace how each stream item increments the counters and how a query reads them back
- Explain why a count-min estimate can be too high but can never be too low
- Choose the sketch's width and depth from an error target and a confidence target
Builds on What a hash function does, Top-k and merging streams.
01 · A question first
A network monitor must count packets per address for millions of addresses, but it sees each packet exactly once and cannot store them. Ask it about one address and it may answer a little high — never low — from a few kilobytes no matter how long the stream runs. How can a count be wrong in only one direction, and what decides the size of the miss?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Counting a stream you cannot keep
- Two rows of counters
- Why the answer only overshoots
- Choosing width and depth
- What it costs, and the standard variations
- Where count-min sketches do the work
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem