# Large-scale string clustering

I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at this scale.

These are the clustering algorithms I've been looking into:

• Affinity propagation:: seems like a good solution, but the memory usage seems way too high, since the data is dense.
• DBSCAN: could also be an option, but I want all nodes/strings to belong to a cluster and not be considered "noise.
• K-medoids: seems like a good option in terms of memory usage, but the computation time seems worrying. It would also be highly preferred if the number of clusters was not determined before running the algorithm as in affinity propagation.

Do you have any ideas on how this problem can be solved? The computation time is not extremely important, as long as the result is satisfiable and it can be done within a couple of days.

• There are as many clustering algorithms as there are clustering problems. In many cases, you can't really pick an algorithm without thinking hard about what your similarity measure is, how you parameterise feature space, and what you expect the clusters to look like in that space. DBSCAN is a case in point, because it's designed for the case where the clusters are not linearly separable in feature space. – Pseudonym Jan 30 '19 at 1:04
• Well, I already know what the similarity metric should/can be. Levensthein or Damerau-levenshtein and this metric can easily be incorporated in the above-mentioned clustering algorithms. – James Smith Jan 30 '19 at 1:10
• In that case, it would be helpful to edit the question to provide that additional context. We'd prefer that you put it in the question, not in the comments, so people don't have to read the comments to understand what you're asking. And we'd prefer that you provide all relevant information up front, so we don't waste our time telling you things you already know and to help us provide answers that are more relevant to your particular situation. – D.W. Jan 30 '19 at 18:22

One approach is to measure similarity using the Levenshtein edit distance. If you have $$N$$ strings, the naive way is to loop over all $$N^2/2$$ pairs, compute the edit distance for each, and save the pairs where the edit distance is below some threshold. However, this doesn't scale when $$N$$ gets large. Another alternative is to use fancier data structures and algorithms to find only the pairs of strings that are similar, e.g., BK-trees, ternary search trees, metric trees, Levenshtein automata, shingling, or other methods. See, e.g., How fast can we identifiy almost-duplicates in a list of strings?, How to speed up process of finding duplicates/similar items in a large amount of strings?, Find all pairs of strings in a set with Levenshtein distance < d, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, and https://cstheory.stackexchange.com/q/4165/5038 for some references. Credits to Pseudonym for part of this suggestion.