HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Discrete Mathematics & Theoretical Computer Science · 01.01.2007 · DMTCS Proceedings vol. AH,... (Proceedings)
DOI: 10.46298/dmtcs.3545 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 01.01.2007. Verfasst von Philippe Flajolet und 3 weiteren Autor:innen. Die Arbeit wurde bisher 367-mal zitiert (Crossref).
Abstract (Originalsprache)
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.
Zitieren
APA
Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AH,...(Proceedings). https://doi.org/10.46298/dmtcs.3545
Vancouver
Flajolet P, Fusy É, Gandouet O, Meunier F. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics & Theoretical Computer Science. 2007;DMTCS Proceedings vol. AH,...(Proceedings). doi:10.46298/dmtcs.3545
BibTeX
@article{Flajolet2007,
author = {Flajolet, Philippe and Fusy, Éric and Gandouet, Olivier and Meunier, Frédéric},
title = {HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2007},
volume = {DMTCS Proceedings vol. AH,...},
number = {Proceedings},
doi = {10.46298/dmtcs.3545}
}
EUVIMED