<p>(Sorry but not enough reputation otherwise this would be a comment.)</p>
<p>Note that set difference is equivalent to set intersection with the complement i.e. <span class="math-container">$S_i\backslash S_j = S_i \cap \overline{S_j}$</span>. Thus you could double the number of sets to <span class="math-container">$S_1, S_2, ...., S_k, \overline{S_1}, ..., \overline{S_k}$</span> and apply the set intersection pre-processing to the appropriate pairs.</p>

CC BY-SA 4.0
2020-07-17T15:09:59.297Z
2020-07-17T15:09:59.297Z
Xin Yuan Li
<p>Yes, let's require even less and say you're just interested in figuring out if the difference (similarly, intersection) is empty or not. It is trivial to have a quadratic-sized data structure with constant time query (by pre-processing everything) and also a linear-sized structure with linear query time (by just storing the sets trivially), and it's natural to conjecture that it's impossible to get the best of both worlds (or even get &quot;very far&quot; from the trivial schemes). People have been looking for lower bounds for this type of problem, the area is known as &quot;static data structures&quot;. However, it is recently known that getting sufficiently strong lower bounds for the static data structure required for this type of problem can lead to major (a.k.a. &quot;scary&quot;) consequences (lower bounds on matrix rigidity) that, in sufficient strength, are currently considered beyond reach. See this <a href="https://eccc.weizmann.ac.il/report/2018/188/" rel="nofollow noreferrer">enter link description here</a></p>
<p>You can slightly make the problem more difficult as follows (so as to make proving lower bounds &quot;easier&quot;): You get all the sets first, and have to pre-process. Then, you get a new set <span class="math-container">$T$</span>, and can update the data structure. Finally, you get a query <span class="math-container">$i$</span> and have to take the difference of <span class="math-container">$S_i$</span> and <span class="math-container">$T$</span> (or just report if the intersection is empty). For this very important variation (called &quot;dynamic data structure&quot; or specifically &quot;multiphase problem&quot; defined <a href="https://dl.acm.org/doi/10.1145/1806689.1806772" rel="nofollow noreferrer">here</a>) 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.</p>

CC BY-SA 4.0
2020-07-19T19:02:20.320Z
2020-07-19T19:02:20.320Z
Mahdi Cheraghchi
<p>Given <span class="math-container">$k$</span> sets <span class="math-container">$S_1$</span>, <span class="math-container">$S_2$</span>, <span class="math-container">$\dots$</span>, <span class="math-container">$S_k$</span> in the universe <span class="math-container">$U = \{1, 2, \dots, n\}$</span>, is there a way to preprocess the <span class="math-container">$k$</span> sets such that there is an output-sensitive query algorithm that computes <span class="math-container">$S_i \backslash S_j$</span> for any <span class="math-container">$i$</span> and <span class="math-container">$j$</span>?</p>
<p>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?</p>
<p>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.</p>

CC BY-SA 4.0
2020-07-19T19:42:41.377Z
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.
David Eppstein
<ds.algorithms><ds.data-structures><time-complexity>
Complexity of Set Difference
tamalet
# Complexity of Set Difference

(Asked by: username_0 on 2020-07-14)

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.

**Tags:** ds.algorithms, ds.data-structures, time-complexity

> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2020-07-17. Score: 4

(Sorry but not enough reputation otherwise this would be a comment.)

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.


---

### Answer by username_3 on 2020-07-19. Score: 2

Yes, let's require even less and say you're just interested in figuring out if the difference (similarly, intersection) is empty or not. It is trivial to have a quadratic-sized data structure with constant time query (by pre-processing everything) and also a linear-sized structure with linear query time (by just storing the sets trivially), and it's natural to conjecture that it's impossible to get the best of both worlds (or even get "very far" from the trivial schemes). People have been looking for lower bounds for this type of problem, the area is known as "static data structures". However, it is recently known that getting sufficiently strong lower bounds for the static data structure required for this type of problem can lead to major (a.k.a. "scary") consequences (lower bounds on matrix rigidity) that, in sufficient strength, are currently considered beyond reach. See this [enter link description here](https://eccc.weizmann.ac.il/report/2018/188/)

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](https://dl.acm.org/doi/10.1145/1806689.1806772)) 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.


---

