Set query in a universe with overlapping sets

Question

Suppose we have a universe $U$ of $n$ items $u_1,u_2,u_3,...,u_n$. And a collection of sets (no restriction on being disjoint or exhaustive etc.) which cover some items. Size of each set is bounded by some parameter $k<n$. We need to perform the following update and query efficiently.

Update: 1- Add a new set to the collection having some elements of $U$.

2- Delete any existing set from collection.

Query: Given two vertices, does there exist a set which has both these vertices.

A trivial way would be to maintain a 2D matrix with each $M(i,j)$ storing number of sets containing both $i$ and $j$. Update would be done in $O(k^2)$ by incrementing $M(i,j)$ for all pairs of vertices in set S_i. The query can be done in$ O(1)$ time.

I am looking for some solution with o(k^2) update time and poly log query time..

Answer 1

One can reverse the roles of elements and sets. This can be seen by considering a Boolean matrix of size $m\times n$ where there are $m$ sets and $n$ is the size of the universe. The $i$th row corresponds to the characteristic vector of the $i$th set. Transposing this matrix reverses the roles of sets and elements ($n$ sets and $m$ elements).

Now the question of whether there exists a set containing two items is the same of asking if two sets intersect (after reversing the roles). In a paper that has recently been accepted to WADS 2015, (arxiv version here. see Theorem 3), we show various tradeoffs for the fully dynamic set intersection problem. Since adding/deleting a set corresponds (after role reversal) to adding/deleting an element to or from a bunch of sets, then in terms of the question in mind the update time would be $S\cdot N^{1-\epsilon}$ and the query time is $N^\epsilon$, where $S$ is the size of the set, $N$ is the sum of the sizes of all of the sets, and $0\leq \epsilon\leq 1$. Notice that different points on this tradeoff curve use a different amount of space, specifically $O(N^{2-2\epsilon})$ words. In particular, for constant query time, the space usage is $O(N^2)$ words and the update time is $O(N)$.

However, for the particular scenario where one is interested in poly log query time, we have a preprint (arxiv version here) that in particular shows that unless the 3SUM conjecture is false, if one is interested in sub-polynomial query time, then the constructing of a static data structure for disjointness queries requires $\Omega(N^{2-o(1)})$ time. This immediately implies a lower bound for the incremental version of the problem, where one is only allowed to add elements to sets. In particular, since the total number of elements in sets, counting multiplicity, is $N$, each element that is being added must spend $\Omega(N^{1-o(1)})$ time.

As such, a (polynomially) more efficient update time does not seem likely, even when allowing poly-log query time.