The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index.
HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm
Abstract
Cardinality estimation has a wide range of applications and is of particular importance in database systems. Various algorithms have been proposed in the past, and the HyperLogLog algorithm is one of them. In this paper, we present a series of improvements to this algorithm that reduce its memory requirements and significantly increase its accuracy for an important range of cardinalities. We have implemented our proposed algorithm for a system at Google and evaluated it empirically, comparing it to the original HyperLogLog algorithm. Like HyperLogLog, our improved algorithm parallelizes perfectly and computes the cardinality estimate in a single pass.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Probabilistic counting algorithms for data base applications
Flajolet, P., & Nigel Martin, G. (1985) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(85)90041-8 · Cited by 1,269
Scandinavian Journal of Statistics
(2010) · Scandinavian Journal of Statistics · doi:10.1111/(issn)1467-9469 · Cited by 976
Dremel: interactive analysis of web-scale datasets
Melnik, S., Gubarev, A., Long, J. J., Romer, G., Shivakumar, S., Tolton, M., & Vassilakis, T. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920886 · Cited by 711
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.3545 · Cited by 695
Interpreting the Data: Parallel Analysis with Sawzall
Pike, R., Dorward, S., Griesemer, R., & Quinlan, S. (2005) · Scientific Programming · doi:10.1155/2005/962135 · Cited by 611
Counting Distinct Elements in a Data Stream
Bar-Yossef, Z., Jayram, T. S., Kumar, R., Sivakumar, D., & Trevisan, L. (2002) · Lecture Notes in Computer Science · doi:10.1007/3-540-45726-7_1 · Cited by 460
Tight lower bounds for the distinct elements problem
Indyk, P., & Woodruff, D. P. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238202 · Cited by 153
Order statistics and estimating cardinalities of massive data sets
Giroire, F. (2008) · Discrete Applied Mathematics · doi:10.1016/j.dam.2008.06.020 · Cited by 95
Processing a trillion cells per mouse click
Hall, A., Bachmann, O., Büssow, R., Gănceanu, S., & Nunkesser, M. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2350229.2350259 · Cited by 89
Self-citation
Cited by
KrakenUniq: confident and fast metagenomics classification using unique k-mer counts
Breitwieser, F. P., Baker, D. N., & Salzberg, S. L. (2018) · Genome Biology · doi:10.1186/s13059-018-1568-0 · Cited by 474
Big data in the policy cycle: Policy decision making in the digital era
Höchtl, J., Parycek, P., & Schöllhammer, R. (2016) · Journal of Organizational Computing and Electronic Commerce · doi:10.1080/10919392.2015.1125187 · Cited by 331
“The HyperLogLog-Algorithm is one fascinating example of a Big Data-inspired approach to the seemingly easy problem of counting distinct things, as it generates very good results to the cardinality estimation problem yet only requires minimal time and space (Heule, Nunkesser, and Hall 2013).”
BackgroundKHyperLogLog: Estimating Reidentifiability and Joinability of Large Data at Scale
Chia, P. H., Desfontaines, D., Perera, I. M., Simmons-Marengo, D., Li, C., Day, W.-Y., Wang, Q., & Guevara, M. (2019) · 2019 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2019.00046 · Cited by 15
Metadata
- Authors
- Heule, S., Nunkesser, M., & Hall, A.
- Venue
- Proceedings of the 16th International Conference on Extending Database Technology
- Publisher
- ACM
- Published
- 2013-03-18
- Pages
- 683-692
- OpenAlex
- W1982092405
- Cited by
- 302
- References
- 9
- FWCI
- 10.26
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. https://app.cochat.ai/papers/10.1145/2452376.2452456
- The paper
- Heule, S., Nunkesser, M., & Hall, A. (2013). HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm. Proceedings of the 16th International Conference on Extending Database Technology. https://doi.org/10.1145/2452376.2452456
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
