This extended abstract presents a novel probabilistic algorithm called HYPERLOGLOG for efficiently estimating the cardinality of massive datasets. It improves upon existing algorithms like LOGLOG by achieving higher accuracy while using significantly less memory. The algorithm is based on the harmonic mean of certain observable quantities, which improves the quality of estimations by effectively reducing variance. The paper also provides a rigorous mathematical analysis of the algorithm’s performance, employing techniques such as poissonization and Mellin transforms, to determine its asymptotic behavior in terms of bias and standard error. Finally, the paper discusses practical considerations for implementing the algorithm, including the use of hash functions, correction for small cardinality issues, and potential optimality compared to other existing algorithms.

Link to the Paper: https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf