# Data-Native Global Optimization for Big Data K-means Clustering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 35 references that are in the map.
- First posted on arXiv 17 Jul 2026.

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

- [One-Shot Coresets: The Case of k-Clustering](https://mlsanity.com/paper/1711.09649/) (2017)
- [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)
- [How to Use K-means for Big Data Clustering?](https://mlsanity.com/paper/2204.07485/) (2022)
- [Qualitative Properties of the Minimum Sum-of-Squares Clustering Problem](https://mlsanity.com/paper/1810.02057/) (2018)
- [High-Performance Hybrid Algorithm for Minimum Sum-of-Squares Clustering of Infinitely Tall Data](https://mlsanity.com/paper/2311.04517/) (2023)
- [Variable Landscape Search: A Novel Metaheuristic Paradigm for Unlocking Hidden Dimensions in Global Optimization](https://mlsanity.com/paper/2408.03895/) (2024)
- [Comparative Analysis of Optimization Strategies for K-means Clustering in Big Data Contexts: A Review](https://mlsanity.com/paper/2310.09819/) (2023)
- [Superior Parallel Big Data Clustering through Competitive Stochastic Sample Size Optimization in Big-means](https://mlsanity.com/paper/2403.18766/) (2024)

## Abstract (arXiv)

Big data clustering remains challenging: the Minimum Sum-of-Squares Clustering (MSSC) problem underlying K-means is NP-hard, and existing methods either reach poor local minima or require prohibitive metaheuristic hybrids. We target arbitrarily tall data: a fixed feature space may contain arbitrarily many, possibly infinitely many, observations, while the algorithm accesses only finite random samples. We propose Big-means++, an algorithm achieving scalability and global-search quality by curating inputs to MSSC optimization on big data. It orchestrates local K-means refinements into a data-native global search for big data clustering. Rather than optimizing the full-data MSSC objective, Big-means++ traverses sample-induced surrogate landscapes. Each sample defines a distinct empirical MSSC approximation with a perturbed local-optimum structure, turning sample-to-sample variation into a global-search mechanism. Unlike Big-means, a flowing-incumbent strategy propagates centroid state across empirical landscapes through K-means refinements on fresh samples without rollback to a best-so-far solution. This increases mobility and favors stable, high-quality configurations across approximations of the full-data structure. A new shaking mechanism varies sample size geometrically, broadening the surrogate landscapes explored across resolution scales, accounting for cluster imbalance, and improving solution quality. A competitive multi-agent system asynchronously explores independent sampled landscapes, transforming diverse stochastic trajectories into collective search intelligence. Automatic convergence detection stops each agent after attaining a high-quality solution but before further search risks degrading it, while providing a universal speed-quality control. Experiments on 22 datasets against 11 competing algorithms demonstrate the effectiveness, efficiency, and robustness of Big-means++.