4 ms·
Bloom filters also can be used to approximate the size of the intersection and union of two sets.
by fnord77 5y ago
Bloom filters also can be used to approximate the size of the intersection and union of two sets.
- yaa_minu 5y agoCan you please expound on this a little bit more?
- scheme271 5y agoI 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.
- thomasmg 5y agoYes 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_number_of_items_in_a_Bloom_filter 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.
- fnord77 5y agoyes! Also another alternative is Theta datasketches.