# A sampling-based approach for efficient clustering in large datasets

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 38 references that are in the map.
- First posted on arXiv 29 Dec 2021.

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

- [Sliced Wasserstein Distance for Learning Gaussian Mixture Models](https://mlsanity.com/paper/1711.05376/) (2017)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences](https://mlsanity.com/paper/1609.00978/) (2016)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [Faster and Sample Near-Optimal Algorithms for Proper Learning Mixtures of Gaussians](https://mlsanity.com/paper/1312.1054/) (2013)
- [An Alternative to EM for Gaussian Mixture Models: Batch and Stochastic Riemannian Optimization](https://mlsanity.com/paper/1706.03267/) (2017)
- [Fast K-Means with Accurate Bounds](https://mlsanity.com/paper/1602.02514/) (2016)
- [k-means as a variational EM approximation of Gaussian mixture models](https://mlsanity.com/paper/1704.04812/) (2017)
- [Large Scale Clustering with Variational EM for Gaussian Mixture Models](https://mlsanity.com/paper/1810.00803/) (2018)
- [MCMC for Normalized Random Measure Mixture Models](https://mlsanity.com/paper/1310.0595/) (2013)
- [Can clustering scale sublinearly with its clusters? A variational EM acceleration of GMMs and k-means](https://mlsanity.com/paper/1711.03431/) (2017)
- [Invertible Particle Flow-based Sequential MCMC with extension to Gaussian Mixture noise models](https://mlsanity.com/paper/1807.02535/) (2018)
- [Truncated Variational EM for Semi-Supervised Neural Simpletrons](https://mlsanity.com/paper/1702.01997/) (2017)
- [Truncated Variational Sampling for "Black Box" Optimization of Generative Models](https://mlsanity.com/paper/1712.08104/) (2017)

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

- [Settling Time vs. Accuracy Tradeoffs for Clustering Big Data](https://mlsanity.com/paper/2404.01936/) (2024)
- [Big Learning Expectation Maximization](https://mlsanity.com/paper/2312.11926/) (2023)
- [GBSK: Skeleton Clustering via Granular-ball Computing and Multi-Sampling for Large-Scale Data](https://mlsanity.com/paper/2509.23742/) (2025)
- [Sublinear Variational Optimization of Gaussian Mixture Models with Millions to Billions of Parameters](https://mlsanity.com/paper/2501.12299/) (2025)

## Abstract (arXiv)

We propose a simple and efficient clustering method for high-dimensional data with a large number of clusters. Our algorithm achieves high-performance by evaluating distances of datapoints with a subset of the cluster centres. Our contribution is substantially more efficient than k-means as it does not require an all to all comparison of data points and clusters. We show that the optimal solutions of our approximation are the same as in the exact solution. However, our approach is considerably more efficient at extracting these clusters compared to the state-of-the-art. We compare our approximation with the exact k-means and alternative approximation approaches on a series of standardised clustering tasks. For the evaluation, we consider the algorithmic complexity, including number of operations to convergence, and the stability of the results.