Alternative to spherical K-Means for clustering large high dimensional dataset

Question

What are some alternatives to Spherical K-Means for clustering very large datasets of high dimension?

I'm looking for something that will be fast even on large datasets, and preferably will not require you to specify the number of clusters to find.

Another property that would be nice (I'm not quite sure the name of it) is that the algorithm can calculate the clusters of a dataset A, and then later find the best cluster for a new point b which wasn't in A, without having to recalculate the clustering.

Answer 1

Depending on size of data set, you can try the algorithms in the Mining of Massive Data Sets book, BFR (variant of k-means), Cure, GRGPF, in case they have better off-the-shelf implementations.