@inproceedings{a3ef3186960c45c9a6759b25d582e20c,
title = "Bit-Array-Based Alternatives to HyperLogLog",
abstract = "We present a family of algorithms for the problem of estimating the number of distinct items in an input stream that are simple to implement and are appropriate for practical applications. Our algorithms are a logical extension of the series of algorithms developed by Flajolet and his coauthors starting in 1983 that culminated in the widely used HyperLogLog algorithm. These algorithms divide the input stream into M substreams and lead to a time-accuracy tradeoff where a constant number of bits per substream are saved to achieve a relative accuracy proportional to 1/√M. Our algorithms use just one or two bits per substream. Their effectiveness is demonstrated by a proof of approximate normality, with explicit expressions for standard errors that inform parameter settings and allow proper quantitative comparisons with other methods. Hypotheses about performance are validated through experiments using a realistic input stream, with the conclusion that our algorithms are more accurate than HyperLogLog when using the same amount of memory, and they use two-thirds as much memory as HyperLogLog to achieve a given accuracy.",
keywords = "Cardinality estimation, Hyperloglog, sketching",
author = "Svante Janson and J{\'e}r{\'e}mie Lumbroso and Robert Sedgewick",
note = "Publisher Copyright: {\textcopyright} Svante Janson, J{\'e}r{\'e}mie Lumbroso, and Robert Sedgewick.; 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, A of A 2024 ; Conference date: 17-06-2024 Through 21-06-2024",
year = "2024",
month = jul,
doi = "10.4230/LIPIcs.AofA.2024.5",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Cecile Mailler and Sebastian Wild",
booktitle = "35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, A of A 2024",
address = "Germany",
}