  Since its invention HyperLogLog has become the standard algorithm for
approximate distinct counting. Due to its space efficiency and suitability for
distributed systems, it is widely used and also implemented in numerous
databases. This work presents UltraLogLog, which shares the same practical
properties as HyperLogLog. It is commutative, idempotent, mergeable, and has a
fast guaranteed constant-time insert operation. At the same time, it requires
28% less space to encode the same amount of distinct count information, which
can be extracted using the maximum likelihood method. Alternatively, a simpler
and faster estimator is proposed, which still achieves a space reduction of
24%, but at an estimation speed comparable to that of HyperLogLog. In a
non-distributed setting where martingale estimation can be used, UltraLogLog is
able to reduce space by 17%. Moreover, its smaller entropy and its 8-bit
registers lead to better compaction when using standard compression algorithms.
All this is verified by experimental results that are in perfect agreement with
the theoretical analysis which also outlines potential for even more
space-efficient data structures. A production-ready Java implementation of
UltraLogLog has been released as part of the open-source Hash4j library.
