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 h

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