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

Question

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.

Answer 1

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.

Answer 2

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)$

Answer 3

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.