How to find an distinct URL only in set A not in set B.

Question

There are two sets of URL, both contains millions of URLs. Now, How can I get an URL from A that is not in B. What's The best methods?
Note: you can use any technique, use any tools like database, mapreduce, hashcode, etc, . We should consider the memory efficient, time efficient. You have to consider that every set (A and B) have millions of URL. We should try to find the specific URLs using less memory and less time.

Answer 1

A decent algorithm might be:

load all of set A into a hashmap, O(a)

traverse set B, and for each item, delete the identical value from set A (from the hashmap) if it exists, O(b)

Then your hashmap has the result. This would be O(a+b) where a is size of set A and b is size of set B. (In practice, this would be multiplied by the hash time, which ideally corresponds to approximately O(1) for a good hash.)

Answer 2

Something perhaps a little naive might be a procedure like

1. Sort list A
2. Sort list B

3. Navigate list A and B together such that:

   a. Increment pointer to A and pointer to B when elements match

   b. Increment pointer to B until the element matches the next element in a or until the record b in B would appear after the next element in a (this rule discards elements in B that are not in A)

   c. A match has been found when incrementing subject to these rules such that the next element b in B does not match the next element a in A.

---

This might actually be an interesting place to apply Bloom filters: construct a Bloom filter for set B then for every URL in set A determine if it is in set B. With diminishingly small probability of error you should be able to find all URLs in A not in B.

Answer 3

(sort -u A; cat B B) | sort | uniq -u