Clustering a very large number of very small clusters with most data unrelated I'm trying to detect duplicates in a data set of about 34k distinct items. When I say "duplicate," I don't mean identical items, just very similar. I have an algorithm that will Cartesian join the items and return a sparse matrix of similar items with a similarity from 0.0 to 1.0. This matrix has about 5k non-zero entries in it, so it's very sparse.

I already know what the similar items are by pairs. What I need is a good way to cluster them together. I expect there to be many clusters with only 2 items in them, and a couple thousand with more than 2 items, with the vast majority of items being unclustered.

Is there a clustering algorithm that fits this scenario well? I've tried several, but they either give poor results, or are designed with few large clusters in mind instead of many small clusters, and so tend to crash.

Is clustering the wrong approach?

I'm using Spark, but the sparse matrix is small enough that I don't mind exporting to something else if necessary.
At this data size, you can still use hierarchical clustering.

You can stop the clustering early when the similarity is too low.

But all of these approaches are pretty inefficient. The proper approach is to not use clustering at all. Instead, use similarity search or, e.g., minhash.