# Simple, Scalable and Effective Clustering via One-Dimensional Projections

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 70 references that are in the map.
- First posted on arXiv 25 Oct 2023.

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

- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Dimensionality Reduction for k-Means Clustering and Low Rank Approximation](https://mlsanity.com/paper/1410.6801/) (2014)
- [Approximate Nearest Neighbor Search in High Dimensions](https://mlsanity.com/paper/1806.09823/) (2018)
- [Introduction to Core-sets: an Updated Survey](https://mlsanity.com/paper/2011.09384/) (2020)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms](https://mlsanity.com/paper/1810.05691/) (2018)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [A New Coreset Framework for Clustering](https://mlsanity.com/paper/2104.06133/) (2021)
- [Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension](https://mlsanity.com/paper/1809.02961/) (2018)
- [An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization](https://mlsanity.com/paper/1406.2951/) (2014)
- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [DBSCAN++: Towards fast and scalable density clustering](https://mlsanity.com/paper/1810.13105/) (2018)
- [k-means++: few more steps yield constant approximation](https://mlsanity.com/paper/2002.07784/) (2020)
- [Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics](https://mlsanity.com/paper/1812.08664/) (2018)
- [Local Search Yields a PTAS for k-Means in Doubling Metrics](https://mlsanity.com/paper/1603.08976/) (2016)
- [Fast K-Means with Accurate Bounds](https://mlsanity.com/paper/1602.02514/) (2016)
- [Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics](https://mlsanity.com/paper/1603.09535/) (2016)
- [A Fast Approximation Scheme for Low-Dimensional k-Means](https://mlsanity.com/paper/1708.07381/) (2017)
- [Fast and Accurate k-means++ via Rejection Sampling](https://mlsanity.com/paper/2012.11891/) (2020)
- [A Refined Approximation for Euclidean k-Means](https://mlsanity.com/paper/2107.07358/) (2021)
- [Fast Approximate K-Means via Cluster Closures](https://mlsanity.com/paper/1312.3061/) (2013)
- [An efficient K -means clustering algorithm for massive data](https://mlsanity.com/paper/1801.02949/) (2018)

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

- [Faster and Simpler Greedy Algorithm for k-Median and k-Means](https://mlsanity.com/paper/2407.11217/) (2024)
- [Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph](https://mlsanity.com/paper/2607.08746/) (2026)

## Abstract (arXiv)

Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and k-means++ can take Omega(ndk) time when clustering n points in a d-dimensional space (represented by an n× d matrix X) into k clusters. In applications with moderate to large k, the multiplicative k factor can become very expensive. We introduce a simple randomized clustering algorithm that provably runs in expected time O(nnz(X) + nlog n) for arbitrary k. Here nnz(X) is the total number of non-zero entries in the input dataset X, which is upper bounded by nd and can be significantly smaller for sparse datasets. We prove that our algorithm achieves approximation ratio smashwidetildeO(k4) on any input dataset for the k-means objective. We also believe that our theoretical analysis is of independent interest, as we show that the approximation ratio of a k-means algorithm is approximately preserved under a class of projections and that k-means++ seeding can be implemented in expected O(n log n) time in one dimension. Finally, we show experimentally that our clustering algorithm gives a new tradeoff between running time and cluster quality compared to previous state-of-the-art methods for these tasks.