I have a 3D point cloud with several million points and I need to partition it into roughly 50k clusters. As the clusters have to be spherical, usually a drawback of k-means, k-means seems pretty appropriate. My problem is that $k$ is too big, thus the runtime is unacceptable. The clusters don't have to be exact, I can tolerate misclassifications quite well.

I found a paper on mini-batch k-means, which might work. And this paper utilizing MapReduce. I also read this and other questions, but question and answers are too vague. This (slide 2) source claims with the use of k-d trees runtime can be reduced from $O(l*K*m*n)$ to $O(m*logm)$, I can't find how that should work?

Is mini-batch k-means the way to go? Is there maybe some simple solution for low dimensional data (3D)?

I would appreciate a C++ implementation, so far I could only find mini batch k-means in scikit which I might translate. Can you recommend any other?

  • 1
    $\begingroup$ The clusters don't have to be exact, I can tolerate misclassifications quite well What does that mean? $\endgroup$
    – ttnphns
    Jun 21, 2018 at 18:35
  • $\begingroup$ I read that mini-batch k-means does have other results that k-means, thus it doesn't actually find perfect classification respecting the given distance metric. I am fine with this. $\endgroup$
    – A1m
    Jun 21, 2018 at 18:37

1 Answer 1


I have seen people use OPTICS on millions of points, but that won't create "spherical" clusters.

Probably something extremely simple like LEADER is what you want.

K-means with large k is pretty problematic. First of all, the runtime scales badly with k, and secondly on noisy data you will have clusters with just one outlier quite often.

For just 3 dimensional data, k-d-trees are definitely worth a try. In particular for large k. However these methods are not easy to implement. You'd need a nearest-neighbor join of two trees (one with the data, one with the centers). That requires some pretty complex data management that is not fun to do, and I don't know any k-d-tree library that would provide this functionality.

Mini-batch k-means won't help you much either. The batch sizes must be much larger than k. Plus, it never converges. So you'd need to run it as long as you can afford and then hope the result is good enough. That is okay for visual-bag-of-words but not for many other cases.


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.