11–14 of 14 posts
Is there a companion paper somewhere explaining how it works? I tried to read the comments in the source but didn't really understand much. (Might be related to the fact that I never knew much about vanilla HyperLogLog to begin with.)
Is there a companion paper somewhere explaining how it works? I tried to read the comments in the source but didn't really understand much. (Might be related to the fact that I never knew much about vanilla HyperLogLog to begin with.)
This article by antirez helped me understand HyperLogLog a couple years ago http://antirez.com/news/75
Just a small nitpick, for the craic:
> Moreover, while accessing the registers, we need to compute the sum of pow(2,-register) which involves floating point math. > [...] > * The floating point computation was modified in order to allow for multiple operations to be performed in parallel when possible. This was just a matter of adding parens. Floating point math is not commutative, but in this case there was no loss of precision.
Floating point addition is commutative. It is not associative though.
Aside: I'm admittedly grumpy about the commit history, which is filled with entries such as "Add files via upload" and "Update README.md". That, together with the lack of documentation, makes it much more difficult to figure out what's special about this implementation.
Aside: I'm admittedly grumpy about the commit history, which is filled with entries such as "Add files via upload" and "Update README.md". That, together with the lack of documentation, makes it much more difficult to figure out what's special about this implementation.
https://github.com/redis/redis/blob/unstable/src/hyperloglog... seems to be the starting point, given a number of identical comments (complete with typos, e.g. "Estimate cardinality form register histogram"), function names, macros. Copyright isn't preserved, which is troubling in itself. There's a brief mention of Redis's HLL implementation in the README, which is a hint re: the code's origins. The first divergence…
It would be nice to have comments pointing out specifically what changes are important / why they were made.