1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you interested in a theoretical or a practical solution? If the latter, can you please provide some statistics: how many distinct elements ($n$) exist and how many sets ($|S|$) do you have? There is a simple solution requiring $O(n \cdot |S|^2)$ time (for each element, sets containing this element form a pair). If it's not acceptable, then: how many pairs of sets have 2 (3, 4) common elements? If possible, can you provide a histogram for all possible numbers of common elements? $\endgroup$
    – user114966
    Commented Mar 6, 2021 at 10:15
  • $\begingroup$ The Orthogonal Vectors problem asks whether every two sets are intersecting. Under reasonable assumptions, when the universe has size $O(\log n)$ and there are $n$ sets, then there are no algorithms running in time $O(n^{2-\epsilon})$. $\endgroup$
    – Yuval Filmus
    Commented Mar 6, 2021 at 16:55
  • $\begingroup$ Thanks, I think I found a solution that is more on the practical side, although it should be possible to motivate it theoretically. I will enter this later and hope I got it right. $\endgroup$
    – Radio Controlled
    Commented Mar 8, 2021 at 15:41
  • $\begingroup$ I also have one peculiarity that I forgot to mention as a special case and I think this allows to sped things up practically. $\endgroup$
    – Radio Controlled
    Commented Mar 8, 2021 at 15:42

1 Answer 1

Reset to default
2
$\begingroup$

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>0$ (on a RAM machine). See for example Chen and Williams, An Equivalence Class for Orthogonal Vectors.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.