I am making all pairwise comparisons in a dataset. The use-case is collapsing records into a unique ID based on fuzzy names and dates of birth. The size of the database is around 57,000 individuals. So this is a total of 57,000 choose 2 pairwise combinations. (This is a tiny example I know, but I have other databases with the same problem that are much larger.)

Based on other analysis, I concluded that I do not want to consider people with birthdates of more than three years apart. So I can subset the database into overlapping cohorts, and then only do all pair-wise comparisons within each cohort.

It is easy to show examples of where this cohort approach will reduce the number of pairs I need to compare. Here is one example with my data just based on the quintiles of the year of birth (and those with missing birthdays go into all cohorts).

(Min,1968]  : 13,453
[1962,1980] : 17,335
[1974,1988] : 21,188
[1982,1993] : 21,993
[1987,Max)  : 17,449

Which saves me around 0.7 billion comparisons.

So this brings up two questions:

  • are the choosing the bins based on quantiles a good strategy, or is there anther strategy that works better?
  • how many bins should I make?

There is a better way if I understand your question correctly. Here is the algorithm I propose:

  • Initialize a 'window' list and a 'pairs' list
  • Sort your data on birthday from old to young (or the other way around)
  • Loop over your rows and keep track of all the rows that are still in the last three years since your current row. When you get to a new row, throw out rows that are now more than three years apart, add the current row together with the rows in your 'window' to your pairs set and add current row to your 'window'.

This means you only iterate over your main list once, and if you implement your 'window' list properly (like a linked list for example) you don't need to do a lot of looping in that regard either. You also get all the pairs only once as a by product. Plus you actually get all the pairs, while with your binning approach you get missing pairs around the bin edges (if you don't overlap).

If you use the overlapping binning approach I think you should have bins of 6 years width and the borders shift 3 years each time, that way all true pairs are in at least 1 bin together, and there is the least amount of unwanted pairs.

| improve this answer | |
  • $\begingroup$ Yes that works, thank you. (I did this a few years ago for rollings counts in time.) Definitely is an improvement over what I was doing currently. $\endgroup$ – Andy W Jul 1 '16 at 18:45
  • $\begingroup$ Doing this on my dataset reduces it to around 0.6 billion pairwise comparisons. So in the original it is about 1.6 billion, my bins is around 0.8 billion. (Also my binning approach does not get missing around the edges, because the edges are overlapping.) I think I just got lucky with the bins in my formulation though. Some overly simplified back-of-the-napkin math suggests 5 bins for my data is the optimal. $\endgroup$ – Andy W Jul 1 '16 at 19:26
  • $\begingroup$ If you use the binning approach wouldn't having bin sizes of 6 years be optimal? And then shift them 3 years each. That way all true pairs always share a bin and there is the least unwanted overlap possible. Whatever way you do it, the end result should be the same however so one of your implementations is bugged :) $\endgroup$ – Jan van der Vegt Jul 1 '16 at 19:29
  • $\begingroup$ Is it possible you have duplicate pairs with your binning approach because the pairs appear in two bins due to the overlap? $\endgroup$ – Jan van der Vegt Jul 1 '16 at 19:31
  • 1
    $\begingroup$ Yes my original approach will have redundant calculations, hence why taking it all the way down to simply running bins of 6 years is not optimal. (I'm agreeing that your suggestion is better than my original approach to the problem.) By the time I figure out how to reduce those redundant comparisons I should be left with what your suggestions is anyhow. $\endgroup$ – Andy W Jul 1 '16 at 19:38

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.