5

I would like to sort a list of people into buckets, as duplicates, by an email comparison, but I can't seem to find an efficient way.

Specifications

  • A person has 5 email fields, so in order to know if one person is a duplicate of the latter, I must compare each of his emails to each of of the latter's.

  • A might be duplicate of B and C, but the only way of knowing is comparing A with B and then B with C (See the below image).

enter image description here

  • My input is a list of records of, for example, 5.000 among which there might be no duplicates, all might be the same person, or any other random combination of duplicity.

So, all in all, how can I place this list of people into buckets ? Initially I thought of doing it by nesting a loop and comparing each record to every other record and, if they were matching, create a list which I would save in another list, that way grouping them. The problem is that I then had to nest yet another loop to iterate the created lists in order to validate that one record was not a duplicate of any of the previous ones. The benchmarks of this, obviously, were horrible.

  • It's not clear to me whether you're sorting or finding duplicates. – Robert Harvey Mar 16 '18 at 17:10
  • I know the OP, I am pretty sure he means "sorting in buckets", i.e. finding duplicates, will propose an edit. – Davide Fiocco Mar 16 '18 at 17:22
6

This problem is known, AFAIK, as "partitioning a set into equivalence classes", but I could not find ad hoc a good web resource for it, so I try give a general outline of an efficient algorithm:

The outer part is straightforward:

Start with an empty set of buckets. Each bucket will hold a list of persons, and, for any pair of different buckets, the joint email adresses of the associated persons of each bucket will be disjoint at any time.

  1. iterate over all persons P

  2. For each email adress of P: determine if there is already a related bucket -> gives you a list B of buckets (which might be empty)

  3. if B is empty (none of the email addresses of P matches any of the previous buckets), create a new bucket containing only this person

  4. if B contains exactly one element, put P into that bucket (and extend the email adress list of the bucket accordingly)

  5. if B contains 2 or more buckets, merge these buckets into one (and extend the email adress list of this new bucket accordingly)

So what remains is to pick some efficient data structures which support the required operations:

  • each bucket needs to hold a set of persons -> a list of persons for each bucket will do it

  • efficient adding of persons to a bucket and merging of buckets -> a list is still fine

  • efficient lookup of buckets by email: that means you need an additional dictionary D which maps email -> bucket.

The latter one can be efficiently updated when a new bucket is added, when a bucket gets additional email addresses or when two buckets will be merged (which means the email adresses in the dictionary will need to be remapped to the newly created merged bucket).

To finally retrieve all the found buckets, you can either do some bookkeeping during the process about the newly created buckets and the ones which were deleted during a merge (some additional hashset for all valid buckets will do the trick), or you can iterate over all values of that dictionary and remove the duplicate buckets (see some standard Java solutions here).

The above sketch can be made even more efficient by utilizing a so-called "disjoint-set data structure" instead of a list of persons for each bucket, but to my experience for many practical applications a list is sufficient.

  • Thanks for the answer, Doc! The algorithm has certainly given me some insight. I'll probably go with this solution thanks to it's simplicity! By the way, what's "book-keeping"? – Javier García Manzano Mar 19 '18 at 7:04
  • Furthermore, I'm trying to understand why a disjoint-set would make it more efficient. – Javier García Manzano Mar 19 '18 at 7:23
  • Another problem I've encountered while implementing this algorithm is that once I have my final data structure, it would have two buckets, one with the first and second contact and another with the second and last (prntscr.com/it773n), while the ideal would be to have all three contacts in the same bucket. Am I understanding it wrong? – Javier García Manzano Mar 19 '18 at 10:16
  • @JavierGarcíaManzano: bookkeeping means here: recording which buckets are created and deleted during the process. This can be done by a hashset which is updated in steps 3 and 5 of the algorithm accordingly. – Doc Brown Mar 19 '18 at 18:09
  • @JavierGarcíaManzano: if you got two buckets, there is a bug in your implementation. The algo should create the bucket for person 1. Then for person 2, there is one matching email address, so it should find that bucket. This leads to step 4: person 2 is put into the existing bucket, and the new mail adress "three@email.com" is added to the dictionary pointing to that bucket. Finally, person 3 is processed: the email adress exists, points to the bucket, so step 4 again. Use a debugger and check where this fails. – Doc Brown Mar 19 '18 at 18:16
3

A(nother) way to approach this problem is to recognize it as equivalent to finding connected components in a graph.

One way to construct a relevant (bipartite) graph is considering as nodes "people" (e.g. Person 1, Person 2,...) and as another set of nodes all the (unique) email addresses. An edge between the nodes exists when a "person" has a given email address. Once the graph is drawn, the bucketing/merging problem is equivalent to finding the connected components of the graph, which can be done e.g using depth-first search.

For a very similar problem see e.g. https://stackoverflow.com/questions/42036188/merging-tuples-if-they-have-one-common-element for some Python solutions (tuples there are your lists of emails).

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.