Re:Redis new data structure: the HyperLogLog
by nerfhammer on Tuesday April 01, 2014 @03:11PM
(#7510917)
If you made the number of registers (m) extremely large and the register width 1 then a bloom filter and HLL are almost exactly the same (except bloom filters have multiple hashes for the same input and in HLL you only split one hash into two parts).
HLLs are designed to be useful for cardinality counting past the point where a bloom filter would be over capacity. HLL would be useful for set membership but after some threshold the false positive rate will approach 100% at some super-linear rate.
You can also use a bloom filter as a cardinality counter assuming it isn't too filled up yet: http://en.wikipedia.org/wiki/Bloom_filter#Approximating_the_...
HLLs are designed to be useful for cardinality counting past the point where a bloom filter would be over capacity. HLL would be useful for set membership but after some threshold the false positive rate will approach 100% at some super-linear rate.