Extending That XOR Trick to Billions of Rows

Summary

Can we extend the XOR trick for finding one or two missing numbers in a list to finding thousands of missing IDs in a billion-row table?Yes, we can! This is possible using a data structure called an Invertible Bloom Filter (IBF) that compares two sets with space complexity based only on the size of the difference. Using a generalization of the XOR trick [1], all the values that are identical cancel out, so the size of this data structure depends only on the size of the difference.Most explanations of Invertible Bloom Filters start with standard Bloom filters, which support two operations: insert and maybeContains. Next, they extend to counting Bloom filters, which enables a delete operation. Finally, they introduce Invertible Bloom Filters, which add an exact get operation and a probabilistic listing operation. In this article, I will take a different approach and build up to an IBF from the XOR trick.IBFs have remained relatively obscure in the software development community while the XOR trick is a well-known technique thanks to leetcode. My goal with this article is to connect IBFs to the XOR trick so that more developers understand this fascinating and powerful data structure. Finding 3 Missing NumbersLet's start with a concrete example:A = [1,2,3,4,5,6,7,8,9,10] B = [1,2,4,5,7,8,10] Set B is missing 3 numbers: {3, 6, 9}.The classic XOR trick works for finding 1 or 2 missing numbers, but what about 3 or more? If we don't know how many numbers are missing, we can use a count field to detect when the usual XOR trick will fail:XOR(A) = 1 ^ 2 ^ ... ^ 10 = 11 COUNT(A) = 10 COUNT(B) = 7 Since B has 7 elements and A has 10, we know 3 numbers are missing—too many for the basic XOR trick.To work around this limitation, we can partition our sets using a hash function. Let's try with 3 partitions: H(1) = 2, H(2) = 1, H(3) = 1, H(4) = 0, H(5) = 0 H(6) = 0, H(7) = 2, H(8) = 1, H(9) = 2, H(10) = 1 A_0 = [4,5,6] B_0 = [4,5] A_1 = [2,3,8,10] B_1 = [2,8,10] A_2 = [1,7,9] B_2 = [...