Are joins/pullbacks of bloom filters possible?

Question

An interesting advantage of bloom filters over hash tables, that they share with bitarrays, is that they support taking unions & intersections of sets by simply doing bitwise or & bitwise and respectively. The union of two bloom filters is the same as the bloom filter generated by the union of the sets, while the intersection will at least always be greater than or equal to the bloom filter generated by the intersection of the sets.

This got me thinking, if I use bloom filters to represent tuples, is there a way to do it that allows for efficient projections, cartesian products, and joins, so that it could be used as a heuristic for constraint propagation?

Answer 1

Ok, so the short answer to this question seems to be a "yes, but it grows quickly in size". You can view the bloom filters for each tuple element as vectors of bits. In that case, their tensor product will be a "bloom filter" for the cartesian product, where projection can be done by taking partial traces.

The downside of this is that the number of bits grows exponentially with the size of the tuple. You can mitigate this by maintaining a list of bloom filters for all pairs of tuple elements instead, which is still useful for constraint propagation, and gives projection as the intersection of the projection of each pair filter.

Answer 2

Nope. Bloom filters don't support those operations.