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
This article explains some of this stuff a bit better: http://highscalability.com/blog/2012/4/5/big-data-counting-h...