# Complexity of Set Difference

Given $$k$$ sets $$S_1$$, $$S_2$$, $$\dots$$, $$S_k$$ in the universe $$U = \{1, 2, \dots, n\}$$, is there a way to preprocess the $$k$$ sets such that there is an output-sensitive query algorithm that computes $$S_i \backslash S_j$$ for any $$i$$ and $$j$$?

Has this problem been studied before in the literature? If an output-sensitive algorithm (after preprocessing the sets) is not possible, what is the best complexity we can attain?

I found that there is a related problem which focuses on set intersection rather than set difference. To the best of knowledge, there is no output-sensitive algorithm for the case of set intersection.

• Comment rather than answer because it's a different problem: if you want symmetric difference rather than (as you have written here) asymmetric difference, then the answer is yes, using invertible Bloom filters. Jul 19, 2020 at 19:42

Note that set difference is equivalent to set intersection with the complement i.e. $$S_i\backslash S_j = S_i \cap \overline{S_j}$$. Thus you could double the number of sets to $$S_1, S_2, ...., S_k, \overline{S_1}, ..., \overline{S_k}$$ and apply the set intersection pre-processing to the appropriate pairs.
You can slightly make the problem more difficult as follows (so as to make proving lower bounds "easier"): You get all the sets first, and have to pre-process. Then, you get a new set $$T$$, and can update the data structure. Finally, you get a query $$i$$ and have to take the difference of $$S_i$$ and $$T$$ (or just report if the intersection is empty). For this very important variation (called "dynamic data structure" or specifically "multiphase problem" defined here) proving lower bounds may be within reach (and can lead to lower bounds for all kinds of other data structure problems), but still the state of the art isn't great.