3 ms·

The Cuckoo Hashing algorithm is quite fun. I've been reading quite a bit about probabilistic data structures like Bloom Filters, Cuckoo Filters, HLLs etc lately

The Cuckoo Hashing algorithm is quite fun. I've been reading quite a bit about probabilistic data structures like Bloom Filters, Cuckoo Filters, HLLs etc lately. Here's a paper where they're empirically compared to bloom filters of various types: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf > A single HyperLogLog++ structure, for example, can count up to 7.9 billion unique items using 2.56KB of memory with only a 1.65% error rate. Incidentally, Redis has an implementation for HyperLogLogs that has an even smaller error rate of 0.83%, though it uses more memory if I recall correctly. :)

pselbert 10y ago
The HyperLogLog implementation in Redis is extremely well documented and amazingly quick. It drops down to non-probabilistic counting for smaller sample sizes, providing 100% accuracy with comparable speeds. As a fun exercise, which I wrote about [0], I estimated the number of unique words throughout the major works of Charles Dickens. Side note, that man had an amazing hairdo [1]. [0] https://blog.codeship.com/counting-distinct-values-with-hyperloglog/ https://blog.codeship.com/counting-distinct-values-with-hype... [1] https://upload.wikimedia.org/wikipedia/commons/a/aa/Dickens_Gurney_head.jpg https://upload.wikimedia.org/wikipedia/commons/a/aa/Dickens_...
mgunlogson 10y ago
Just so nobody is confused, HyperLogLog etc. are used for a different operation than Bloom/Cuckoo filters. HLL is used to determine how many unique items you have, the cardinality of a set. Bloom/Cuckoo is used to determine set membership, as in "have I seen this item before". Not sure how much that helps but the distinction was lost on me when I started reading about them.
greglindahl 10y ago
HyperLogLog can trade space for accuracy. One annoying thing about some implementations is that they don't give the programmer access to that trade-off. As an example, a search engine might want to have several HyperLogLog counts for every URL on the Internet. In that case, a 64-bit count may be a good choice over 12 kilobytes.

pselbert 10y ago

The HyperLogLog implementation in Redis is extremely well documented and amazingly quick. It drops down to non-probabilistic counting for smaller sample sizes, providing 100% accuracy with comparable speeds. As a fun exercise, which I wrote about [0], I estimated the number of unique words throughout the major works of Charles Dickens. Side note, that man had an amazing hairdo [1]. [0] https://blog.codeship.com/counting-distinct-values-with-hyperloglog/ https://blog.codeship.com/counting-distinct-values-with-hype... [1] https://upload.wikimedia.org/wikipedia/commons/a/aa/Dickens_Gurney_head.jpg https://upload.wikimedia.org/wikipedia/commons/a/aa/Dickens_...

mgunlogson 10y ago

Just so nobody is confused, HyperLogLog etc. are used for a different operation than Bloom/Cuckoo filters. HLL is used to determine how many unique items you have, the cardinality of a set. Bloom/Cuckoo is used to determine set membership, as in "have I seen this item before". Not sure how much that helps but the distinction was lost on me when I started reading about them.

greglindahl 10y ago

HyperLogLog can trade space for accuracy. One annoying thing about some implementations is that they don't give the programmer access to that trade-off. As an example, a search engine might want to have several HyperLogLog counts for every URL on the Internet. In that case, a 64-bit count may be a good choice over 12 kilobytes.