How HyperLogLog counts unique items without remembering them

What problem does HyperLogLog solve?

Many systems need to know how many different things they have seen, not how many things in total. A router may want the number of unique IP addresses in its traffic, a website the number of unique visitors, a biologist the number of distinct patterns in a DNA sequence. This is called the count-distinct problem, or cardinality estimation.

The obvious approach keeps a dictionary, such as a hash table, and adds each new item only if it is not already there. That gives an exact answer, but the dictionary grows with every new distinct item. When the stream is enormous, or memory is fixed, the exact method stops being practical. HyperLogLog accepts an approximate answer in return for memory that stays tiny and fixed.

How does it work, step by step?

The core idea comes from a property of random numbers. If numbers are uniformly random, a binary number starting with many zeros is rare. Seeing one whose longest run of leading zeros is n suggests that roughly 2 to the power n different numbers have gone by. Rare patterns only turn up once there are many attempts.

Real data is not random, so HyperLogLog first passes every item through a hash function. Identical items always produce the identical hash, so repeats change nothing, while different items behave like random numbers. The algorithm keeps an array of m small counters called registers, all starting at zero. To add an item, it takes the first few bits of the hash to choose a register, then looks at the remaining bits and finds the position of the first 1. If that position beats the value already in the register, the register is updated.

A single maximum is a noisy signal, because one lucky hash can throw the guess far off. So to count, HyperLogLog combines all the registers with a harmonic mean, which resists being dragged upward by a few extreme values, and multiplies by a correction constant that removes a known systematic bias. The result is an estimate of how many distinct items have been added.

What does a small worked example look like?

Imagine a toy version with 4 registers watching a stream of visitor names. Each name is hashed. Two bits of the hash pick one of the 4 registers, and the rest of the bits are scanned for the first 1. Suppose a name lands in register 3 and its first 1 appears at position 2: register 3 now holds 2. A later name lands in register 3 with its first 1 at position 5, so register 3 rises to 5. When a returning visitor appears, the same hash lands in the same place with the same value, and nothing changes.

After thousands of names, each register holds a rough clue about how many distinct names fell into its bucket. No register knows any name, yet together they support a reasonable estimate of the total. Four registers would still be very noisy; real sketches use many more, and the expected error shrinks as 1.04 divided by the square root of m.

Where is HyperLogLog used, and what can it do?

HyperLogLog has three main operations: add an item, count the estimated number of distinct items, and merge two sketches. Merging is simple and powerful. For each register position, keep the larger of the two values, and the result is a sketch of the union of both sets. Counts kept separately on different machines or for different days can therefore be combined later without revisiting the raw data. Using the inclusion-exclusion principle, rough sizes of intersections and differences can also be derived from merges and counts.

In practice, the count-distinct literature describes HyperLogLog as the estimator usually chosen among sketches that track minimum or maximum hashed values. The Redis database offers it, treating count and merge as constant-time because its number of registers is fixed. An extended version also handles a weighted variant of the problem, where each distinct element carries a weight and the goal is the total weight.

Where does it fail or get misused?

HyperLogLog only approximates. It should not be used where an exact count matters, such as billing or legal records. Its raw estimate is also biased when the true count is small, below about two and a half times the number of registers. The original design switches to a different method, Linear Counting, based on how many registers are still zero, in that range. Very large counts that approach the limit of 32-bit registers need a separate correction too.

Later variants address these weak spots. HyperLogLog++ uses a 64-bit hash to cut collisions, adds an empirical bias correction for small counts, and stores registers sparsely while the count is small. When data arrives as a single stream, other estimators can reach the same error with noticeably less memory, though some of them give up the ability to merge sketches.

What does HyperLogLog teach about thinking?

HyperLogLog shows that a good enough answer can be far cheaper than a perfect one. Knowing whether a site has about a million or about two million visitors is often all a decision needs, and paying for exactness would mean storing every visitor. It also shows how aggregating many weak, noisy signals produces a stable estimate, provided the method of combining them is robust to outliers. And it is a reminder that a summary is not the data itself: the sketch can say roughly how many, but never which ones.

Questions people ask

The thinking behind it

• map is not the territory
• signal vs noise
• diminishing returns

More algorithms, explained

• How consistent hashing works
• How reservoir sampling picks a fair sample from an endless stream
• How the A* search algorithm works
• How the count–min sketch works