How should I formulate the problem of “binning” many millions of points into thousands of bins?

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?

Thank you.

• A very effective non-ML solution, "MOSS," has been in wide use for two decades: see theory.stanford.edu/~aiken/moss. But since you don't describe what "most similar" really means, and you seem a little unsure, it's unclear whether MOSS solves your problem or not. – whuber Feb 21 '18 at 16:26