# How to Use K-means for Big Data Clustering?

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 45 references that are in the map.
- First posted on arXiv 14 Apr 2022.

## Builds on (most cited first, 7 of 7)

- [To Cluster, or Not to Cluster: An Analysis of Clusterability Methods](https://mlsanity.com/paper/1808.08317/) (2018)
- [One-Shot Coresets: The Case of k-Clustering](https://mlsanity.com/paper/1711.09649/) (2017)
- [SOS-SDP: an Exact Solver for Minimum Sum-of-Squares Clustering](https://mlsanity.com/paper/2104.11542/) (2021)
- [Improved Guarantees for k-means++ and k-means++ Parallel](https://mlsanity.com/paper/2010.14487/) (2020)
- [HG-means: A scalable hybrid genetic algorithm for minimum sum-of-squares clustering](https://mlsanity.com/paper/1804.09813/) (2018)
- [Qualitative Properties of the Minimum Sum-of-Squares Clustering Problem](https://mlsanity.com/paper/1810.02057/) (2018)
- [A Tabu Search based clustering algorithm and its parallel implementation on Spark](https://mlsanity.com/paper/1702.01396/) (2017)

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

- [Kernel Correlation-Dissimilarity for Multiple Kernel k-Means Clustering](https://mlsanity.com/paper/2403.03448/) (2024)
- [Block-Diagonal Guided DBSCAN Clustering](https://mlsanity.com/paper/2404.01341/) (2024)
- [Granular-Ball-Induced Multiple Kernel K-Means](https://mlsanity.com/paper/2506.18637/) (2025)
- [Superior Parallel Big Data Clustering through Competitive Stochastic Sample Size Optimization in Big-means](https://mlsanity.com/paper/2403.18766/) (2024)
- [Boosting K-means for Big Data by Fusing Data Streaming with Global Optimization](https://mlsanity.com/paper/2410.14548/) (2024)
- [Clust-Splitter - an Efficient Nonsmooth Optimization-Based Algorithm for Clustering Large Datasets](https://mlsanity.com/paper/2505.04389/) (2025)
- [Data-Native Global Optimization for Big Data K-means Clustering](https://mlsanity.com/paper/2607.15835/) (2026)

## Abstract (arXiv)

K-means plays a vital role in data mining and is the simplest and most widely used algorithm under the Euclidean Minimum Sum-of-Squares Clustering (MSSC) model. However, its performance drastically drops when applied to vast amounts of data. Therefore, it is crucial to improve K-means by scaling it to big data using as few of the following computational resources as possible: data, time, and algorithmic ingredients. We propose a new parallel scheme of using K-means and K-means++ algorithms for big data clustering that satisfies the properties of a ``true big data'' algorithm and outperforms the classical and recent state-of-the-art MSSC approaches in terms of solution quality and runtime. The new approach naturally implements global search by decomposing the MSSC problem without using additional metaheuristics. This work shows that data decomposition is the basic approach to solve the big data clustering problem. The empirical success of the new algorithm allowed us to challenge the common belief that more data is required to obtain a good clustering solution. Moreover, the present work questions the established trend that more sophisticated hybrid approaches and algorithms are required to obtain a better clustering solution.