---
abstract: 'This work presents new cardinality estimation methods for data sets recorded by HyperLogLog sketches. A simple derivation of the original estimator was found, that also gives insight how to correct its deficiencies. The result is an improved estimator that is unbiased over the full cardinality range, is easy computable, and does not rely on empirically determined data as previous approaches. Based on the maximum likelihood principle a second unbiased estimation method is presented which can also be extended to estimate cardinalities of union, intersection, or relative complements of two sets that are both represented as HyperLogLog sketches. Experimental results show that this approach is more precise than the conventional technique using the inclusion-exclusion principle.'
author:
- Otmar Ertl
bibliography:
- 'bibliography.bib'
title: New Cardinality Estimation Methods for HyperLogLog Sketches
---

Introduction
============

Counting the number of distinct elements in a data stream or large datasets is a common problem in big data processing. In principle, finding the number of distinct elements $\symCardinality$ with a maximum relative error $\symError$ in a data stream requires $\symBigO(\symCardinality)$ space [@Alon1999]. However, probabilistic algorithms that achieve the requested precision only with high probability are able to drastically reduce space requirements. Many different probabilistic 