I'm working on a type of string matching problem. In this problem, I have ~10k strings in set A and ~25 million strings in set B. For each string in set B, I want to find the string in set A which is most similar.
The most naive, non-ML approach: For each string in set A, compare it (via fuzzy distance or edit distance, etc.) to each string in set B, and take the one with the smallest distance. This approach doesn't work for me because it's computationally intractable (even though I'm working on AWS).
I'm sure this is a problem structure that others have dealt with before. One idea I had was to vectorize each string (via TF-IDF, etc.) in set A, and, for each string in set B, compare it's vector (via cosine similarity, etc.) to the vectors in string A.
This, of course, has the same complexity of the naive approach.
Is there a clever ML-based approach (maybe via clustering?) that people have used to solve similar problems?