HyperLogLog is a probabilistic algorithm for estimating the number of distinct elements in a collection, a problem known as cardinality estimation. It represents the collection with a small array of registers rather than storing its individual elements. Under standard hashing assumptions, its relative standard error is approximately , where is the number of registers. Its compact representation, tolerance of repeated elements, and ability to combine independently constructed summaries make it useful in databases, stream processing, and distributed computing.
Purpose and background
Counting records is straightforward; counting distinct values requires recognizing repetitions. An exact solution can maintain a hash table containing every distinct value, but its memory consumption grows with the number of distinct elements. For datasets containing billions of identifiers, this can be expensive even when the desired output is only a single count.
HyperLogLog instead maintains a sketch: a compressed statistical summary from which an approximate answer can be computed. The sketch does not retain enough information to reconstruct the original collection or enumerate its members.
Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier introduced HyperLogLog in 2007. It developed earlier probabilistic counting techniques, particularly LogLog counting, by using a different aggregation method to improve accuracy for a given number of registers. Subsequent work introduced practical refinements, notably HyperLogLog++.
Hashing and the statistical principle
HyperLogLog applies a hash function to each input value. The algorithm treats the resulting bit strings as approximately independent, uniformly distributed random values.
For such a bit string, define as the position of the first 1, counting from 1. Thus:
- A string beginning with
1has . - A string beginning with
01has . - A string beginning with
001has .
The probability of observing at least leading zero bits is
Long runs of leading zeros are therefore rare. If many independently hashed values have been observed, longer runs become more likely. The longest observed run consequently provides information about the number of distinct inputs.
A single maximum is a noisy estimator. HyperLogLog reduces this variability by distributing hashed values among many registers and combining the information they retain.
Repeated occurrences of the same input produce the same hash and the same register update. They therefore have no additional effect after the first occurrence. This is the basis of distinct counting without explicitly tracking duplicates.
Register structure and updates
Choose a precision parameter , giving
registers. Each register initially contains zero.
Split each hash into:
- A -bit prefix selecting a register .
- A remaining suffix , used to compute .
For each input value , update
For a finite suffix consisting entirely of zeros, the rank is defined as one more than its length, or handled by an equivalent implementation convention.
The registers form a small array. Each stores a maximum rank, not an element count. Consequently, a register may remain unchanged after many new distinct elements arrive, while a single unusually long zero run may increase it substantially.
Some implementations use low-order bits for register selection or count trailing rather than leading zeros. These choices are statistically equivalent under suitable hashing assumptions, but sketches must use compatible conventions to be merged correctly.
Estimating the cardinality
The classical raw HyperLogLog estimate is
Here is a normalization constant. Common values are
with the usual approximation
for .
The reciprocal sum corresponds to a scaled harmonic mean of the register-derived quantities . Compared with an arithmetic mean, it limits the influence of unusually large register values.
Small-cardinality correction
The raw estimator performs poorly when many registers remain empty. In particular, it gives a positive estimate even for an empty sketch.
Let be the number of zero-valued registers. When , linear counting gives the alternative estimate
This uses the fraction of unoccupied registers to estimate how many distinct values were assigned to them. The classical HyperLogLog procedure uses this correction in its small-cardinality range, conventionally when the raw estimate is at most .
Modern implementations may use different switching thresholds, empirical bias corrections, or alternative estimators. “HyperLogLog” can therefore denote either the original estimator or the broader family of compatible register-based sketches.
Finite-hash correction
A finite hash space introduces collisions: different inputs can produce the same complete hash. At sufficiently large cardinalities, this causes undercounting independently of register-estimation error.
The original algorithm used 32-bit hashes and included a large-range correction. For a hash space of size , the correction has the form
This correction cannot recover the identities of colliding inputs, and estimates become unstable as the observed hash-space occupancy approaches saturation. Using 64-bit hashes greatly extends the practical range before finite-hash effects become significant.
Accuracy and memory use
Under the standard random-hash model, the classical estimator has an asymptotic relative standard error of approximately
Representative values are:
| Registers | Approximate relative standard error |
|---|---|
| 1,024 | 3.25% |
| 4,096 | 1.63% |
| 16,384 | 0.81% |
| 65,536 | 0.41% |
Reducing the standard error by a factor of two requires approximately four times as many registers.
These percentages are statistical measures, not guaranteed error bounds for every dataset. For a fixed hash function and fixed input collection, the output is deterministic. The probabilistic analysis concerns the behavior induced by random hashing; actual errors also depend on the estimator, hash quality, and cardinality range.
For a fixed -bit hash, a register needs to represent only values up to , together with its initial zero state. Thus a small number of bits per register is sufficient. A common dense representation uses six bits per register: 16,384 such registers require 12 KiB of register storage, excluding metadata and implementation overhead.
In the theoretical growing-range model, the familiar space complexity is
bits for target relative error on the order of . Practical fixed-width implementations instead allocate a fixed register budget and have a finite supported range.
Merging and distributed computation
Two compatible sketches can be merged by taking the register-wise maximum:
This produces exactly the register state that would result from processing all elements of both collections into one sketch. Overlapping elements do not require special handling.
The merge operation is:
- Associative: grouping merges differently does not change the result.
- Commutative: merge order does not matter.
- Idempotent: merging a sketch with itself changes nothing.
These properties support partitioned processing in systems such as MapReduce and incremental aggregation in data warehouses. Workers can transmit sketches instead of all distinct identifiers. Merging the sketches introduces no additional register-level approximation beyond that already inherent in the combined sketch.
Compatibility requires the same hash function, seed, input encoding, precision, and register interpretation, or an explicitly supported conversion. Merely having the same number of bytes is insufficient. Some higher-precision sketches can be reduced to a lower precision, but this requires accounting for the changed division between index bits and rank bits.
Computational cost
After hashing an input, a normal update reads and potentially modifies one register. Its time complexity is ; hashing a variable-length input also requires processing that input’s bytes.
A straightforward estimate scans all registers and costs . Implementations can maintain auxiliary statistics to accelerate repeated estimates. Merging two dense sketches also costs .
Unlike exact distinct-value storage, the dense sketch’s memory requirement does not increase as additional elements arrive. This makes it useful when the number of processed records is much larger than the memory budget.
HyperLogLog++ and implementation variants
HyperLogLog++ was described in 2013 by Stefan Heule, Marc Nunkesser, and Alexander Hall. Its engineering improvements include:
- 64-bit hashing, extending the useful cardinality range.
- Empirical bias correction, improving estimates in ranges where the raw estimator has systematic bias.
- Sparse representation, reducing storage for low-cardinality sketches.
- Refined transitions between estimators, improving small-range behavior.
Sparse representations store information about occupied positions rather than allocating every dense register immediately. Their details vary, and switching between sparse and dense modes affects storage and execution costs.
Later estimators can derive estimates from the register histogram without following the original correction scheme. Consequently, two systems using similar HyperLogLog register arrays need not return identical estimates.
Applications and limitations
HyperLogLog is used for approximate distinct-value aggregation, including unique visitors, distinct network addresses, event identifiers, and distinct values in SQL queries. Systems such as Redis provide HyperLogLog-based operations.
Several limitations distinguish it from an exact set representation:
It does not support membership queries. A sketch can estimate a count but cannot determine whether a particular element occurred.
Ordinary sketches do not support deletion. Registers retain maxima, not the observations responsible for them. Removing an element does not reveal which smaller rank should replace a maximum. Sliding-window applications therefore require additional structures, such as time-partitioned sketches.
Intersections and differences are not native operations. Union is directly mergeable, but estimating an intersection through
can amplify estimation error, especially when the intersection is small. Specialized estimators can exploit additional information in compatible sketch pairs, but register-wise minima are not an exact intersection operation.
Input representation matters. Inconsistent normalization, serialization, or treatment of missing values can make logically identical values hash differently. This is a data quality issue that the estimator cannot correct.
Hash assumptions matter. Poorly distributed hashes can bias both register selection and rank statistics. Deliberately chosen inputs can also undermine assumptions in adversarial settings. A cryptographic hash function is not required for ordinary non-adversarial workloads, although hash selection and seeding matter when inputs are untrusted.
Compactness is not a privacy guarantee. A sketch is not reversible in the same way as an explicit list, but its contents and changes may still disclose information. HyperLogLog does not, by itself, provide differential privacy.