The Invertible Bloom Lookup Table (IBLT) is a simple data sketching algorithm that has a shockingly powerful ability to find the symmetric set difference with size (mainly) relative to the size of the difference, and not the number of elements in either set. The inner workings of it can be better understood here, but the gist of what the data structure does and how it works can be understood in the following diagram.

The graphic above is for specifically reconciling differences between versions. However, this naturally extends to any two sets that typically have a large number of similar elements.

Each of the sets are compressed into an IBLT, which takes up space relative to the size of the difference (with a minor caveat I will not be going over here). Then we take these two versions and simply compare the difference and what remains in the IBLT is only the elements which are different, which we can see visualized above.

This provides some intuition for how the data structure works. However it may not be as clear how this is possible. Recall the XOR operation has the unique property of being the inverse of itself. In other words, if we take a bit string and XOR it with the same string, we get a bit string of just 0s. Therefore by using the XOR operation as the crux of the IBLT data structure, then copies of elements are canceled out of the IBLT.