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?