Counting a Billion Things in 12 KB: HyperLogLog, Count-Min and MinHash
Exact counting costs memory that grows with the data. Sketches trade a little accuracy for a fixed, tiny footprint. Three to know and when to use each.
On this page
“How many unique users hit this endpoint today?” sounds trivial. Store every user ID in a set and call size(). Now do it for a billion events across 10,000 endpoints, and your analytics job needs more RAM than the service it is measuring. Sketches exist because, for most analytics questions, being right within one percent is the same as being right.
One question, one structure
HyperLogLog: unique counts from leading zeros
Hash every item to a uniformly random bit string. If you have seen a hash that starts with 10 zeros, you have probably seen on the order of 2^10 distinct items, because that pattern is that rare. A single such observation is noisy, so HyperLogLog splits the hash space into many buckets, keeps the longest zero-run per bucket, and combines them with a harmonic mean.
The accuracy is a formula, not a hope: standard error is about 1.04 / sqrt(m) for m buckets. With m = 16,384 buckets that is roughly 0.8 percent, and the whole structure fits in about 12 KB. Merging two sketches is just taking the max per bucket, so you can count uniques per hour and union them into uniques per day without re-reading the data.
Count-Min Sketch: frequencies with one-sided error
Keep a small grid of counters, d rows by w columns, each row with its own hash function. To record an item, increment one counter per row. To query, hash again and take the minimum of the d counters.
Collisions only ever add to a counter, so the minimum is always at least the true count: it can overestimate, never underestimate. Widen the grid to shrink the error, deepen it to shrink the failure probability.
estimate(item) = min over rows r of counter[r][ hash_r(item) ]
If you are hunting for items above a threshold, an overcount gives you a few false candidates you can verify cheaply. An undercount would make you miss a real heavy hitter. Count-Min’s error direction is exactly the safe one for that job.
MinHash: similarity without comparing sets
Jaccard similarity is intersection over union. Computing it exactly means touching both sets. MinHash uses a neat identity: for a random hash function, the probability that two sets have the same minimum hash equals their Jaccard similarity.
So compute, say, 128 minimum hashes per set (one per hash function) and store that signature. To compare two sets, count how many positions match and divide by 128. Combine with locality-sensitive hashing and you can find near-duplicates among millions of documents without all-pairs comparison.
Choosing and sizing
| Need | Use | You trade away |
|---|---|---|
| Unique count | HyperLogLog | Exactness, and you cannot list the items |
| Frequency / top items | Count-Min Sketch | Overcounts by a bounded amount |
| Set similarity | MinHash | Exactness of the similarity score |
| Membership with deletes | Cuckoo filter | Small false-positive rate |
Do
Use sketches for analytics, monitoring, rate limiting and candidate generation, where a small, bounded error is irrelevant to the decision.
Don't
Use them for money, inventory or compliance counts. If someone will ask “exactly how many”, store exactly.
Takeaway
Exact counting is a luxury of small data. At scale, a sketch gives you a fixed memory budget, mergeable partial results, and an error you can state in advance. Learn the question each one answers and you can replace several heavyweight jobs with a few kilobytes.
Frequently asked questions
What does HyperLogLog actually estimate?
The number of distinct elements in a stream, such as unique visitors, without storing the elements. It hashes each item and tracks, per bucket, the longest run of leading zeros seen. Rare long runs imply many distinct items. Its standard error is about 1.04 divided by the square root of the number of buckets.
Can a Count-Min Sketch undercount?
No. It can only overcount, because hash collisions add other items' counts to yours. You take the minimum across several hash rows, which trims the overcount. That one-sided error makes it safe for heavy-hitter detection, where you want to find big items and can tolerate a few false alarms.
How does MinHash estimate set similarity?
For a random hash function, the probability that two sets share the same minimum hash value equals their Jaccard similarity (intersection over union). Compute many such minimums per set, compare the signatures, and the fraction that match estimates the similarity, without comparing the full sets.
When should I not use a sketch?
When you need exact answers: billing, inventory, compliance counts. Sketches shine for analytics, monitoring, deduplication candidates and recommendations, where a one percent error is irrelevant but memory and latency are not.

/* Comments */
Comments are offline right now — we reconnect automatically, nothing is lost.