ExaLogLog: Space-Efficient and Practical Approximate Distinct Counting up to the Exa-Scale

这项工作介绍了一种新的数据结构ExaLogLog，用于近似不同计数，它具有与流行的HyperLogLog算法相同的实用特性。它是可交换的、幂等的、可合并的、可简化的，具有常数时间的插入操作，并支持高达exa级别的不同计数。同时，根据理论推导和实验证明，它只需要43%的空间就能达到相同的估计误差。

解决问题：该论文旨在介绍一种新的数据结构ExaLogLog，用于近似计数，可以达到与流行的HyperLogLog算法相同的实际效果。

关键思路：ExaLogLog是一种新的数据结构，可以进行近似的不同计数，并支持合并、降低、插入和计数操作。相比于HyperLogLog算法，ExaLogLog需要更少的空间来达到相同的估计误差。

其他亮点：论文通过理论推导和实验证明，ExaLogLog可以支持高达exa级别的不同计数，并且可以减少43%的空间。实验使用了不同的数据集，并且提供了开源代码。该工作为近似计数领域提供了一种新的、高效的解决方案。

相关研究：最近的相关研究包括Probabilistic Counting Algorithms for Data Base Applications、HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm等。