---
topic: system-design
author: Crashtech Editorial
published: Nov 13, 2026 · read: 3 min
---

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.

– –

“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

How many distinct items? HyperLogLog
Unique visitors, distinct search queries, distinct IPs. A few kilobytes per counter regardless of how many items you feed it.
How often does each item appear? Count-Min Sketch
Trending hashtags, hot keys, noisy clients. Never undercounts, which makes it safe for finding the heavy hitters.
How similar are these two sets? MinHash
Near-duplicate documents, similar user interest sets, plagiarism checks. Compares compact signatures instead of full sets.
Have I seen this before? Bloom / Cuckoo filter
Membership checks. Cuckoo filters add one feature plain Bloom filters lack: you can delete items.

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) ]
Why one-sided error is a feature

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.

Advertisement

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

NeedUseYou trade away
Unique countHyperLogLogExactness, and you cannot list the items
Frequency / top itemsCount-Min SketchOvercounts by a bounded amount
Set similarityMinHashExactness of the similarity score
Membership with deletesCuckoo filterSmall 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.

Advertisement

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.

Sources & further reading

/* Comments */