HyperLogLog: Estimating Billions of Unique Elements in Kilobytes of Memory

In real-time analytics, calculating the exact number of unique elements (the cardinality or `COUNT(DISTINCT)`) across massive streams—such as daily active users (DAUs), distinct IP addresses, or unique search queries—traditionally requires storing every seen key in a Hash Set or Balanced Search Tree.

For a dataset containing 100 million 64-bit identifiers, an exact hash set requires gigabytes of RAM. Invented by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier in 2007, **HyperLogLog (HLL)** is a probabilistic data structure that estimates cardinality with a typical standard error of ~1.04 / sqrt(m) while consuming a fixed memory footprint of roughly **12 KB**, regardless of whether the dataset contains 10,000 or 10 billion distinct items.

The Core Probability Intuition: Counting Leading Zeros

Consider tossing a fair coin repeatedly until getting 'Heads' (1). The probability of seeing a sequence starting with $k$ consecutive 'Tails' (0s) followed by a Head is $(1/2)^{k+1}$:

Seeing '1...' (0 leading zeros): Happens ~50% of the time (expected trials: 2).
Seeing '01...' (1 leading zero): Happens ~25% of the time (expected trials: 4).
Seeing '00001...' (4 leading zeros): Happens ~3.125% of the time (expected trials: 32).
Seeing a maximum run of $R$ leading zeros suggests we have likely observed approximately $2^{R+1}$ distinct random events.

By hashing input items uniformly across a 64-bit binary space, the pattern of leading zeros in the hash outputs directly mirrors this coin-tossing probability model.

Register Bucketing and Harmonic Mean Averaging

Relying on a single maximum run of leading zeros yields high statistical variance. HyperLogLog eliminates variance through two structural techniques:

1. Stochastic Averaging across m Registers

HLL divides its state into $m = 2^p$ independent registers (buckets). For standard implementations (e.g., $p = 14$), there are $m = 16,384$ registers. When an item is added:

Compute a 64-bit uniform hash of the item.
Use the first $p$ bits of the hash to select the target register index $j$ ($0 \le j < m$).
Count the number of leading zeros $\rho$ in the remaining $(64 - p)$ bits (plus 1).
Update the register value: $M[j] = \max(M[j], \rho)$.

2. Harmonic Mean Estimation Formula

Instead of using the arithmetic mean (which is easily corrupted by single outlier runs), HLL computes the **Harmonic Mean** of $2^{-M[j]}$ across all registers to strongly discount extreme values:

E = alpha_m * m^2 * ( sum_{j=1}^{m} 2^(-M[j]) )^(-1)

Where $\alpha_m$ is a predetermined bias-correction constant (for $m = 16384$, $\alpha_m \approx 0.7213 / (1 + 1.079 / m)$).

Range Corrections and Distributed Merging

1. Small Range Correction (Linear Counting)

When total cardinality is small relative to $m$ and many registers remain 0, raw HLL estimates suffer non-linear bias. In this range ($E < 2.5 \cdot m$), HLL switches to Linear Counting based on the number of empty registers $V$: $E^* = m \cdot \ln(m / V)$.

2. Large Range Correction (64-Bit Space)

When using 32-bit hashes, hash collisions occur near $2^{32}$, requiring large-range asymptotic corrections. Modern 64-bit implementations (such as HyperLogLog++) eliminate this boundary, allowing seamless counting up to $2^{64}$ with zero overflow risk.

3. Lossless Distributed Merge (O(m) Time)

Two or more HyperLogLog instances configured with the same register size $m$ can be merged without accessing original data points by taking the element-wise maximum across registers: $M_{merged}[j] = \max(M_A[j], M_B[j])$. This allows parallel, decentralized metric aggregation across distributed worker nodes.

C++ Implementation Blueprint (Standard HLL Engine)

#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdint>

class HyperLogLog {
private:
    static constexpr int P = 14;              // 14 bits -> 16384 registers
    static constexpr int M = 1 << P;         // 16384
    static constexpr double ALPHA = 0.7213 / (1.0 + 1.079 / M);
    std::vector<uint8_t> registers;

    uint64_t hash64(const std::string& key) const {
        // 64-bit MurmurHash3 or std::hash wrapper
        return std::hash<std::string>{}(key);
    }

    int countLeadingZeros(uint64_t val, int max_bits) const {
        if (val == 0) return max_bits;
        int zeros = 0;
        while ((val & (1ULL << (max_bits - 1 - zeros))) == 0 && zeros < max_bits) {
            zeros++;
        }
        return zeros;
    }

public:
    HyperLogLog() : registers(M, 0) {}

    void add(const std::string& item) {
        uint64_t h = hash64(item);
        uint32_t j = h >> (64 - P); // Top P bits for register index
        uint64_t w = h & ((1ULL << (64 - P)) - 1); // Remaining 64-P bits
        int leading_zeros = countLeadingZeros(w, 64 - P) + 1;
        registers[j] = std::max(registers[j], static_cast<uint8_t>(leading_zeros));
    }

    double count() const {
        double sum = 0.0;
        int empty_registers = 0;
        for (int j = 0; j < M; ++j) {
            sum += std::pow(2.0, -registers[j]);
            if (registers[j] == 0) empty_registers++;
        }

        double estimate = ALPHA * M * M / sum;

        // Linear counting for small range correction
        if (estimate <= 2.5 * M && empty_registers > 0) {
            estimate = M * std::log(static_cast<double>(M) / empty_registers);
        }
        return estimate;
    }

    void merge(const HyperLogLog& other) {
        for (int j = 0; j < M; ++j) {
            registers[j] = std::max(registers[j], other.registers[j]);
        }
    }
};

Real-World Distributed and Big Data Systems

Redis In-Memory Analytics: Provides native O(1) commands (`PFADD`, `PFCOUNT`, `PFMERGE`) using 12 KB dense register allocations per key.
Cloud Data Warehouses (Google BigQuery, Snowflake, AWS Redshift): Accelerating `APPROX_COUNT_DISTINCT()` analytical SQL queries across petabyte tables in seconds.
High-Throughput OLAP Engines (ClickHouse, Apache Pinot): Storing intermediate HLL sketches in aggregate projection tables for sub-second unique visitor reporting.
Network Traffic & DDoS Monitoring: Tracking unique destination IPs and flow endpoints per second across edge router interfaces without unbounded memory growth.