Estimating Cardinality with HyperLogLog

What is Cardinality?

Cardinality refers to the count of distinct elements in a dataset. For example, given the list [“Alice”, “Bob”, “Jack”, “Alice”], the cardinality is 3, as there are only three unique names.

A straightforward way to compute cardinality is by using a hash set — each unique element is stored once, and the total count is the number of keys. While hash lookups are efficient (~O(log n)), this approach requires linear memory relative to the number of unique elements. For large-scale datasets (e.g., tracking Facebook’s daily visitors), storing every unique entry becomes impractical due to memory constraints.

This raises an important question: Do we always need an exact count, or is an approximation sufficient? In many real-world scenarios (e.g., website analytics), an approximate count is acceptable and far more cost-effective.

A Probabilistic Approach to Cardinality Estimation

To estimate cardinality efficiently, we can leverage probability theory. Consider a simple analogy: flipping a fair coin. The probability of getting Heads (H) or Tails (T) is ½.

• The chance of getting three consecutive Heads (HHH) is lower than getting two Heads (HH), which in turn is lower than a single Head (H).
• If someone reports observing HHH, we can infer they likely performed many trials to achieve this outcome.

This intuition forms the basis of probabilistic cardinality estimation.

From Random Numbers to Hashing

Suppose we hash each element in a dataset, producing uniformly distributed values between [0, 1]. For example:

Input: [120, 100, 90, 100, 90] Hashed: [0.2, 0.4, 0.3, 0.4, 0.3]

A naive estimator would be:

Estimate=1/min⁡(hashed values)=1/0.2=5

However, this method has two major flaws:

1. High Variance — Due to the infinite range of possible hash values.
2. Overestimation Risk — A single extremely small hash value skews the result.

Improving Stability: Counting Leading Zeroes

To reduce variance, we can convert hash values to binary and count the number of leading zeroes. The probability of observing k consecutive zeroes is:

P(k leading zeros)=1/(2^k)

Thus, the estimator becomes:

Estimate=2(maximum leading zeros observed)

But this still has issues:

• Estimates are constrained to powers of two (2, 4, 8, 16, …).
• Variability remains high because a single extreme value (e.g., many leading zeros) can distort the estimate.

LogLog: Reducing Variance with Multiple Buckets

The LogLog algorithm improves accuracy by using multiple hash functions (or splitting one hash into buckets and that will reduce using intensive computational for multiple hash value).

How it works:

1. Divide the hash output into two parts:

2. The first few bits determine the bucket.

3. The remaining bits determine the leading zero count (R).

4. Track the maximum R per bucket.

5. Combine results using:

Estimate=constant×m×2^√m∑Ri​

• m = number of buckets
• Ri​ = max leading zeros in bucket i

Performance:

• Error rate: ~1.3/√m With 2048 buckets (11 bits each), memory usage is just 1.2KB, supporting cardinalities up to 2²⁷ with ~2.8% error.

HyperLogLog: Further Refinement

HyperLogLog (HLL) enhances LogLog by:

• In HyperLogLog (HLL), the harmonic mean is used to combine estimates from multiple buckets (instead of the arithmetic mean in LogLog). This helps because:
• Some buckets may have unusually high cardinality estimates due to hash collisions. The harmonic mean dampens the effect of these outliers, leading to a more stable and accurate final estimate.
• Reducing the error rate to ~1.05/√m without additional memory.

Implementation and Results

I’ve developed a high-performance, memory-efficient HyperLogLog algorithm in TypeScript, now available as an **npm package **and i can share the result of implementing this using 2¹⁴ buckets.

If you want to take a review on implementation: https://www.npmjs.com/package/@hazemaltakriti/hyperloglog

Redis and HyperLogLog

Redis includes a built-in implementation of HyperLogLog using the PFADD, PFCOUNT, and PFMERGE commands, with a default precision of 14, effectively distributing the data into 2¹⁴ buckets.

PFADD unique_visitors "user1" "user2" "user3" "user1"
PFCOUNT unique_visitors # Returns 3

Conclusion

HyperLogLog provides an efficient, memory-friendly method for approximate cardinality estimation, making it ideal for large-scale systems like web analytics, databases, and distributed computing. By leveraging probabilistic techniques, it achieves high accuracy with minimal storage — proving that sometimes, approximation is better than perfection.

References:

• https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
• https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/
• https://antirez.com/news/75