0
$\begingroup$

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.

Thank you in advance!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Pseudonym ♦
    Commented Jan 30, 2019 at 1:04
  • $\begingroup$ 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. $\endgroup$
    – James Smith
    Commented Jan 30, 2019 at 1:10
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jan 30, 2019 at 18:22

1 Answer 1

Reset to default
1
$\begingroup$

There are many possible approaches. One approach that I would suggest investigating is finding all pairs of similar strings, and then applying a standard algorithm for clustering of sparse graphs. There are multiple possible approaches for finding similar strings, depending on how you plan to measure similarity.

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.

Alternatively, if you want to measure similarity using the number of characters the differ (i.e., like the edit distance but with only the "replace" operation and without the "insert" or "delete" operations), you could look at locality sensitive hashing as a way to find all pairs of similar strings.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I'm not quite sure why locality-sensitive hashing would be a better solution than just using Levenshtein to find similar strings and can you explain to me why you would apply a clustering algorithm after LSH. LSH already puts similar strings in the same bucket/cluster. $\endgroup$
    – James Smith
    Commented Jan 30, 2019 at 0:55
  • $\begingroup$ 10 million strings isn't that much. If Levenshtein was your metric, a ternary search tree would probably do the job for finding neighbours. $\endgroup$
    – Pseudonym ♦
    Commented Jan 30, 2019 at 1:08
  • $\begingroup$ You might be right about that. But I'm looking for a solution that can handle a lot more strings than that. Perhaps a billion. $\endgroup$
    – James Smith
    Commented Jan 30, 2019 at 1:15
  • $\begingroup$ Besides that - a ternary tree will not make me able to cluster the dataset.. :-) $\endgroup$
    – James Smith
    Commented Jan 30, 2019 at 1:33
  • $\begingroup$ @JamesSmith, the main benefit it has is that it spares you from having to do 10 million * 10 million (= 100 trillion) edit distance computations. But Pseudonym is right that a ternary search tree might be even better. $\endgroup$
    – D.W. ♦
    Commented Jan 30, 2019 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.