4 ms·

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 (

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

schlupa 5y ago
That's similar to what I do on our translation memory at the Commission. The issue we have is that we search for sentences, not words and the medium length of sentences in the database is around 120 characters and we have around 1.5 billion sentences in the database. A pairwise Levenshtein would be completely impossible as added to that we have to take care of replaceables in the segments (dates, numbers, months, weekdays, etc). To accelerate the search we use fuzzy keys which are trigram counts based and have them organized in a ternary tree. For the fuzzy distance, a simple difference calculation between 2 fuzzy keys is close enough to Levenhstein distance that we don't need more fancy metrics (for short sentences it is relatively bad but short sentences are mostly irrelevant for translation memories). Our fuzzy index reduces our search space for the Levenshtein distance calculation by 4 to 5 order of magnitudes (a sentence search is done on a space of 100K-300K sentences, after filtering the number of candidates rarely go beyond 100).
- CornCobs 5y ago
  Interesting! What I noticed when approaching the problem was that there is quite little information on scaling up. I also don't think there are good out-of-the-box solutions covering a wide range of use cases. Dedup (basically cross-product) and linkage (highly dependent on the relative sizes of your search set and backing data) have very different optimizations when your data is large

schlupa 5y ago

That's similar to what I do on our translation memory at the Commission. The issue we have is that we search for sentences, not words and the medium length of sentences in the database is around 120 characters and we have around 1.5 billion sentences in the database. A pairwise Levenshtein would be completely impossible as added to that we have to take care of replaceables in the segments (dates, numbers, months, weekdays, etc). To accelerate the search we use fuzzy keys which are trigram counts based and have them organized in a ternary tree. For the fuzzy distance, a simple difference calculation between 2 fuzzy keys is close enough to Levenhstein distance that we don't need more fancy metrics (for short sentences it is relatively bad but short sentences are mostly irrelevant for translation memories). Our fuzzy index reduces our search space for the Levenshtein distance calculation by 4 to 5 order of magnitudes (a sentence search is done on a space of 100K-300K sentences, after filtering the number of candidates rarely go beyond 100).

CornCobs 5y ago
Interesting! What I noticed when approaching the problem was that there is quite little information on scaling up. I also don't think there are good out-of-the-box solutions covering a wide range of use cases. Dedup (basically cross-product) and linkage (highly dependent on the relative sizes of your search set and backing data) have very different optimizations when your data is large