How HyperLogLog Estimates Cardinality with Hashes

HyperLogLog (HLL) is an algorithm designed to estimate the cardinality—the number of unique elements—of massive datasets using a fraction of the memory required by traditional counting methods. This article explains the mechanics of HyperLogLog, focusing on how it transforms input data into uniform binary hash values, tracks leading zeros as a measure of probability, distributes observations across multiple registers to reduce variance, and combines these measurements via a harmonic mean to deliver accurate estimates for billions of items using only a few kilobytes of memory.

The Foundation: Binary Hashes and Probability

To count distinct items without storing every raw value, HyperLogLog first passes each input item through a uniform, collision-resistant hash function. This function maps any data type (such as user IDs, URLs, or IP addresses) to a uniformly distributed binary number, typically 64 bits in length.

In a uniformly distributed binary sequence, each bit has an independent 50% probability of being either a 0 or a 1, mirroring a series of fair coin flips where 0 represents heads and 1 represents tails.

When observing the sequence of bits from left to right: * The probability of a hash starting with one leading zero (0...) is \(1/2\) (\(2^{-1}\)). * The probability of two leading zeros (00...) is \(1/4\) (\(2^{-2}\)). * The probability of \(k\) leading zeros (00...01) is \(1/2^k\) (\(2^{-k}\)).

Because observing a sequence with \(k\) consecutive leading zeros is an event that occurs once every \(2^k\) random trials, observing a maximum run of \(k\) leading zeros suggests that roughly \(2^k\) distinct items have been processed.

Mitigating Variance: Register Bucketing

Relying on a single hash observation produces high variance; an unlikely sequence with many leading zeros could appear on the very first item, skewing the estimate entirely. HyperLogLog resolves this through a technique called stochastic averaging.

Instead of evaluating all hashes globally, HLL splits the hash into two distinct segments: 1. The Register Index: The first \(p\) bits of the hash select one of \(m = 2^p\) sub-streams, known as registers or buckets. 2. The Run Length: The remaining \((64 - p)\) bits are evaluated to count the number of leading zeros plus one (the position of the first 1 bit).

Each register only stores the maximum number of leading zeros it has observed from the items routed to it. By dividing the dataset across thousands of registers (for example, \(p = 14\) yields \(16,384\) registers), the algorithm distributes the workload and dampens the impact of individual statistical anomalies.

Aggregation via the Harmonic Mean

Once data has been streamed through the registers, the algorithm aggregates the maximum values recorded in each register to compute the final cardinality estimate.

Rather than using an arithmetic mean—which remains vulnerable to large outlier values—HyperLogLog uses the harmonic mean of the estimates across all registers:

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

The harmonic mean heavily penalizes extreme outliers, producing a stable, robust measurement across the entire collection of buckets.

Memory Efficiency at Scale

Because each register only needs to store the maximum position of a leading zero rather than the raw data itself, each register requires very little memory. In a 64-bit hash space, the maximum possible run of zeros is 64, which fits into a 6-bit integer (\(2^6 = 64\)).

With \(16,384\) registers of 6 bits each: \[\text{Total Memory} = 16,384 \times 6 \text{ bits} = 98,304 \text{ bits} = 12 \text{ KB}\]

With only 12 KB of memory, HyperLogLog can estimate the cardinality of datasets containing billions of distinct elements with a typical standard error rate of roughly \(1.04 / \sqrt{m}\) (approximately 0.81% for 16,384 registers). For smaller datasets where registers might remain empty, HLL incorporates bias corrections like Linear Counting to maintain accuracy across the entire range of dataset sizes.