Computing the intersection of N sets over an M-element universe

Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$.

1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$?

2.) I am also looking for a good parallel and a good distributed algorithm.

• What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. – Raphael Feb 20 '16 at 10:51
• The title you have chosen is not well suited to representing your question. We have collected some advice here. I'll edit in a better one for you now; please take more care in the future! – Raphael Feb 20 '16 at 10:54
• 1. Define "good". What metric do you want to use? What do you want to optimize? What are your criteria for something to count as "good"? I think the question is not well-defined in its current state; community votes, anyone? 2. What approaches have you already considered? Why did you reject them? – D.W. Feb 21 '16 at 19:11

Usual method is you sort all the sets, and select common elements by looking at the beginning of each sorted sequence. This gives you $O(NM)$ algorithm if you do bucket sort. Or in the bucket sort step itself you may check if all the sorted sequence has common elements by doing an operation AND on the bits.

There is even better algorithm that runs in $O(\Sigma_{i=1}^N |S_i| + M$ (i.e. $O(n+M)$) if sets are not multisets (which is the case here). Let $V[1..M]$ be a zero vector. For each $i \in 1..N$, for each $x \in S_i$ do increment $V[x]$. Select those $x$ for which $V[x] = N$. (Note: For multisets also we can do something similar, but we need to do some housekeeping to ensure that we increment only once for a particular element $x$ in a set $S_i$ even if it occurs multiple times.)

If the elements of each sets are already stored in efficient search data structure they you can do it another way. This also works if you have domain as general values rather than values from $Z_M$. You take the smallest sized set $S_{min}$ and select elements from $S_{min}$ one by one by checking if it belongs to every set $S_i$ in time $O(\log |S_i|)$. This gives you $O(N\cdot |S_{min}|\cdot \log(|S_{max}|))$-time algorithm, where $S_{max}$ is the largest set, and which might be better than $O(NM)$ if smallest and largest sets are small enough.

• It does not make much sense to ignore $M$ in running-time bounds in a case such as this. – Raphael Feb 20 '16 at 10:53
• @Shreesh what is $\Sigma$? – T.... Feb 20 '16 at 11:21
• It is $\Sigma_{i=1}^N|S_i|$, the total number of elements. – Shreesh Feb 20 '16 at 11:22

Represent each set $S_i$ as a 0-1 vector $V_i$, then sum all of them. Then your intersection set is the fields where you have $N$ in the sum vector $\Sigma V_i$.

Runtime is $O(N.M)$

• This is worse than the naive algorithm using ordered lists (which will depend on the size of the sets, not the universe). – Raphael Feb 20 '16 at 10:53
• @Raphael Yes, but you don't need to sort. – Mohammad Al-Turkistany Feb 20 '16 at 10:56
• @Raphael I think $O(M.N)$ is best possible. – Mohammad Al-Turkistany Feb 20 '16 at 11:02
• @MohammadAl-Turkistany why do you say so? – T.... Feb 20 '16 at 11:06

Here is an O(n) algorithm:

Create an std::unordered_set

Put all items of vector A into the set

Go through all items of vector B, checking that they are present in the unordered_set, and incrementing the count for each item that is present. Return the final count.

Here is an implementation in C++11, using a lambda for brevity:

vector<int> a {2, 3, 5, 7, 11, 13}; vector<int> b {1, 3, 5, 7, 9, 11}; unordered_set<int> s(a.begin(), a.end()); int res = count_if(b.begin(), b.end(), [&](int k) {return s.find(k) != s.end();}); // Lambda above captures the set by reference. count_if passes each element of b // to the lambda. The lambda returns true if there is a match, and false otherwise.

• Please get rid of the source code and replace it with ideas, pseudo code and arguments of correctness. See here and here for related meta discussions. – Raphael Feb 20 '16 at 10:51
• I'm sorry but, to anyone who doesn't know a lot of C++, your answer is completely incomprehensible. The question mentions nothing at all about C++ so answers shouldn't rely on it. – David Richerby Feb 20 '16 at 17:12