HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm - Archive ouverte HAL Access content directly
Conference Papers Discrete Mathematics and Theoretical Computer Science Year : 2007

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

(1) , (1) , (2) , (1)
1
2

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.
Fichier principal
Vignette du fichier
dmAH0110.pdf (515.14 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-00406166 , version 1 (21-07-2009)
hal-00406166 , version 2 (17-08-2015)

Identifiers

Cite

Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. AofA: Analysis of Algorithms, Jun 2007, Juan les Pins, France. pp.137-156, ⟨10.46298/dmtcs.3545⟩. ⟨hal-00406166v2⟩
31155 View
6574 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More