Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

HLL: add 1 to the number of zeros? #14

Open
jwr opened this issue Feb 23, 2018 · 0 comments
Open

HLL: add 1 to the number of zeros? #14

jwr opened this issue Feb 23, 2018 · 0 comments

Comments

@jwr
Copy link

jwr commented Feb 23, 2018

Ok, I realize this might be wasting your time, but I can't let go and I have to ask:

In hll/insert*, line 24

zeros (Long/numberOfTrailingZeros (bit-shift-right hv offset))]
you do not add 1 to the number of trailing zeros. Reading the original HLL paper, as well as the subsequent "Understanding the HyperLogLog", it seems they always add 1 (to quote from the original paper: "equivalently one plus the length of the initial run of 0’s").

This makes a big difference, since the buckets are initialized with zeros, so not adding 1 means that in many cases we won't even update the buckets.

I have to ask, because yes, of course I added inc to that line, and quickly discovered that when I do, the tests do not pass and the results are incorrect. So the code works correctly, but why?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant