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.
$\begingroup$
$\endgroup$
1
-
7$\begingroup$ (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? $\endgroup$– Tsuyoshi ItoAug 20, 2012 at 13:06
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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), which seems most practical.
Also, note that there is a related question in the stackoverflow.
$\begingroup$
$\endgroup$
5
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 to store the sets, and then intersection is implemented with bitwise AND operations.
-
3$\begingroup$ But if you can choose your data structure, why not choose a sorted array? $\endgroup$– JeffεAug 20, 2012 at 17:11
-
$\begingroup$ I can indeed choose the data structure of choice, as long as their creation is not costly. $\endgroup$ Aug 20, 2012 at 20:36
-
$\begingroup$ @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. $\endgroup$ Aug 20, 2012 at 20:40
-
$\begingroup$ @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. $\endgroup$– JeffεAug 21, 2012 at 13:49
-
$\begingroup$ @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. $\endgroup$ Aug 22, 2012 at 3:33