<p>Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We would like to asnwer this in constant time. Under this setting, the conjecture is that any data structure that allows constant query time requires $\tilde{\Omega}(n^2)$ space.</p>

<p>This problem has very tight connection to distance oracles and range diameter queries. Work by Patrascu regarding <a href="https://people.csail.mit.edu/mip/papers/balls/paper.pdf" rel="noreferrer">distance oracle</a> mentions that the $\tilde{\Omega}(n^2)$ bound is a folklore conjecture. Range diameter query <a href="http://people.scs.carleton.ca/~michiel/2Drangediam.pdf" rel="noreferrer">work</a> also gives good intuition about the lower bounds and conjectures that space requirement for supporting the above queries is quadratic in $n$ is required.</p>

<p>I am looking for additional results of this form for set intersection queries with multiple sets i.e what is the space requirement for answering queries of the form $S_i \cap S_j \cap S_k$. Are there any results for multi set query lower bounds? Or is it trivial to show bounds using the conjecture for $2$ set intersection queries. Any leads in this direction appreciated!</p>

CC BY-SA 3.0
2017-02-23T15:13:12.230Z
@RickyDemer That is true. But this gives weak lower bounds. My conjecture is that for 3 sets, we need at least $\tilde \Omega(n^3)$ (This comes from algorithms that perform delay enumeration in database theory) but no provable results. Which is why I am looking for some research on this now!
karmanaut
<ds.data-structures><lower-bounds><communication-complexity>
Set Intersection lower bounds
karmanaut
# Set Intersection lower bounds

(Asked by: username_0 on 2017-02-22)

Consider $S\_1, ...,S\_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S\_i \cap S\_j$ is empty or not. We would like to asnwer this in constant time. Under this setting, the conjecture is that any data structure that allows constant query time requires $\tilde{\Omega}(n^2)$ space.

This problem has very tight connection to distance oracles and range diameter queries. Work by Patrascu regarding [distance oracle](https://people.csail.mit.edu/mip/papers/balls/paper.pdf) mentions that the $\tilde{\Omega}(n^2)$ bound is a folklore conjecture. Range diameter query [work](http://people.scs.carleton.ca/~michiel/2Drangediam.pdf) also gives good intuition about the lower bounds and conjectures that space requirement for supporting the above queries is quadratic in $n$ is required.

I am looking for additional results of this form for set intersection queries with multiple sets i.e what is the space requirement for answering queries of the form $S\_i \cap S\_j \cap S\_k$. Are there any results for multi set query lower bounds? Or is it trivial to show bounds using the conjecture for $2$ set intersection queries. Any leads in this direction appreciated!

**Tags:** ds.data-structures, lower-bounds, communication-complexity

> **Comments:**
> **username_0**: @RickyDemer That is true. But this gives weak lower bounds. My conjecture is that for 3 sets, we need at least $\tilde \Omega(n^3)$ (This comes from algorithms that perform delay enumeration in database theory) but no provable results. Which is why I am looking for some research on this now!  

---

## 0 answers

