# Log-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 22 references that are in the map.
- First posted on arXiv 19 Dec 2024.

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

- [SqueezeLLM: Dense-and-Sparse Quantization](https://mlsanity.com/paper/2306.07629/) (2023)
- [Any-Precision LLM: Low-Cost Deployment of Multiple, Different-Sized LLMs](https://mlsanity.com/paper/2402.10517/) (2024)
- [Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D](https://mlsanity.com/paper/1701.07204/) (2017)
- [Noisy, Greedy and Not So Greedy k-means++](https://mlsanity.com/paper/1912.00653/) (2019)
- [Ego Network Structure in Online Social Networks and its Impact on Information Diffusion](https://mlsanity.com/paper/2206.02422/) (2022)

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

- [GuidedQuant: Large Language Model Quantization via Exploiting End Loss Guidance](https://mlsanity.com/paper/2505.07004/) (2025)
- [Q-Palette: Fractional-Bit Quantizers Toward Optimal Bit Allocation for Efficient LLM Deployment](https://mlsanity.com/paper/2509.20214/) (2025)

## Abstract (arXiv)

Clustering is a key task in machine learning, with k-means being widely used for its simplicity and effectiveness. While 1D clustering is common, existing methods often fail to exploit the structure of 1D data, leading to inefficiencies. This thesis introduces optimized algorithms for k-means++ initialization and Lloyd's algorithm, leveraging sorted data, prefix sums, and binary search for improved computational performance. The main contributions are: (1) an optimized k-cluster algorithm achieving O(l · k2 · log n) complexity for greedy k-means++ initialization and O(i · k · log n) for Lloyd's algorithm, where l is the number of greedy k-means++ local trials, and i is the number of Lloyd's algorithm iterations, and (2) a binary search-based two-cluster algorithm, achieving O(log n) runtime with deterministic convergence to a Lloyd's algorithm local minimum. Benchmarks demonstrate over a 4500x speedup compared to scikit-learn for large datasets while maintaining clustering quality measured by within-cluster sum of squares (WCSS). Additionally, the algorithms achieve a 300x speedup in an LLM quantization task, highlighting their utility in emerging applications. This thesis bridges theory and practice for 1D k-means clustering, delivering efficient and sound algorithms implemented in a JIT-optimized open-source Python library.