Hacker News Reader

Bloom filters also can be used to approximate the size of the intersection and union of two sets.

Can you please expound on this a little bit more?

I believe that if you have two bloom filters containing the hashes of each set, you can do use bitwise AND or a bitwise OR to get approximate intersection or union of the two sets.

Yes exactly. Do a bitwise AND / OR, and count the number of bits that are set. From this count, you can estimate the number of entries in the set: https://en.wikipedia.org/wiki/Bloom_filter#Approximating_the...

HyperLogLog (and variants) can do the union part as well, and need much less space than Bloom filters thought. For large sets, that is. For cardinality smaller than e.g. 100, Bloom filters are better.

yes!

Also another alternative is Theta datasketches.

Reply on news.ycombinator.com