Set Operations: Union and Intersection

Bloom filters compose elegantly with bitwise operations — as long as the two filters share m, k, AND the hash family.

UNION = bitwise OR (exact)

(A | B).contains(x)  iff  x's bits are all set in A | B
                      iff  for each of x's bits: that bit is set in A OR set in B

If x was added to A, all its bits are set in A → all are set in A|B → MAYBE. Same for items added to B. No extra false positives are introduced beyond what a single filter holding both inserted sets would have had.

INTERSECTION = bitwise AND (approximate, FP rate goes UP)

(A & B).contains(x)  iff  for each of x's bits: that bit is set in BOTH A AND B

Items in the true intersection of A's and B's added sets survive (their bits are in both filters). But items in NEITHER set can also have all their bits coincidentally lit in both filters, especially when m is small or the filters are loaded — those become false positives that neither A nor B alone would have surfaced.

Concretely: if A has FP rate p_A and B has FP rate p_B, the AND'd filter has FP rate ≤ p_A for items in A's set and ≤ p_B for items in B's set, but for items in NEITHER set the FP rate is roughly p_A * p_B of the items that pass A — but the rate of items passing A is itself elevated. In practice the intersection-Bloom should only be treated as a quick filter, then verified against the underlying sets.

When to use these

• UNION: merging filters across shards, distributed systems, replicated logs. Each node maintains its filter; periodically OR them together for a global view.
• INTERSECTION: rare; usually you want exact intersection. Used in some streaming join algorithms as a coarse pre-filter.

What goes wrong

Different m or k or hash family → element-wise bit positions mean different things → garbage. Always negotiate a single shared filter spec for filters that need to compose.