How to efficiently iterate a supervised model over the Cartesian product of very large number of records?

Question

The problem:

Two large databases, with ~1M records each, "old customer data" and "new customer data". The data came from different sources and was ingested at different times, so there are many duplicates, but the duplicates might not be exact matches. For example In the old data, the customer was listed as "Michael Smith" but in the new data, they were listed as "Mike Smith" or "M. Smith", or the names match, but the address field is different: How do we now if it is different people with the same name or the same person who changed address?

Approach:

It seems possible to use a supervised learning approach to classify a pair of records as either being duplicates or not.

Question:

Assuming such a model is possible and we have trained it, how would we iterate over the entire data set to produce our predictions?

To apply a supervised approach (or any ML/Probabilistic approach), I can only think of naively examining each pair of records one-by-one, but this means our models would have to iterate through $10^{12}$ records, which doesn't seem feasible even with advanced compute capabilities?

How can one efficiently iterate/search through the combined data set in a situation like this?

Answer 1

This problem is called record linkage and there are methods to avoid iterating the whole cartesian product. The main method I know was called "blocking" and consists in doing a first "rough" pass to create groups of matching candidates (the "blocks"). For example you can create groups which contain at least X n-grams in common. This can be done through one linear iteration through all the entities, storing them in every applicable bin based on their n-grams (an entity can be stored in several bins). I assume that some kind of clustering could also be used to generate the groups of similar entities. Then you end up with multiple groups of smaller size, and you run the cartesian product comparison on every group individually. This can greatly reduce the complexity.

note: I was working on this maybe 10 years ago so there might be more recent approaches.