# UltraLogLog: A Practical and More Space-Efficient Alternative to HyperLogLog for Approximate Distinct Counting

**Authors:** Otmar Ertl  
**arXiv:** [2308.16862](https://arxiv.org/abs/2308.16862)  
**Date:** 2023-08-31  
**Summary page:** https://www.summarizepaper.com/en/paper/2308.16862v5/

## Key points

- UltraLogLog is a groundbreaking algorithm for approximate distinct counting, offering a more space-efficient alternative to HyperLogLog.
- It achieves a 28% reduction in space requirements compared to HyperLogLog due to its innovative design and efficient data structures.
- UltraLoog introduces a simpler and faster estimator that maintains a 24% space reduction while ensuring estimation speeds comparable to those of HyperLoog.
- In non-distributed settings where martingale estimation can be applied, UltraLoog reduces space requirements by 17%.
- The algorithm's smaller entropy and utilization of 8-bit registers contribute to better compaction when using standard compression algorithms, enhancing storage efficiency and streamlining data processing operations.
- Experimental results validate the theoretical analysis supporting UltraLoog's enhanced performance metrics.
- A production-ready Java version of UltraLoog has been integrated into the open-source Hash4j library for practical implementation by developers seeking advanced solutions for distinct counting applications.

## Summary

UltraLogLog is a groundbreaking algorithm that offers a practical and more space-efficient alternative to HyperLogLog for approximate distinct counting. Originally, HyperLogLog emerged as the standard algorithm in this field due to its space efficiency and compatibility with distributed systems, making it a popular choice across various databases. However, UltraLogLog presents itself as a formidable contender by possessing similar practical properties to HyperLogLog while offering significant improvements. One of the key advantages of UltraLogLog is its ability to achieve a 28% reduction in space requirements for encoding the same amount of distinct count information compared to HyperLogLog. This reduction in space utilization can be attributed to the algorithm's innovative design and efficient data structures. Additionally, UltraLoog introduces a simpler and faster estimator that maintains a 24% space reduction while ensuring estimation speeds comparable to those of HyperLoog. In scenarios where martingale estimation can be applied in non-distributed settings, UltraLoog showcases its capability to reduce space requirements by 17%. Furthermore, the algorithm's smaller entropy and utilization of 8-bit registers contribute to better compaction when employing standard compression algorithms. These features not only enhance storage efficiency but also streamline data processing operations. Experimental results validate the theoretical analysis supporting UltraLoog's enhanced performance metrics. The findings underscore the potential for developing even more space-efficient data structures inspired by UltraLoog's success. To facilitate practical implementation, a production-ready Java version of UltraLoog has been integrated into the open-source Hash4j library, ensuring accessibility and usability for developers seeking advanced solutions for distinct counting applications. In conclusion,  stands out as an innovative and effective solution that redefines the landscape of approximate distinct counting algorithms. Its superior , fast insert operation, and compatibility with  position it as a valuable tool for optimizing data processing tasks across various domains.