# HyperLogLog

**HyperLogLog** (HLL) is a probabilistic algorithm that estimates the number of distinct elements, the cardinality, in a large data set or stream, using a single pass over the data and a fixed, small amount of memory that does not grow with the cardinality being counted. It was introduced by [Philippe Flajolet](https://www.edgepedia.org/philippe-flajolet), Éric Fusy, Olivier Gandouet, and Frédéric Meunier in a 2007 paper published in the proceedings of the AofA 07 conference in *Discrete Mathematics and Theoretical Computer Science*.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup> Determining exact cardinality requires memory essentially proportional to the number of distinct elements, because every element seen must be remembered; HyperLogLog trades a small, characterizable error for constant memory.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup>

| Key fact | Detail |
|---|---|
| Question answered | How many distinct elements are in a stream, estimated in one pass without storing the elements<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup> |
| Standard error | About \( 1.04/\sqrt{m} \), where m is the number of registers<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup> |
| Memory | Fixed regardless of cardinality; with m = 2048 registers, 32-bit hashing, and 5-bit registers, cardinalities beyond 10<sup>9</sup> are estimated with about 2% accuracy in 1.5 kB<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup> |
| Mergeability | Two sketches merge by taking the per-register maximum, so partial counts can be unioned without rescanning data<sup>[2](https://synapse.kakde.eu/synapse/system-design-from-first-principles/building-blocks/probabilistic-data-structures)</sup> |
| Redis implementation | Native data type with PFADD, PFCOUNT, and PFMERGE; up to 12 KB of memory and a standard error of 0.81%; cardinalities up to 2<sup>64</sup><sup> • </sup><sup>[3](https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/)</sup> |
| Typical uses | Unique visitors to a web page, unique search queries per day, unique users who played a song or viewed a video<sup>[3](https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/)</sup> |
| Limits of the sketch | Supports union (merging) well, but set intersection and difference operations are not provided intrinsically because the resulting error would be poor<sup>[4](https://datasketches.apache.org/docs/HLL/HllSketches.html)</sup> |

## How the algorithm works

All efficient cardinality estimators rely on randomization supplied by a hash function that maps each element to a bit string treated as a sequence of coin flips. HyperLogLog uses a bit-pattern observable: the position ρ of the leftmost 1-bit in the hashed value. Seeing a pattern of ρ − 1 leading zeros is an indication that the cardinality is at least on the order of 2<sup>ρ</sup>, because such a run is rare among few distinct values.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup>

A single such observation is too noisy to be useful, so the algorithm applies **stochastic averaging**, a technique introduced in Flajolet and Martin's earlier Probabilistic Counting work. The first b bits of each hash value select one of \( m = 2^{b} \) registers, splitting the stream into m substreams; each register stores the maximum ρ value seen in its substream. This emulates m parallel experiments with a single hash function and costs a constant number of operations per element.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup>

The estimate is formed from the registers through a harmonic mean of the quantities \( 2^{-M[j]} \), combined with a correction constant \( \alpha_m \): the estimator is \( E = \alpha_m m^{2} Z \), where \( Z = \left( \sum_{j=1}^{m} 2^{-M[j]} \right)^{-1} \). The harmonic mean is the key difference from the earlier LOGLOG algorithm, which used what amounts to a geometric mean; it acts as a variance-reduction device that tames slow-decaying right tails of the distribution.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup> Each register needs at most \( \log_2 \log_2 N + O(1) \) bits when cardinalities up to N must be estimated, which is why the whole sketch fits in a few kilobytes.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup>

The original paper's analysis, using poissonization and Mellin transforms, shows the estimator is asymptotically almost unbiased and that its standard error approaches \( \beta_{\infty}/\sqrt{m} \) with \( \beta_{\infty} = \sqrt{3\log 2 - 1} \approx 1.03896 \), giving the commonly quoted \( 1.04/\sqrt{m} \).<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup>

## Mergeability and distributed use

Because each register holds a maximum, two sketches of the same configuration merge by taking the per-register maximum, and the result estimates the cardinality of the union. This makes HyperLogLog well suited to distributed systems: daily unique counts can be computed per shard and unioned into a site-wide total without rescanning raw data.<sup>[2](https://synapse.kakde.eu/synapse/system-design-from-first-principles/building-blocks/probabilistic-data-structures)</sup>

Production systems exploit this heavily. In Presto, the functions APPROX_SET, MERGE, and CARDINALITY let queries store HLL sketches in tables and roll them up later; Facebook's engineering team describes computing weekly or daily sketches and merging four weekly partitions to obtain a monthly distinct count without touching the original data set.<sup>[5](https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/)</sup> GoogleSQL in BigQuery exposes HyperLogLog++ functions, HLL_COUNT.INIT, MERGE, MERGE_PARTIAL, and EXTRACT, for approximate aggregation with partial re-aggregation and custom precision, which the plain APPROX_COUNT_DISTINCT function does not allow.<sup>[6](https://cloud.google.com/bigquery/docs/reference/standard-sql/hll_functions)</sup>

## Implementations

**Redis** implements HyperLogLog as a native data type, available since version 2.8.9. PFADD adds elements (O(1) per element), PFCOUNT returns the approximated cardinality (O(1) for a single key), and PFMERGE merges sketches. The implementation uses up to 12 KB of memory with a standard error of 0.81%, and can estimate cardinalities up to 2<sup>64</sup>. HLLs are encoded as Redis strings, so GET and SET can serialize and restore them.<sup>[3](https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/)</sup>

**Presto** offers two data types: HYPERLOGLOG, which starts in a sparse layout that is an exact representation for up to 256 unique elements and switches to a dense layout of about 8 KB beyond that, and P4HYPERLOGLOG, which is always dense. Observed standard error of APPROX_DISTINCT is about 2.3% for cardinalities above 256 and 0 below; APPROX_SET, which instantiates 4,096 buckets, reduces the error to 1.6% (\( 1.04/\sqrt{4096} \)). Dense layouts store bucket values as 4-bit deltas from a baseline, with overflow entries for larger deltas.<sup>[5](https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/)</sup>

**Apache DataSketches** provides a high-performance HLL implementation with precision parameter lgK from 4 to 21 and three register encodings, HLL_4, HLL_6, and HLL_8. Its HIP estimator makes it about 20% more accurate than a conventional HLL sketch of the same size, and below its transition point (about 384 uniques) sketches grow in 4-byte increments rather than occupying full size. The library's documentation notes that HLL sketches support union but are not recommended when set intersection or difference with reasonable accuracy is needed; the Theta sketch family serves that case.<sup>[4](https://datasketches.apache.org/docs/HLL/HllSketches.html)</sup>

## Comparison with related structures

HyperLogLog belongs to a family of probabilistic structures that trade bounded error for space independent of scale, each answering a different question: a [Bloom filter](https://www.edgepedia.org/bloom-filter) answers membership (is this element in the set?), HyperLogLog answers distinct count, and a Count-Min Sketch answers frequency (how often did this element appear?).<sup>[7](https://shirokoff.ca/blog/probabilistic-data-structures)</sup> A single analytics pipeline over a clickstream commonly runs all three side by side over the same events.<sup>[8](https://djangoproject.in/blog/system-design-data-structures-for-big-data/)</sup>

Within cardinality estimation itself, the 2007 paper's comparison table places HyperLogLog at \( 1.04/\sqrt{m} \) accuracy using m registers of at most 5 bits each, against 0.78 for Probabilistic Counting, 1.00 for MINCOUNT, 1.20 for Adaptive Sampling, and 1.30 for LOGLOG; it matches LOGLOG's accuracy while consuming only 64% of that algorithm's memory.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup> Later work continues to compress the sketch: HyperLogLogLog reduces the sketch from \( O(m \log \log n) \) bits toward \( m \log_2 \log_2 \log_2 m + O(m + \log \log n) \) bits,<sup>[9](https://arxiv.org/abs/2205.11327)</sup> and UltraLogLog, introduced by Otmar Ertl in 2023, shares HyperLogLog's practical properties (commutative, idempotent, mergeable, constant-time insert) while requiring 28% less space to encode the same distinct-count information.<sup>[10](https://arxiv.org/abs/2308.16862)</sup>

## Accuracy in practice

The error is a design parameter rather than an accident: it is set by the number of registers, with the formula \( 1.04/\sqrt{m} \) attached, so a practitioner chooses the precision in advance.<sup>[1](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)</sup><sup> • </sup><sup>[7](https://shirokoff.ca/blog/probabilistic-data-structures)</sup> The error distribution of unique-count sketches is not Gaussian; it is closer to a family of multinomial distributions, and for small sketches (K ≤ 4096) it becomes quite distorted, which is why the DataSketches library derives confidence bounds from empirical measurements and lookup tables rather than closed-form solutions.<sup>[4](https://datasketches.apache.org/docs/HLL/HllSketches.html)</sup> For skewed data that produces millions of mostly tiny sketches, the long tail of sketch sizes can dominate storage cost and reduce HLL's size advantage over Theta sketches to a factor of 2 to 4.<sup>[4](https://datasketches.apache.org/docs/HLL/HllSketches.html)</sup>

## References

1. [Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. DMTCS Proceedings AH, AofA 07, pp. 127–146.](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)
2. [Probabilistic Data Structures — Synapse, System Design from First Principles](https://synapse.kakde.eu/synapse/system-design-from-first-principles/building-blocks/probabilistic-data-structures)
3. [HyperLogLog, Redis Docs](https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/)
4. [HyperLogLog Sketches, Apache DataSketches documentation](https://datasketches.apache.org/docs/HLL/HllSketches.html)
5. [HyperLogLog in Presto: Faster cardinality estimation, Engineering at Meta (2018)](https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/)
6. [HyperLogLog++ functions, Google Cloud BigQuery documentation](https://cloud.google.com/bigquery/docs/reference/standard-sql/hll_functions)
7. [Probabilistic Data Structures at Scale: Bloom Filters, HyperLogLog, Count-Min Sketch](https://shirokoff.ca/blog/probabilistic-data-structures)
8. [Bloom Filters, HyperLogLog, Count-Min Sketch Explained, System Design for Big Data](https://djangoproject.in/blog/system-design-data-structures-for-big-data/)
9. [HyperLogLogLog: Cardinality Estimation With One Log More, arXiv:2205.11327](https://arxiv.org/abs/2205.11327)
10. [Otmar Ertl (2023). UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting. arXiv:2308.16862.](https://arxiv.org/abs/2308.16862)

---
*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Numerical, string, and geometric algorithms › Pseudorandomness and hashing algorithms*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license