HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

TLDR

This extended abstract describes and analyses a near‑optimal probabilistic algorithm, HYPERLOGLOG, for estimating the cardinality of very large data sets. HYPERLOGLOG uses a single pass over the data with auxiliary memory of m units, achieving a relative error of about 1.04/√m, and it parallelizes optimally while adapting to sliding‑window models. The algorithm outperforms the previous best estimator LOGLOG, matching its accuracy while using only 64 % of the memory, and can estimate cardinalities beyond 10⁹ with 2 % accuracy using just 1.5 kB.

Abstract

This extended abstract describes and analyses a near-optimal probabilistic algorithm, HYPERLOGLOG, dedicated to estimating the number of \emphdistinct elements (the cardinality) of very large data ensembles. Using an auxiliary memory of m units (typically, "short bytes''), HYPERLOGLOG performs a single pass over the data and produces an estimate of the cardinality such that the relative accuracy (the standard error) is typically about $1.04/\sqrt{m}$. This improves on the best previously known cardinality estimator, LOGLOG, whose accuracy can be matched by consuming only 64% of the original memory. For instance, the new algorithm makes it possible to estimate cardinalities well beyond $10^9$ with a typical accuracy of 2% while using a memory of only 1.5 kilobytes. The algorithm parallelizes optimally and adapts to the sliding window model.