5 ms·
HyperLogLog counters are one of my favourite things. They're incredibly clever. So also, you can combine this idea with the idea of bloom filters (another prob
by dhotson 13y ago
HyperLogLog counters are one of my favourite things. They're incredibly clever.
So also, you can combine this idea with the idea of bloom filters (another probabilistic data structure) in a really interesting way.
The goal is to have a _lot_ of counters in a fixed amount of space.
First part is to encode your HyperLogLog counter in unary. So each counter generally only takes up a few bits.
Quick unary tutorial: in unary you count with a sequence of 1's (followed by 0 to signify the end of the number). 3 is encoded as 1110. 5 is 111110. 7 is 11111110. You get the idea.
So also, we're just estimating cardinality, not an exact count. We're estimating if we've seen 2^n things... not n things. Counting to a billion is going to be: 1 billion ~= 2^30 ~= 31 bits.
So you can store all these counters in a big array of bits (a bitmap) and index into it using a hash function. As you probably guessed, all these unary counters will end up overlapping each other in weird ways.
But! The cool thing is if you use a bloom filter to insert and retrieve multiple counters using different hash functions.. and then average the results. The more of these probabilistic and messed up counters you average .. the better the results get!
It's kind of opposite of the usual programmer "junk in, junk out" problem. In this case, the more junk you combine, the better the results. Pretty neat huh? :)
I don't have links to the papers behind these ideas sorry. I learnt most of this from a presentation by Alex Sharp at PyCon Au. Edit: found link to talk - http://pyvideo.org/video/1621/big-data-with-python http://pyvideo.org/video/1621/big-data-with-python
This article explains some of this stuff a bit better: http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html http://highscalability.com/blog/2012/4/5/big-data-counting-h...
- ronaldx 13y agoAveraging the results correctly must be an interesting problem in itself? I believe that standard averages wouldn't necessarily give you the maximum likelihood.
- dhotson 13y agoTo be honest, I'm not an expert at this stuff—merely enthusiastic about it. I could have some details wrong. My intuition says that a straight average should give you fairly good results.. although antirez talks a bit about bias in HyperLogLog counts that he's trying to adjust for. So maybe an average + some bias correction gives you better results?
- ronaldx 13y agoOn light reflection: probably if you do N tests, the modal result would be a good enough choice, or perhaps the median. The issue is that (e.g.) the arithmetic mean would be very influenced by the stats that gave randomly bad results - the very results you are trying to exclude by doing the test multiple times and taking an average.
- dhotson 13y agoSo I think this is roughly what antirez is talking about with 'registers' for a counter. From the article: The standard error of HyperLogLog is 1.04/sqrt(m), where “m” is the number of registers used. Redis uses 16384 registers, so the standard error is 0.81%. My understanding is that the error is very small because you're averaging over 16,000 registers. Edit: also, I think you want the mean because it'll give you back a precise/fractional power of 2 that is pretty close to the actual count. The median would give you the nearest integer power of two, which is probably not a good estimate of the real count. Double edit: looks like there's some research around improving averaging by throwing away outliers: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali...
- nerfhammer 13y agoIt uses harmonic mean, not arithmetic mean
- ronaldx 13y agoMakes sense (as a heuristic?), thanks a lot.