# Big-Data Clustering: K-Means or K-Indicators?

arXiv: https://arxiv.org/abs/1906.00938 · HTML: https://mlsanity.com/paper/1906.00938/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2019.

## Built on by (most cited first, 1 of 1)

- [Riemannian Difference-of-Convex Optimization for K-Means Clustering](https://mlsanity.com/paper/2609.34310/) (2026)

## Abstract (arXiv)

The K-means algorithm is arguably the most popular data clustering method, commonly applied to processed datasets in some "feature spaces", as is in spectral clustering. Highly sensitive to initializations, however, K-means encounters a scalability bottleneck with respect to the number of clusters K as this number grows in big data applications. In this work, we promote a closely related model called K-indicators model and construct an efficient, semi-convex-relaxation algorithm that requires no randomized initializations. We present extensive empirical results to show advantages of the new algorithm when K is large. In particular, using the new algorithm to start the K-means algorithm, without any replication, can significantly outperform the standard K-means with a large number of currently state-of-the-art random replications.