The symmetric difference is {3, 6, 5}—elements 3 and 6 are only in A, while element 5 is only in B.

The naive approach of checking |COUNT(A) - COUNT(B)| = 1 fails here because the count difference is 1, but the symmetric difference has 3 elements. Applying the basic XOR trick gives a meaningless result.

To detect this case, we can use an additional accumulator with a hash function:

COUNT(A) = 5, XOR(A) = 2
COUNT(B) = 4, XOR(B) = 2
XOR_HASH(A) = H(1) ^ H(2) ^ H(3) ^ H(4) ^ H(6)
XOR_HASH(B) = H(1) ^ H(2) ^ H(4) ^ H(5)

XOR(B) ^ XOR(A) = 0
XOR_HASH(B) ^ XOR_HASH(A) = H(3) ^ H(5) ^ H(6) 
H(3) ^ H(5) ^ H(6) ≠ H(0) 

While we can't yet recover the full symmetric difference, we can detect when the XOR result is unreliable by checking if the hash accumulators behave consistently.

Invertible Bloom Filters

The Core Idea

The original XOR trick relies on an accumulator that stores the XOR aggregate of a list. Building on this, we've introduced:

1. Partitioning to divide sets into smaller parts
2. Additional accumulators that store the element count and hash of XOR aggregate

To fully generalize this into a robust data structure, we need:

1. A partitioning scheme that creates recoverable partitions with high probability
2. An iterative process that uses recovered values to unlock additional partitions

This is exactly what Invertible Bloom Filters [2] provide. IBFs use a Bloom filter-style hashing scheme to assign elements to multiple partitions, then employ a graph algorithm called "peeling" to iteratively recover the symmetric difference with very high probability [3].

Structure

An IBF consists of an array of cells, where each cell contains three accumulators:

• idSum: XOR aggregate of element values
• hashSum: XOR aggregate of element hashes
• count: number of elements in the cell

Figure 2: Figure from [2] showing the process of encoding elements into IBF cells.

Operations

For computing symmetric differences, IBFs support three key operations:

1. Encode: Build an IBF from a set of values
2. Subtract: Subtract one IBF from another—identical values cancel out, leaving only the symmetric difference
3. Decode: Recover stored values by finding "pure" cells (count = ±1 and H(idSum) = hashSum) and iteratively "peeling" them

The IBF has one parameter d—the expected size of the symmetric difference. With proper sizing (typically m > 1.22d cells), IBFs recover the full symmetric difference with very high probability.

Algorithms for each IBF operation from [2].

Example Implementation

I have not found a solid, maintained library of IBFs in any language (if you know of any please let me know!), so I created a basic implementation in Python if you would like to play with it: https://gist.github.com/hundredwatt/a1e69ff300de941041d824e49249d3d7

Example usage:

a = [1, 2, 4, 5, 6, 7, 9, 10]
b = [1, 3, 4, 5, 6, 7, 9, 10]
set_a = set(a)
set_b = set(b)
ibf_size = 100
k = 4


ibf_a = IBF(size=ibf_size, k=k)
for item in a:
   ibf_a.insert(item)

ibf_b = IBF(size=ibf_size, k=k)
for item in b:
   ibf_b.insert(item)


diff_ibf = ibf_a.subtract_ibf(ibf_b)


success, decoded_added, decoded_removed = diff_ibf.decode()


assert(success)
expected_added = set_a - set_b
expected_removed = set_b - set_a

print("--- Verification ---")
print(f"Expected added (in A, not B): {len(expected_added)} items")
print(f"Decoded added:                  {len(decoded_added)} items")
assert(expected_added == decoded_added)

print(f"Expected removed (in B, not A): {len(expected_removed)} items")
print(f"Decoded removed:                  {len(decoded_removed)} items")
assert(expected_removed == decoded_removed)