A website sees hundreds of millions of events.
The question is not how many events occurred.
It is:
How many different users, devices, queries or objects appeared?
Exact distinct counting can require a large set of identities.
HyperLogLog takes a startlingly different route.
It forgets the identities and keeps statistical evidence about how many identities there probably were.
Quick Read
HyperLogLog is a probabilistic algorithm for estimating cardinality: the number of distinct elements in a multiset or stream. Rather than storing every unique item, it hashes items and records compact information about patterns in the hash outputs. Those patterns are used to estimate how large the unseen distinct set must have been.
One-sentence answer: HyperLogLog is lossy because it discards the identities and exact membership of distinct items while preserving enough statistical structure to estimate the size of the unique set with small, quantifiable relative error.
Why Distinct Counting Is Harder Than Ordinary Counting
Count every event and one integer is enough.
Count distinct items and repetition becomes the problem.
If the same identifier appears one million times, it should contribute one to cardinality.
An exact solution therefore needs some way to remember which identities have already appeared.
At large scale, that exact set can dominate memory.
The Strange Clue Hidden in Leading Zeros
Imagine hashing items so the resulting bit strings behave approximately like random binary sequences.
A string beginning with one zero is common.
Two leading zeros are less common.
Ten leading zeros are rare.
If you observe a very rare leading-zero pattern, that suggests you probably sampled many distinct hash values before encountering it.
HyperLogLog turns this rare-event logic into a cardinality estimator.
One Maximum Is Too Noisy
Using only the single longest leading-zero run would be unstable.
A lucky rare hash could make the set look much larger than it is.
So HyperLogLog divides the hashed stream into many registers or buckets and tracks compact statistics within each.
Combining many register observations produces a much more stable estimate.
The Register Is a Tiny Memory of Extremeness
Each register records only a small number related to the most extreme qualifying hash pattern seen for that bucket.
It does not know which item produced that pattern.
It does not know how many duplicates occurred.
It remembers only a statistic that helps estimate cardinality.
This is extreme task-shaped compression.
Duplicates Naturally Disappear
Hash the same item repeatedly and it produces the same bucket and rank pattern.
Once that register has already seen an equal or more extreme value, repeated duplicates change nothing.
This is exactly what a cardinality estimator wants.
Frequency disappears because only uniqueness matters.
More Registers, Lower Relative Error
Allocate more registers and the estimator generally becomes more precise.
Use fewer registers and memory falls while uncertainty rises.
The trade-off is transparent: memory buys statistical precision rather than exact storage.
The Error Is Relative
HyperLogLog is attractive because its uncertainty scales with the size of the estimate in a predictable way for a chosen register count.
An estimate around one million might be wrong by thousands while still being extremely useful operationally.
For many dashboards, capacity-planning systems and large-scale analytics, “about 1.01 million distinct users” is more useful than spending huge memory to preserve exact identities merely to display a rounded total.
Small-Cardinality Behaviour Needs Special Care
At very small cardinalities, the ordinary asymptotic behaviour of a sketch can be less efficient than methods that exploit the many still-empty registers.
Practical implementations often include corrections or alternative estimation regimes.
The larger lesson is important: approximate algorithms usually have operating regions. One formula is not automatically optimal everywhere.
Hash Quality Matters
The estimator relies on hash outputs behaving sufficiently like a uniform random distribution for the statistical assumptions to hold.
A poor hash can bias bucket occupancy or leading-zero statistics.
The sketch may be tiny, but its truthfulness depends on the transformation that feeds it.
HyperLogLog Is Mergeable
This is one of its great systems advantages.
Suppose Singapore, London and New York each maintain compatible sketches of distinct visitors.
The sketches can be merged register by register, keeping the more extreme value for each position.
The merged structure estimates the distinct union without shipping every identifier to one place.
Approximation gains not only memory efficiency but distributed composability.
Merging Does Not Mean Adding
If Site A has one million users and Site B has one million users, the union is not necessarily two million.
The same people may appear in both.
HyperLogLog’s merge operation handles overlap because the sketches represent the union’s hash evidence rather than two independent totals that are simply summed.
Analytics Uses Cardinality Everywhere
Distinct users.
Distinct search terms.
Distinct IP addresses.
Distinct products viewed.
Distinct devices touching a service.
These counts can become enormous while the receiver often needs only a population-scale estimate.
Databases Can Offer Approximate DISTINCT Queries
Exact COUNT(DISTINCT ...) over huge datasets can require substantial sorting, hashing or distributed state.
Approximate cardinality functions based on sketching can answer much faster with controlled error.
This is a mature example of approximation becoming a first-class query contract rather than an implementation embarrassment.
Privacy Can Improve Incidentally—but HyperLogLog Is Not a Privacy Guarantee
A HyperLogLog sketch does not retain a plain list of identities, which can reduce direct exposure compared with storing the full set in fast analytical memory.
But that does not make the structure formally private.
Privacy requires its own threat model and mechanisms. A lossy representation can reduce accessible detail without satisfying a rigorous privacy definition.
Education: Unique Ideas Versus Total Mentions
A class discussion produces 200 comments.
How many distinct ideas appeared?
That question is structurally different from total participation.
HyperLogLog is not a classroom teaching tool in the ordinary sense, but the distinction is valuable: count events, count frequencies and count unique entities are three different information jobs.
When HyperLogLog Is Exactly the Right Loss
Use it when the distinct population is huge, exact identities are not needed by the immediate receiver, small relative error is acceptable, mergeability matters, and memory or network cost makes an exact set unattractive.
The algorithm shines when the output itself will eventually be a rounded population-scale number.
When HyperLogLog Becomes Dangerous
- An approximate count is used where exact legal, billing or safety totals are required.
- The estimate is compared against a hard threshold without accounting for uncertainty.
- Sketches built with incompatible parameters or hashes are merged.
- Poor hashing breaks the estimator’s statistical assumptions.
- The user assumes the sketch can identify which items were present.
- The exact source is deleted even though future audit or individual-level analysis may require it.
A Practical HyperLogLog Audit
- Question: is cardinality really the only quantity required?
- Error: what relative error is acceptable?
- Registers: how much memory is allocated?
- Hash: is hashing sufficiently uniform and stable?
- Merge: are distributed sketches compatible?
- Threshold: could estimation error change a consequential decision?
- Source: is richer exact data retained where necessary?
Continue Through eduKateSG
Continue with How Lossy Works | Count-Min Sketch, How Lossy Works | Bloom Filters, and the companion article How Lossy Works | Probabilistic Sketches.
Final Thought: Sometimes You Do Not Need to Remember Who—Only How Many Different Whos There Were
HyperLogLog is an elegant answer to a narrow question.
It gives up identity so scale can survive.
That is lossy design at its most disciplined.