Yea pairwise string matching for problems like record linkage is O(n^2) and is really infeasible for larger data.

I once had to deal with a problem like this (matching business entity names against a large database) and ended up preprocessing the names into vectors of trigram (3-letter groups) counts, performing TF-IDF on the trigrams and then taking cosine similarity (which is simply matrix multiplication which though O(mnp) is much faster)

The new solution also gave speedups in the 1000-2000x ballpark and had some nice properties:

1. Inverse document frequency naturally filtered out less important "mispellings" (e.g. PTE LTD vs PRIVATE LIMITED) 2. Trigrams maintain order within words but are less concerned about order between words, which happened to matter less in names