Bloom Filters: More than a space-efficient hashmap

Re:Bloom Filters: More than a space-efficient hashmap by fnord77 on Wednesday August 11, 2021 @02:03AM (#28138588)

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

[ Parent | on HN ]

Re:Bloom Filters: More than a space-efficient hashmap by yaa_minu on Wednesday August 11, 2021 @02:49AM (#28138865)

Can you please expound on this a little bit more?

[ Parent | on HN ]

Re:Bloom Filters: More than a space-efficient hashmap by scheme271 on Wednesday August 11, 2021 @03:05AM (#28138962)

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.

[ Parent | on HN ]

Re:Bloom Filters: More than a space-efficient hashmap by thomasmg on Wednesday August 11, 2021 @03:38AM (#28139161)

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.

[ Parent | on HN ]

Re:Bloom Filters: More than a space-efficient hashmap by fnord77 on Wednesday August 11, 2021 @07:02PM (#28149131)

yes!

Also another alternative is Theta datasketches.

[ Parent | on HN ]