15

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 mentions that the $\tilde{\Omega}(n^2)$ bound is a folklore conjecture. Range diameter query work 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!

karmanaut
  • 1,177
  • 5
  • 16
  • 1
    Well, if ​ $S_k = U$ ​ then $;;; S_i \cap S_j \cap S_k : = : S_i \cap S_j \cap U : = : S_i \cap S_j ;;;$, $;;;$ so answering your queries on n sets is at least as hard as answering 2-set queries on n-1 sets. $;;;;;;;;$ –  Feb 23 '17 at 08:21
  • @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 Feb 23 '17 at 15:13

0 Answers0