What are leading zeroes in regards to HyperLogLog?

244 views Asked by At

I was reading antirez.com and Wikipedia and some other sources to understang what HLL is and how it works, but each time the term "Leading Zeroes" is used I stumble. Please explain what it means when we talk about HyperLogLog.

1

There are 1 answers

0
Juan Lopes On

Leading zeroes is the number of 0s before the first 1 in the binary representation of the hash. It is equivalent to computing the most significant bit.

HyperLogLog algorithm does not really depend on computing these leading zeroes, it just needs to check a known prefix in the binary representation of the hash. It happens that computing the most significant bit is fast on most hardware implementations.