Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How a HyperLogLog works

opensourceconnections.com

Post reply on HN
Print view View original

11–19 of 19 posts

Re: How a HyperLogLog works

#11

Post by Chinjut »

amitparikh wrote: post #6
cwyers wrote: post #4

I 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.

"Let's say we have a whiteboard and we have to count how many individuals visit our home. If our neighbor visits 5 times, they count as one unique visitor. If a friend comes over once, that's another unique visitor. So far, we have 2 unique visitors."

They may not specifically use the word "distinct" (opting for phrases like "unique visitor" instead), but they certainly make the concept clear.

Re: How a HyperLogLog works

#12

Post by druzac »

Here's a less contrived application. This paper uses hlls to compute miss rate curves for LRU caches from traces of block requests. https://www.usenix.org/system/files/conference/osdi14/osdi14...

The short, simplified story is a list of hlls (a 'counterstack' in the paper, which is an unfortunate bit of historically motivated terminology) are used to count the number of distinct blocks requested. Each hll is fed every block request. A new hll is created after a certain number of requests, so the counts your hlls report correspond to estimations of the number of unique blocks accessed in tails of the trace. The oldest hll has seen every block in the trace, while the most recently created has seen a tail of the trace of length It turns out that you can use this structure to compute stack distances, which are the number of unique blocks accessed between two requests to the same block. The details are a little hairy, so see the paper for the full story.

Re: How a HyperLogLog works

#16

Post by eridius »

0xdeadbeefbabe wrote: post #3
softwaredoug wrote: post #2

Seriously? 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".

Would you expect a title "How Hash Table works"? No, you'd expect "How a Hash Table works". Same thing here.

Re: How a HyperLogLog works

#17

Post by mcherm »

darkmighty wrote: post #10
amitparikh wrote: post #6

Earlier quoted context omitted.

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.

I disagree. I think that the article does an EXCELLENT job of describing it. They avoided the term "cardinality" on purpose, since the target audience was people who might well be scared off by fancy words they weren't familiar with.

And the problem posed was not to count the number of visitors, but to count the number of different people who visited... the fancy word for that is the "cardinality of unique visitors" but "number of different people" is just as accurate.

Counting the number of people could NOT be done with the same amount of space. This example required two simple counters on the blackboard... call it 30 bits of memory, assuming you didn't expect either counter to get more than 8. That's just about exactly enough space to store ONE social security number... and nowhere near enough to count the unique people.

Re: How a HyperLogLog works

#18

Post by [deleted] »

dblock wrote: post #5

A 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…

[deleted]

Re: How a HyperLogLog works

#19

Post by dwenzek »

cwyers wrote: post #4

I 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.

My concerns are not really about the contrived usage of only 2 buckets and decimal numbers. This may give a picture to start with.

But, this is a pity to elude how the final cardinal estimate is computed. And this is shame to publish a gist so sloppy : all key points are buggy (bucket assignation, count of leading zeros, final outcome).

I started my day with "Oh fine, a post witch may help me to understand quickly how hyperloglog works" but I was so confused after that reading, that I forced me to dive into the paper and a high quality code (redis implementation) to leave with a better understanding and no more false assumptions.

This may be ok to simplify an algorithm to help people to grasp it. But at least, as an author, we have to give a true insight.

Post reply on HN