hyperloglog · shipping · also HLL

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

  1. Flajolet, Fusy, Gandouet and Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. AofA 2007, sections 1 and 4. (accessed 2026-10-29)
  2. Heule, Nunkesser and Hall. HyperLogLog in Practice. EDBT 2013, sections 4-6 and Figure 1. (accessed 2026-10-29)
  3. Ertl. New Cardinality Estimation Methods for HyperLogLog Sketches. arXiv:1706.07290v1, sections 2 and 6. (accessed 2026-10-29)
  4. Hesela: exact register-state example with distinct assigned hashes, executable derivation and tests. (accessed 2026-10-29)
  5. Redis command reference: PFADD return information and the no-element creation exception. (accessed 2026-10-29)
  6. Redis PFMERGE reference: an existing destination is an input to the union. (accessed 2026-11-20)
  7. Redis 7.2.4, pinned hyperloglog.c: pfaddCommand, pfcountCommand and pfmergeCommand. (accessed 2026-11-20)
  8. Hesela: native Redis HLL window controls, sparse/dense results, guarded-rebuild example and exact replay package. (accessed 2026-11-20)
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]

JSON: /data/terms/hyperloglog.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. HyperLogLog. Hesela. 2026-11-20. https://hesela.dev/terms/hyperloglog/