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!

  • 1
    $\begingroup$ 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. $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user6973
    Feb 23, 2017 at 8:21
  • $\begingroup$ @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! $\endgroup$
    – karmanaut
    Feb 23, 2017 at 15:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.