HyperLogLog

Deep dive

How it works

In: a well-mixed 64-bit hash of each item · Out: an estimate of the number of distinct items, standard error 1.04/√m · State: m = 2^p registers (6 bits each, 12 KB at p = 14) · Cost: add O(1), estimate and merge O(m)

h = hash64(x) = [ p bits: register idx | 64-p bits: w ]
rank = leading_zeros(w) + 1           register[idx] = max(register[idx], rank)
E = alpha_m * m^2 / sum_j 2^(-register[j])

1. idx = h >> (64-p); w = h << p; rank = clz(w) + 1, capped at 64-p+1.
2. Keep the max rank per register.
3. Raw estimate E = α_m · m² / Σ 2^-M[j] with α_m = 0.7213/(1 + 1.079/m) (m ≥ 128).
4. If E ≤ 2.5·m and some registers are zero (V of them), use linear counting m·ln(m/V).
5. With 64-bit hashes no large-range correction is needed (it existed for 32-bit hashes near 2^32).
6. HLL++ adds an empirical bias correction for E < 5m and a sparse encoding (list of (idx, rank) with higher precision) while the set is small.

Code

pub struct Hll { p: u32, regs: Vec<u8> }

impl Hll {
    pub fn new(p: u32) -> Self {
        assert!((4..=18).contains(&p));
        Hll { p, regs: vec![0; 1 << p] }
    }

    /// `h` must be a well-mixed 64-bit hash (e.g. XXH3, wyhash, or fmix64 of an integer).
    pub fn add_hash(&mut self, h: u64) {
        let idx = (h >> (64 - self.p)) as usize;
        let w = (h << self.p) | (1u64 << (self.p - 1)); // sentinel bit caps rank at 64 - p + 1
        let rank = w.leading_zeros() as u8 + 1;
        let r = &mut self.regs[idx];
        if rank > *r { *r = rank; }
    }

    pub fn merge(&mut self, other: &Hll) {
        assert_eq!(self.p, other.p, "merge needs equal precision (or downsample the larger)");
        for (a, &b) in self.regs.iter_mut().zip(&other.regs) { *a = (*a).max(b); }
    }

    pub fn count(&self) -> f64 {
        let m = self.regs.len() as f64;
        let alpha = match self.regs.len() {
            16 => 0.673,
            32 => 0.697,
            64 => 0.709,
            _ => 0.7213 / (1.0 + 1.079 / m),
        };
        let mut sum = 0.0;
        let mut zeros = 0usize;
        for &r in &self.regs {
            sum += f64::powi(2.0, -(r as i32)); // table of 2^-r in hot code
            zeros += (r == 0) as usize;
        }
        let e = alpha * m * m / sum;
        if e <= 2.5 * m && zeros > 0 {
            m * (m / zeros as f64).ln() // linear counting for small cardinalities
        } else {
            e
        }
    }
}

// let mut h = Hll::new(14); for id in ids { h.add_hash(fmix64(id)); } h.count()

Complexity and constants

• Add: one hash + one load/compare/store, order of 2-10 ns when the sketch is in cache; the hash usually dominates.
• Errors are roughly normal: 95 % of estimates within ±2σ (±1.6 % at p = 14).
• Raw estimator has a bias bump around 2.5m-5m; HLL++'s bias tables or Ertl's improved estimator fix it.
• Merge: m byte-max operations, trivially vectorized.

Efficiency

• Cost: an add is one hash plus one load, compare and store: order of 2-10 ns with the sketch in cache, and the hash usually dominates. Memory is fixed: 12 KB for 0.81 % error at p = 14 (Redis dense encoding), however many items. Merge is m byte-max operations. Bound: hashing compute for adds, memory bandwidth for merges.
• Levers:
  • sparse encoding for small sets — near-exact counts and far less than 12 KB (HLL++, Heule et al. 2013) — many sketches with few items each
  • improved estimator — removes the bias bump near 2.5m-5m without empirical tables (Ertl 2017) — all ranges
  • SIMD register-wise max — merge of 16384 registers in a few µs (order of) — union over shards or time buckets
  • fixed p and hash across the system — merges need no downsampling — multi-producer pipelines
  • CPC sketch — about 40 % smaller than HLL for the same error (Apache DataSketches) — stored or shipped sketches
• Naive → standard → state of the art:
  • hash set of all items · about 8+ bytes per distinct item, exact
  • HyperLogLog, p = 14 · 12 KB, 0.81 % error, mergeable
  • HLL++ with sparse mode, or Ertl estimator / CPC · near-exact when small, 40 % smaller with CPC

Implementation notes

• Store registers as u8 for speed (as above) or packed 6 bits for memory; Redis packs 6 bits and uses a sparse run-length encoding until about 3 KB.
• Keep a precomputed 2^-r table and the zero count incrementally if count() is hot.
• Downsampling p → p' < p: each old register maps to new index i >> (p-p'); its new rank is the position of the first 1 in the dropped p-p' index bits, or r + (p-p') if they are all zero (empty registers stay 0); take the max per new register. Simpler: fix one p per system.
• The hash must be the same across all producers whose sketches you merge, including seed.
• Sparse mode (HLL++): store (idx at p' = 25, rank) pairs sorted and delta/varint-encoded; convert to dense when it exceeds the dense size. Gives near-exact counts for small sets.
• Serialize with a version, p, hash id, and encoding type.

Pitfalls

• Feeding unhashed or weakly hashed values (sequential IDs): ranks stop being geometric and estimates are wildly off.
• Using 32-bit hashes at > 10^8 distinct items: collisions bias the count; use 64-bit.
• Computing intersections via |A| + |B| - |A∪B| when the overlap is small: error of the union swamps it.
• Merging sketches with different p or different hash functions.
• Reporting the estimate as an integer without its error bar.

Variants and alternatives

In production

• Databases and analytics engines: Redis (PFADD/PFCOUNT/PFMERGE, p = 14, 12 KB dense, sparse encoding), Google BigQuery (HLL_COUNT.*, HLL++), Trino/Presto approx_distinct, Apache Druid, ClickHouse uniqHLL12/uniqCombined.
• Search: Elasticsearch cardinality aggregation (HLL++).
• Libraries for web and network analytics (unique users, source IPs): Apache DataSketches.

Implementations

Sources

• Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier, HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, AofA 2007. paper · pdf
• Stefan Heule, Marc Nunkesser, Alexander Hall, HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm, EDBT 2013. paper
• Otmar Ertl, New cardinality estimation algorithms for HyperLogLog sketches, arXiv 1702.01284, 2017. paper
• Kyu-Young Whang, Brad T. Vander-Zanden, Howard M. Taylor, A Linear-Time Probabilistic Counting Algorithm for Database Applications, ACM TODS 1990. paper
• Redis documentation, HyperLogLog. docs
• Apache DataSketches Rust library. code