Count-Min sketch
On the roadmap:Staff Engineer · step 2: Approximate answers at scale
Count how often each item appears in a fast stream using a small fixed table. Estimates can be too high but never too low.
In plain words
A grid of counters and several hash functions. To count an item, each row's hash picks one counter and adds one. To ask for a count, read the same counters and take the smallest. Other items may have added to those counters, so the answer can be too high, but never too low.
Why it matters
Counting every different item exactly needs memory for all of them. A sketch stays the same small size however many different items arrive, which makes counting practical for busiest pages, trending topics and traffic at huge scale.
Where you meet it
- Frequency estimates inside Caffeine's TinyLFU cache admission, using a compact 4-bit counter table
- Finding the most frequent items, such as trending searches or heavy network flows
- Streaming and monitoring systems that cannot store every item
You will be able to
- Size a sketch from an error margin and a confidence
- Explain why estimates are never too low
- Say when an exact count or a top-k structure is the better tool
In interviews
Comes up for 'top K frequent items', trending topics and any counting problem too big for a hash map.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- A table of counters: depth rows by width columns
- Sizing the table from an error margin and a confidence
- add() that bumps one counter in every row
- estimate() that takes the smallest of those counters
/** A seeded string hash: FNV-1a followed by a murmur-style finaliser. A different seed gives an independent-looking hash. */
function hash(s: string, seed: number): number {
let h = (0x811c9dc5 ^ Math.imul(seed + 1, 0x9e3779b1)) >>> 0;
for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
return h >>> 0;
}
export class CountMinSketch {
readonly width: number;
readonly depth: number;
readonly table: Uint32Array[]; // depth rows of width counters (public so a picture can show them)
total = 0;
/** epsilon: how far above the true count an estimate may be, as a share of all items counted. delta: the chance it is further above than that. */
constructor(epsilon: number, delta: number) {
this.width = Math.ceil(Math.E / epsilon);
this.depth = Math.max(1, Math.ceil(Math.log(1 / delta)));
this.table = Array.from({ length: this.depth }, () => new Uint32Array(this.width));
}
add(item: string, count = 1): void {
this.total += count;
for (let r = 0; r < this.depth; r++) this.table[r][hash(item, r) % this.width] += count;
}
/** Never below the true count. Other items sharing a counter can only push it up, so the smallest of the rows is the best guess. */
estimate(item: string): number {
let best = Infinity;
for (let r = 0; r < this.depth; r++) best = Math.min(best, this.table[r][hash(item, r) % this.width]);
return best;
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints count-min-sketch ok when everything passes. You need Node.js installed.
mkdir count-min-sketch && cd count-min-sketch
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Caffeine's cache admission uses a compact table of small counters of this kind, so it can tell which keys are used often without storing them all.
- Sketches built on different machines can be merged by adding their tables, so counting can be spread out and then combined.
- Systems pair the sketch with a short list of the current top items, because a sketch alone cannot list what it has counted.
- Counters are often only a few bits wide and are aged over time so that old popularity fades.
Ways to count at scale
| What it answers | Memory | Accuracy | Pick it when | |
|---|---|---|---|---|
| Count-Min sketch | How many times was this item seen? | Fixed and small | Never too low, can be too high | You need counts for a huge or unknown set of items |
| Hash map of counts | The exact count per item | Grows with the different items | Exact | The different items fit in memory |
| HyperLogLog | How many different items were seen? | A few kilobytes | Typically a few percent off | You need distinct counts, not per-item counts |
| Bloom filter | Was this item seen at all? | A few bits per item | Can say yes wrongly | You need membership, not counts |
| Sorting a log of events | Exact counts after the fact | Disk and time | Exact | Batch reports |
What it cannot do
It can only over-count
Collisions add to a counter, so rare items can look more common than they are. Heavy items are estimated best.
It cannot list items
It stores counts, not names, so you need another structure to know what to ask about.
Accuracy depends on the total
The error is a share of everything counted, so a small count in a huge stream can be swamped by it.
Items cannot simply be removed
Subtracting can push a counter below a true count, so the never-too-low guarantee is lost.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Track the ten most frequent items with a small heap beside the sketch
- Make old counts fade so recent popularity wins
- Merge two sketches built on different machines by adding their tables