HyperLogLog
HyperLogLog is a compact probabilistic sketch that estimates the number of distinct values from maxima of hash-derived register ranks.
A hash prefix selects one of m registers; remaining bits determine a rank. Repeats leave maxima unchanged. Under independent uniform hash bits, the classic asymptotic relative standard error is about 1.04/sqrt(m): 16384 registers give 0.81%, not a worst-case bound. [1]
Direct register-wise maximum constructs the union sketch when both use the same precision, rank range, hash function and seed, input encoding, index/rank conventions and register order. The count remains estimated. HLL++ adds 64-bit hashes, bias correction and sparse storage with different small-cardinality behavior. [2] [3]
A register-only sketch cannot generally undo an insertion. Distinct assigned hashes 0001 and 0010 select one register with ranks 2 and 1. Sets {a} and {a,b} both store [2,0,0,0], but deleting a requires [0,0,0,0] or [1,0,0,0]. No full-hash collision is involved. [4]
No-op insertion does not prove membership: adding b to {a} leaves the registers unchanged although b was absent. This cannot justify discarding a stored chunk. [4] PFADD returning 0 reports no changed registers, not confirmed duplicate input. [5]
Register-wise minimum does not generally construct an intersection. Joint estimation can estimate overlap size, not recover its items. For A minus B, subtract B's count from the union count; subtracting B's count from A's requires that B is a subset of A. Estimated differences can have large relative errors when the result is small. [3]
Relations
- related
- Bloom filter, Data deduplication
Limitations
- Redis PFMERGE includes an existing destination. In a pinned Redis 7.2.4 replay, reusing a rollup yields 120 for a requested 20-identity active union; a fresh destination yields 20. Expiring a source does not retract its contribution from the rollup. [6, 8]
- A missing still-required source is accepted as empty: the same constructed 20-identity window then reports 10. Keep a complete manifest of sealed buckets and distinguish missing from intentionally empty input. These are population-selection failures, not measured estimator error rates. [7, 8]
- The native replay adds a distinct 184th identity while PFADD returns 0, the estimate stays 183 and cached bytes remain identical. The example replacement checks source presence and builds into a fresh key on one server; it does not establish ingestion completeness, cross-server consistency or durability, and makes the destination persistent. [8]
Citations
- Flajolet, Fusy, Gandouet and Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. AofA 2007, sections 1 and 4.
- Heule, Nunkesser and Hall. HyperLogLog in Practice. EDBT 2013, sections 4-6 and Figure 1.
- Ertl. New Cardinality Estimation Methods for HyperLogLog Sketches. arXiv:1706.07290v1, sections 2 and 6.
- Hesela: exact register-state example with distinct assigned hashes, executable derivation and tests.
- Redis command reference: PFADD return information and the no-element creation exception.
- Redis PFMERGE reference: an existing destination is an input to the union.
- Redis 7.2.4, pinned hyperloglog.c: pfaddCommand, pfcountCommand and pfmergeCommand.
- Hesela: native Redis HLL window controls, sparse/dense results, guarded-rebuild example and exact replay package.
Sources & caveats
- The three papers were read beyond their abstracts on 2026-10-29; the standard-error statement is asymptotic and assumes the stated hash-randomness model.
- The four-bit example is a constructed information-loss witness, not an observed error rate or a reproduction of a paper's experiments.
- The deletion result concerns only the register state. Sliding-window or deletion-aware designs can retain additional information.
- HLL estimates a count, not variable-sized unique payload bytes, physical capacity savings or safe garbage-collection candidates.
- The PFADD contract was read in the official command reference; the four-bit example does not execute Redis or reproduce its hash mapping.
- The 2026-11-20 native controls use Redis 7.2.4 commit d2c8a4b91e8c0e6aefd1f5bc0bf582cddbe046b7, isolated Unix sockets and deterministic byte identities. They are not field measurements, an accuracy benchmark, a new Redis defect or a recommendation to deploy that historical version. [8]