  We discuss the problem of counting distinct elements in a stream. A stream is
usually considered as a sequence of elements that come one at a time. An exact
solution to the problem requires memory space of the size of the stream. For
many applications this solution is infeasible due to very large streams. The
solution in that case, is to use a probabilistic data structure (also called
sketch), from which we can estimate with high accuracy the cardinality of the
stream. We present a new algorithm, ExtendedHyperLogLog (EHLL), which is based
on the state-of-the-art algorithm, HyperLogLog (HLL). In order to achieve the
same accuracy as HLL, EHLL uses 16% less memory. In recent years, a martingale
approach has bean developed. In the martingale setting we receive better
accuracy at the price of not being able to merge sketches. EHLL also works in
the martingale setting. Martingale EHLL achieves the same accuracy as
Martingale HLL using 12% less memory.

Data Structures and Algorithms