ExaLogLog: Approximate distinct counting with 43% less space than HyperLogLog(arxiv.org)

ExaLogLog: Approximate distinct counting with 43% less space than HyperLogLog

https://arxiv.org/abs/2402.13726

1 comments

tudorg2 anni fa

> We introduce ExaLogLog (ELL), which is based on a recently proposed generalization of earlier data structures such as HLL, EHLL, and PCSA [17]. However, the geometric distribution of the update values is replaced by a distribution for which it is easier to map a 64-bit hash value to a corresponding random value. When optimally configured, ELL achieves a MVP of 3.67 as theoretically predicted and experimentally confirmed. Compared to HLL with 6-bit registers, ELL supports the same operating range up to the exa-scale, but requires 43% less space.

Sounds promising! I love the HyperLogLog idea and it's good to see improvements to it.