<p>Although many efficient set intersection algorithms have been proposed in the literature, my recommendation is the algorithm proposed in this paper:
<a href="https://arxiv.org/abs/1103.2409" rel="nofollow noreferrer">Bolin Ding, Arnd Christian König: Fast Set Intersection in Memory. PVLDB 4(4): 255-266 (2011)</a>, which seems most practical.</p>

<p>Also, note that there is a related question in the <a href="https://stackoverflow.com/questions/497338/efficient-set-intersection-algorithm">stackoverflow</a>.</p>

CC BY-SA 3.0
2012-08-20T15:32:14.830Z
2017-07-31T18:40:22.990Z
2017-07-31T18:40:22.990Z
Snowie
<p>Call your sets <em>A</em> and <em>B</em> respectively, and assume wlog that <em>Card(A) = n &lt; Card(B) = m</em>. If you are allowed to choose a data structure, you may want to use a hash table <em>H</em> as follows. Store all of the elements of set <em>B</em> in <em>H</em>. Then iterate through the elements in <em>A</em>. For each element <em>e</em>, check if <em>e</em> is in <em>H</em>. If yes, output <em>e</em> in the intersection set, otherwise in the difference set.
Since looking up an element in the hash table is <em>O(1)</em> (on average), the algorithm requires <em>O(n)</em> and is linear in the cardinality of <em>A</em>.</p>

<p>If <em>Card(A) = Card(B)</em>, a fast intersection algorithm is to use a <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">Bloom filter</a> to store the sets, and then intersection is implemented with bitwise AND operations. </p>

CC BY-SA 3.0
2012-08-20T17:11:18.290Z
But if you can choose your data structure, why not choose a sorted array?
Jeffε
CC BY-SA 3.0
2012-08-20T20:36:09.733Z
I can indeed choose the data structure of choice, as long as their creation is not costly.
Valerio Schiavoni
CC BY-SA 3.0
2012-08-20T20:40:33.530Z
@JeffE, can we use a sorted array to solve the problem in *o(n+m)*  ? If not, what is the advantage ? Thank you in advance.
Massimo Cafaro
CC BY-SA 3.0
2012-08-21T13:49:56.847Z
@MassimoCafaro: The advantage is fewer lines of code, smaller constant factors, and zero probability of error.  The problem _obviously_ can't be solved exactly in $o(n+m)$ time, because you have to read the entire input.
Jeffε
CC BY-SA 3.0
2012-08-22T03:33:05.307Z
@JeffE, thank you very much for your answer. It's my fault: my question, as posed, sounds silly. What I actually meant is: given that preprocessing the arrays to sort them requires *O(n lg n)* + *O(m lg m)* which is higher than the *O(m)* average time required to populate a hash table with the elements of set *B*, it is then possible to design a *sublinear* time algorithm that with high probability solves the problem ? So that one can somewhat balance the preprocessing cost with a fast, even though randomized, algorithm using the sorted arrays.
Massimo Cafaro
CC BY-SA 3.0
2012-08-20T14:03:18.207Z
2012-08-20T14:03:18.207Z
Massimo Cafaro
<p>What is the most efficient algorithm to compute the difference between two set data structures? In particular, the algorithm should efficiently discover elements in the first set that are also in the second set and return the difference-set.</p>

CC BY-SA 3.0
2012-08-20T13:06:46.600Z
(1) Which “set data structure” will the algorithm receive?  (2) Why should an “algorithm to compute set difference” discover elements in the intersection of the two given sets?  (3) What do you know?  What have you tried?
Tsuyoshi Ito
<ds.data-structures><data-sets>
Most efficient algorithm to compute set difference?
Valerio Schiavoni
# Most efficient algorithm to compute set difference?

(Asked by: username_0 on 2012-08-20)

What is the most efficient algorithm to compute the difference between two set data structures? In particular, the algorithm should efficiently discover elements in the first set that are also in the second set and return the difference-set.

**Tags:** ds.data-structures, data-sets
> **Comments:**
> **username_1**: (1) Which “set data structure” will the algorithm receive?  (2) Why should an “algorithm to compute set difference” discover elements in the intersection of the two given sets?  (3) What do you know?  What have you tried?  

---

## 2 answers

### Answer by username_2 on 2012-08-20. Score: 3

Although many efficient set intersection algorithms have been proposed in the literature, my recommendation is the algorithm proposed in this paper:
[Bolin Ding, Arnd Christian König: Fast Set Intersection in Memory. PVLDB 4(4): 255-266 (2011)](https://arxiv.org/abs/1103.2409), which seems most practical.

Also, note that there is a related question in the [stackoverflow](https://stackoverflow.com/questions/497338/efficient-set-intersection-algorithm).


---

### Answer by username_3 on 2012-08-20. Score: 1

Call your sets *A* and *B* respectively, and assume wlog that *Card(A) = n < Card(B) = m*. If you are allowed to choose a data structure, you may want to use a hash table *H* as follows. Store all of the elements of set *B* in *H*. Then iterate through the elements in *A*. For each element *e*, check if *e* is in *H*. If yes, output *e* in the intersection set, otherwise in the difference set.
Since looking up an element in the hash table is *O(1)* (on average), the algorithm requires *O(n)* and is linear in the cardinality of *A*.

If *Card(A) = Card(B)*, a fast intersection algorithm is to use a [Bloom filter](http://en.wikipedia.org/wiki/Bloom_filter) to store the sets, and then intersection is implemented with bitwise AND operations.

> **Comments:**
> **username_4**: But if you can choose your data structure, why not choose a sorted array?  
> **username_0**: I can indeed choose the data structure of choice, as long as their creation is not costly.  
> **username_3**: @JeffE, can we use a sorted array to solve the problem in *o(n+m)*  ? If not, what is the advantage ? Thank you in advance.  
> **username_4**: @MassimoCafaro: The advantage is fewer lines of code, smaller constant factors, and zero probability of error.  The problem _obviously_ can't be solved exactly in $o(n+m)$ time, because you have to read the entire input.  
> **username_3**: @JeffE, thank you very much for your answer. It's my fault: my question, as posed, sounds silly. What I actually meant is: given that preprocessing the arrays to sort them requires *O(n lg n)* + *O(m lg m)* which is higher than the *O(m)* average time required to populate a hash table with the elements of set *B*, it is then possible to design a *sublinear* time algorithm that with high probability solves the problem ? So that one can somewhat balance the preprocessing cost with a fast, even though randomized, algorithm using the sorted arrays.  

---

