If I invoke KMeans.train by using the random initialization algorithm, I do not observe this problem, even with very large k, like k=5000. This makes me suspect that the kmeans|| in Spark is not properly implemented and do not utilize parallel implementation.
I have also tested my code and data set with Spark 1.3.0, and I still observe this problem. I quickly checked the PR regarding the KMeans algorithm change from 1.2.0 to 1.3.0. It seems to be only code improvement and polish, not changing/improving the algorithm.
I originally worked on Windows 64bit environment, and I also tested on Linux 64bit environment. I could provide the code and data set if anyone want to reproduce this problem.
I hope a Spark developer could comment on this problem and help identifying if it is a bug.