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 $\approx 1-2\%$ error) for massive space savings.

Play with HyperLogLog

I have created an interactive app that lets you experiment with HyperLogLog in real-time. Here is how the app works:

• Input IP Address:

  • Click "Random IP" to generate an IP address automatically.

  • Add the entered IP to the HyperLogLog by clicking "Add to HLL".

• Adjust Bucket Count:

  • Use the slider to adjust the number of buckets ($m = 2^p$).

  • Modifying this resets the HyperLogLog and clears previous data.

• Add Multiple Random IPs:

  • Use the preset buttons to insert 1K, 5K, 10K, 50K, or 100K random IP addresses into the sketch.

• View Metrics:

  • Compare Actual Count, Estimated Count, Difference, Margin of Error, and Actual Error in the metrics cards.

• Inspect Buckets:

  • Scroll through individual buckets to observe how HyperLogLog distributes hashed items and tracks maximum leading zero runs.

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: Notice what happens to the variance and error margin if you reduce the bucket count to a very small number.

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 $k$ consecutive leading zeros is $2^{-k}$. For example:

  • Starting with 0... ($k=1$): probability $1/2$
  • Starting with 00... ($k=2$): probability $1/4$
  • Starting with 000... ($k=3$): probability $1/8$

• If the maximum run of leading zeros observed is $k$, we can roughly estimate that we have seen on the order of $2^k$ distinct elements.

3. Bucketing and Variance Reduction

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

• The first $p$ 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 leading zero count ($M[j]$) observed so far.

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 $m$ buckets:

$E = \alpha_m \cdot m^2 \cdot \left(\sum_{j=1}^{m} 2^{-M[j]} \right)^{-1}$

Where:

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

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

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

5. Bias Correction for Edge Cases

The raw estimate $E$ can exhibit bias at the extreme ends:

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

   $E_{\text{corrected}} = m \cdot \ln\left(\frac{m}{V}\right)$

2. Large Range Correction: When $n$ approaches $2^{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:

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

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

• Space complexity scales as $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 $2^{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

• HyperLogLog: The Analysis of a Near-Optimal Cardinality Estimation Algorithm (Flajolet et al.)

• Engineering at Meta: HyperLogLog in Presto

• Redis Documentation: HyperLogLog Data Type