4 ms·

Can you please expound on this a little bit more?

• scheme271 5y ago
  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.
  • thomasmg 5y ago
    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_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 ago
      yes! Also another alternative is Theta datasketches.