2026-07-20T11:15:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17014 2024-03-12T12:01:01Z ddc:004 open_access

Cardinality Estimation Using Gumbel Distribution Łukasiewicz, Aleksander Uznański, Przemysław Streaming algorithms Cardinality estimation Sketching Gumbel distribution Cardinality estimation is the task of approximating the number of distinct elements in a large dataset with possibly repeating elements. LogLog and HyperLogLog (c.f. Durand and Flajolet [ESA 2003], Flajolet et al. [Discrete Math Theor. 2007]) are small space sketching schemes for cardinality estimation, which have both strong theoretical guarantees of performance and are highly effective in practice. This makes them a highly popular solution with many implementations in big-data systems (e.g. Algebird, Apache DataSketches, BigQuery, Presto and Redis). However, despite having simple and elegant formulation, both the analysis of LogLog and HyperLogLog are extremely involved - spanning over tens of pages of analytic combinatorics and complex function analysis. We propose a modification to both LogLog and HyperLogLog that replaces discrete geometric distribution with the continuous Gumbel distribution. This leads to a very short, simple and elementary analysis of estimation guarantees, and smoother behavior of the estimator. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksander Łukasiewicz and Przemysław Uznański 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.76 urn:nbn:de:0030-drops-170140 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.76 eng https://creativecommons.org/licenses/by/4.0/legalcode