-1
$\begingroup$

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.

$\endgroup$
  • 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 Ito Aug 20 '12 at 13:06
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ But if you can choose your data structure, why not choose a sorted array? $\endgroup$ – Jeffε Aug 20 '12 at 17:11
  • $\begingroup$ I can indeed choose the data structure of choice, as long as their creation is not costly. $\endgroup$ – Valerio Schiavoni Aug 20 '12 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$ – Massimo Cafaro Aug 20 '12 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 '12 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$ – Massimo Cafaro Aug 22 '12 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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