How a HyperLogLog works
opensourceconnections.com
How a HyperLogLog works
1–10 of 19 posts
Re: How a HyperLogLog works
#2Seriously? Someone renamed the title? Nobody likes Ren & Stimpy these days?
Re: How a HyperLogLog works
#3Seriously? Someone renamed the title? Nobody likes Ren & Stimpy these days?
Surely that someone favored homework over R&S, but "a HyperLogLog" Why does it need an "a"? I would have expected "How HyperLogLog works".
Re: How a HyperLogLog works
#4I don't think this does a very good job of explaining the HyperLogLog, honestly. A slightly less contrived example would've been useful.
Re: How a HyperLogLog works
#5A simpler and more concise explanation in https://github.com/aaw/hyperloglog-redis.
"The basic idea of HyperLogLog (and its predecessors PCSA, LogLog, and others) is to apply a good hash function to each value observed in the stream and record the longest run of zeros seen as a prefix of any hashed value. If the hash function is good, the bits in any hashed value should be close to statistically independent, so seeing a value that starts with exactly X zeros should happen with probability close to 2 -(X + 1). So, if you've seen a run of 5 zeros in one of your hash values, you're likely to have around 2 6 = 64 values in the underlying set. The actual implementation and analysis are much more advanced than this, but that's the idea."
Re: How a HyperLogLog works
#6I don't think this does a very good job of explaining the HyperLogLog, honestly. A slightly less contrived example would've been useful.
I agree. Additionally, the words "distinct" or "cardinality" don't appear anywhere in this article, which is a major omission when discussing HyperLogLog. The primary use of the algorithm is to provide a cardinality estimate.
Re: How a HyperLogLog works
#7A simpler and more concise explanation in https://github.com/aaw/hyperloglog-redis . "The basic idea of HyperLogLog (and its predecessors PCSA, LogLog, and others) is to apply a good hash function to each value observed in the stream and record the longest run of zeros seen as a prefix of any hashed value. If the hash function is good, the bits in any hashed value should be close to statistically independent, so seei…
Interesting to see Bitcoin use almost the same principle. Essentially it's "if there is a hash with enough leading zeroes, we can assume a lot of CPU time has been put into the network."
Of course that's just an artifact of what's really happening, which is pseudo-random values + laws of probability.
Re: How a HyperLogLog works
#8I don't think this does a very good job of explaining the HyperLogLog, honestly. A slightly less contrived example would've been useful.
In other words: https://www.youtube.com/watch?v=cDGlN6mluGA
:)
Re: How a HyperLogLog works
#9Seriously? Someone renamed the title? Nobody likes Ren & Stimpy these days?
You really think that there are a lot of people on HN who know what Ren&Stimpy was?
Re: How a HyperLogLog works
#10I don't think this does a very good job of explaining the HyperLogLog, honestly. A slightly less contrived example would've been useful.
I agree. Additionally, the words "distinct" or "cardinality" don't appear anywhere in this article, which is a major omission when discussing HyperLogLog. The primary use of the algorithm is to provide a cardinality estimate.
Agreed, cardinality is the key word: it goes with how his example is inappropriate -- if you were just counting the number of people coming in a simple addition (and maybe take a log() ) would cost just as much. I believe the usefulness of HLL is evaluating the cardinality of sets you need to access -- you "sample" the set and get a quick estimate of the cardinality of certain objects.