Probabilistic Data Structure Showdown: Cuckoo Filters vs. Bloom Filters

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by manish_gill on Monday November 28, 2016 @02:27PM (#13057723)

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

> 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. :)

[ Parent | on HN ]

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by pselbert on Monday November 28, 2016 @04:38PM (#13058662)

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-hype... [1] https://upload.wikimedia.org/wikipedia/commons/a/aa/Dickens_...

[ Parent | on HN ]

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by mgunlogson on Monday November 28, 2016 @05:17PM (#13058901)

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.

[ Parent | on HN ]

Re:Probabilistic Data Structure Showdown: Cuckoo Filters vs.... by greglindahl on Monday November 28, 2016 @05:48PM (#13059109)

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.

[ Parent | on HN ]