Set Operations: Union and Intersection

Two Bloom filters can be combined without ever seeing the original keys, because a filter is just an array of bits. After this lesson your program holds several named filters, merges them with UNION and INTERSECT, refuses merges that make no sense, and estimates how many distinct keys a filter holds from its bit count.

The compatibility rule

A bit position only means something relative to m, k and the hash functions that produced it. Two filters can be combined only if all three match. If m or k differ, bit 7 in one filter and bit 7 in the other describe different things, and the merged array is meaningless. Your program must refuse: UNION and INTERSECT print ERR MISMATCH and create nothing.

Union is bitwise OR, and it is exact

If a key was added to A, all its bits are set in A, so they are set in A | B. The same holds for B. So A | B answers MAYBE for every key in either set, and the bit array is identical to the one you would get by adding both sets to a single filter. Union introduces no extra error. This is how sharded systems build a global view: every node keeps a filter, and a coordinator ORs them together.

Intersection is bitwise AND, and it is approximate

A key in both sets has its bits set in both filters, so it survives A & B. But a key that is only in A can also survive: its bits may be set in B by other keys. A & B is therefore a filter for a superset of the true intersection, with more false positives than either input. Treat it as a cheap first pass, then confirm against the real data.

Worked example

With m = 16, k = 2: filter A holds red and green, filter B holds green and blue.

A        1000010000000110   4 bits set
B        1001000000010010   4 bits set
A | B    1001010000010110   6 bits set
A & B    1000000000000010   2 bits set

green is in both sets, so its bits appear in both inputs. The union has 6 bits, not 4 + 4 = 8: the shared key's bits are counted once, because OR merges instead of adding.

Estimating how many keys a filter holds

A filter does not store a count, but its bit count reveals one. After n keys, each bit is still 0 with probability about e^(-k*n/m), so the expected number of set bits X satisfies X/m = 1 - e^(-k*n/m). Solving for n:

n_estimate = -(m / k) * ln(1 - X / m)

For example, a filter with m = 1024 and k = 3 holding 80 distinct keys has 216 bits set, and the formula gives 80.87, which rounds to 81. If every bit is 1 the logarithm is undefined, so report FULL.

This also sizes a merge. The estimate of A | B is the number of distinct keys in either, and by inclusion and exclusion the intersection has about est(A) + est(B) - est(A | B) keys, without any false-positive blow-up from the AND.

Common mistakes

• Merging without checking m and k. The error must be ERR MISMATCH, and the output name must not exist afterwards.
• Sharing storage. UNION u a b must produce a new, independent filter. If ADD u key changes a, you aliased the array.
• Forgetting that the output name may be one of the inputs (UNION a a b updates a in place).
• Checking for a missing filter after the mismatch. A missing filter is reported first: ERR NOFILTER.
• Trusting A & B as exact. Its CHECK can say MAYBE for a key that is only in A.

Your exercise

The starter already manages named filters with INIT, ADD, CHECK, POPCOUNT and BITS. You write UNION, INTERSECT (with the error rules) and ESTIMATE.