New cardinality estimation algorithms for HyperLogLog sketches

Understand

This paper presents new methods to estimate the cardinalities of data sets recorded by HyperLogLog sketches.

• A theoretically motivated extension to the original estimator is presented that eliminates the bias for small and large cardinalities.
• Based on the maximum likelihood principle a second unbiased method is derived together with a robust and efficient numerical algorithm to calculate the estimate.
• The maximum likelihood approach can also be applied to more than a single HyperLogLog sketch.