Back to blog

An Interactive Guide to HyperLogLog

6 min read
hyperloglog
interactive_blog
algorithms

Learn to estimate large unique counts efficiently using HyperLogLog. Dive into the algorithm, its applications, and play with an interactive app

An Interactive Guide to HyperLogLog

The Problem

Imagine you’re running a large-scale online store. Thousands of users visit your website every second, and you want to know how many unique users visit each day. This sounds straightforward: just track each user by their IP address or login ID. But here’s the catch: keeping a set of every unique identifier requires huge amounts of memory, especially as the number of users grows into the billions.

How do you solve this problem without drowning in memory usage? This is where HyperLogLog, a probabilistic cardinality estimation algorithm, comes into play.

The Solution

HyperLogLog (HLL) is a clever algorithm that provides an approximate count of unique items (even billions of items) while using a tiny fraction of the memory (typically around ~1.5 kB) required by exact hash sets. It achieves this by trading off a tiny amount of precision (usually ≈1−2%\approx 1-2\% error) for massive space savings.

Play with HyperLogLog

Below is a HyperLogLog counting unique IP addresses. Next to it is an exact Set holding every IP, so you can see how close the estimate gets:

  • Add one IP by typing it (or clicking Random IP) and pressing Add to HLL. You'll see how its hash is split into a bucket and a run length, and whether that bucket changes. Add the same IP twice: the sketch doesn't change, which is exactly why it counts unique items.

  • Add thousands at once with the +1K to +100K buttons.

  • Change the bucket count with the slider (m = 2^p). This starts a fresh sketch.

  • Watch the error chart. Each point is the estimate's error at that count. The shaded band is the expected margin of error, ±1.04/√m.

Try it · HyperLogLog
Buckets (m = 2^p)128 · 640 bits
Add random IPs:
Actual count
0
HLL estimate
0
Actual error
+0.00%
Margin of error
±9.2%
1.04 / √m
Last added

Add an IP to see how it’s hashed and which bucket it updates.

Buckets
darker = longer run
Hover a bucket
Estimate error as the count grows · shaded band is ±1.04/√m
-18.4%-9.2%0.0%+9.2%+18.4%110100
The actual count comes from an exact Set kept alongside the sketch, so you can see how far off the estimate is.

Things to Notice

  • Margin of error decreases as buckets increase: A single bucket might get unlucky with an unusually long run of leading zeros early on, but spreading observations across hundreds or thousands of buckets smooths out the variance. (Similar to how risk pooling works in insurance).

  • The error never reaches absolute zero: Because HyperLogLog is a probabilistic data structure, small statistical variance is inherent.

  • Skimping on buckets increases error: Drop the slider to 16 buckets and add 100K IPs. The band widens to ±26% and the estimate wanders inside it.

  • Memory barely grows: 4,096 buckets take about 2.5 KB, whether they've seen a thousand IPs or a million. The exact Set alongside needs tens of megabytes.

How HyperLogLog Works

1. Hash Functions and Uniform Distribution

To estimate cardinality, we first hash incoming items. A good hash function is deterministic and distributes outputs uniformly across the entire bit space.

2. Leading Zeros and Cardinality

The core insight is based on coin flipping and probabilities:

  • When hashing data to a 64-bit integer, each bit is equally likely to be 0 or 1.

  • The probability of a hash starting with kk consecutive leading zeros is 2−k2^{-k}. For example:

    • Starting with 0... (k=1k=1): probability 1/21/2
    • Starting with 00... (k=2k=2): probability 1/41/4
    • Starting with 000... (k=3k=3): probability 1/81/8
  • If the maximum run of leading zeros observed is kk, we can roughly estimate that we have seen on the order of 2k2^k distinct elements.

3. Bucketing and Variance Reduction

A single estimate has high variance. To reduce error, HyperLogLog divides the hash space into m=2pm = 2^p independent buckets:

  • The first pp bits of the hash value determine the bucket index.

  • The remaining bits are used to count the number of leading zeros.

  • Each bucket maintains the maximum run length (M[j]M[j], the leading zeros plus one) observed so far.

Try it with any value below. The first p bits pick the bucket; the run of zeros after them is the coin-flip streak.

Try it · Splitting a hash
Index bits (p)16 buckets
00010010010101001111010001011100
first 4 bits → bucket 12 leading zeros, then a 1 → run length 3

192.168.0.1 goes to bucket 1 of 16. Its run length is 3, a 1-in-8 sight, so on its own this bucket guesses it has seen about 23 = 8 distinct items. The bucket keeps the longest run it has ever seen.

Type anything. The hash changes completely with every keystroke, but the split stays the same.

4. Combining Estimates with the Harmonic Mean

Instead of using a simple arithmetic mean (which is heavily skewed by outliers), HyperLogLog uses the harmonic mean of the estimates across all mm buckets:

E=αm⋅m2⋅(∑j=1m2−M[j])−1E = \alpha_m \cdot m^2 \cdot \left(\sum_{j=1}^{m} 2^{-M[j]} \right)^{-1}

Where:

  • m=2pm = 2^p: Total number of buckets.

  • M[j]M[j]: Maximum leading zeros observed in the jj-th bucket.

  • αm\alpha_m: A bias-correction constant derived empirically based on mm.

5. Bias Correction for Edge Cases

The raw estimate EE can exhibit bias at the extreme ends:

  1. Small Range Correction (Linear Counting): When E≤52mE \le \frac{5}{2}m and there are empty buckets (V>0V > 0), hash collisions are rare. HyperLogLog falls back to Linear Counting:

    Ecorrected=m⋅ln⁡(mV)E_{\text{corrected}} = m \cdot \ln\left(\frac{m}{V}\right)

  2. Large Range Correction: When nn approaches 2322^{32} (on 32-bit hashes), corrections are applied to account for 32-bit hash space saturation.

6. Error and Memory Efficiency

The theoretical standard error of HyperLogLog is approximately:

Error≈1.04m\text{Error} \approx \frac{1.04}{\sqrt{m}}

  • With m=2048m = 2048 buckets (each requiring only 5 or 6 bits), the standard error is roughly ≈2.3%\approx 2.3\%, using just 1.5 KB of memory!

  • Space complexity scales as O(mlog⁡(log⁡n))O(m \log(\log n)), making HyperLogLog remarkably memory-efficient.

Real-World Applications

  • Web Analytics: Platforms like Google Analytics and YouTube use HyperLogLog variants to estimate unique daily/monthly active users and video views.

  • Databases & Caches: Redis provides built-in PFADD / PFCOUNT commands taking ~12 KB for up to 2642^{64} items; TimescaleDB uses it for fast time-series rollups.

  • Big Data & Query Engines: Apache Druid and Presto / Trino use HyperLogLog for ultra-fast COUNT(DISTINCT ...) queries across petabytes of data.

Limitations

  • Approximation Only: HyperLogLog produces an estimate, not an exact count. If 100% exact precision is required (such as in billing or financial transactions), exact sets must be used instead.

  • Hash Function Dependency: Accuracy relies heavily on a uniform, high-quality hash function (e.g., MurmurHash3 or HighwayHash).

  • Cannot Retrieve Elements: HyperLogLog only counts unique items; it does not store or allow retrieval of the actual elements.

Further Reading