Efficient cardinality of set overlap relation Assume that we have a set S of sets s.
Every pair (s,s') in SxS can be overlapping or not.
How can we efficiently compute the number of pairs (s,s') that are overlapping, i.e. that share at least one element?
Additional: actually each set s occurs a number of times (S is a multiset). I have tried to create a matrix M of scipy.sparse.csr_matrix that stores the subset partial order over S. Then I have tried to add the additional edges for overlaps through M.T.dot(M) to then later compute f.dot(M).dot(f.T), where f gives the frequency for each s. Unfortunately M.T.dot(M) becomes too large, so if anything, we probably have to propagate the counts through the subset partial order one after the other.
Hints: it might seem apparent at first to just take the sum over the union of all elements in all s of their frequency squared to sum up the number of pairs sharing one particular element. However the problem is that this counts many pairs multiple times. For example {a,b} is counted for a and also for b. This is why it seems important to use the subset partial order.
Any ideas?
Consider the following problem. We are given $n$ sets $S_1,\ldots,S_n \subseteq \{1,\ldots,\log n\}$, and have to decide whether there are two disjoint sets among them. This problem is known as Orthogonal Vectors (OV), and it is conjectured that it cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon&gt;0$ (on a RAM machine). See for example Chen and Williams, An Equivalence Class for Orthogonal Vectors.