Web-scale k-means clustering

D. Sculley

article2010WWW1,349 citations

Proposes a mini-batch optimization and fast L1 projection method for k-means clustering that reduces computational cost by orders of magnitude on massive datasets while maintaining solution quality and producing compact, sparse cluster centers.

Listen

Modern web-based systems rely heavily on unsupervised clustering for tasks like grouping search results, aggregating news stories, and detecting near-duplicate content. While classic batch k-means remains the industry standard, its high computational cost makes it too slow for large datasets in user-facing applications that demand sub-second response times. Online stochastic gradient descent offers faster execution but produces significantly lower-quality groupings due to random noise. High dimensionality also creates bulky cluster centers that incur heavy storage and network transfer penalties.

The article demonstrates two enhancements to overcome these scalability barriers: a mini-batch optimization technique for k-means clustering and an efficient approximation method to enforce sparsity in cluster centers. The goal is to dramatically lower processing latency and memory footprints while retaining near-optimal clustering quality.

The author evaluated this approach using the benchmark RCV1 text document collection, training on 781,265 examples and evaluating on 23,149 held-out test documents across different cluster counts. The mini-batch algorithm was compared against standard batch k-means and single-example stochastic gradient descent. Additionally, the author tested an approximate bisection projection against an existing linear-time projection method to assess execution time, non-zero feature counts, and clustering accuracy.

The evaluation revealed three key findings. First, mini-batch k-means converged to near-optimal cluster centers orders of magnitude faster than classic batch k-means, processing nearly one million documents in a fraction of a CPU second on a standard single machine. Second, mini-batch updates significantly outperformed online stochastic gradient descent in solution quality by reducing noise while avoiding the computational overhead of redundant data. Third, the proposed approximate projection method reduced execution time by more than 500-fold compared to full-batch clustering (0.19–0.27 seconds versus 133.96 seconds) and reduced non-zero features from over 200,000 down to roughly 2,500 to 44,000, incurring only a negligible increase in test error.

These results demonstrate that organizations can deploy high-quality, real-time clustering directly in latency-critical web products without expensive distributed computing hardware. The resulting sparsity drastically cuts memory usage and network bandwidth when transmitting cluster models across distributed systems. Operating teams can achieve these benefits using standard commodity servers.

Engineering teams supporting large-scale text or web clustering applications should adopt mini-batch k-means to optimize latency and operational costs. For systems with constrained storage or high network distribution demands, teams should implement projected gradient descent using the approximate bisection method. System architects can tune the batch size and sparsity parameters depending on whether their primary constraint is training speed or absolute cluster fidelity.

The findings are demonstrated on text categorization data and may vary with data modalities exhibiting different distribution characteristics. While confidence in the performance gains is high due to consistent experimental results and open-source availability, organizations should run initial pilot benchmarks on their specific domain data before full production deployment.

Google http k-means clustering algorithm optimization web-scale k-means clustering mini-batch optimization sparse cluster centers

Sculley (2010).pdf

Paper: Efficient projections onto the l1-ball for learning in high dimensions, John C. Duchi et al. (2008). It develops the efficient L1-ball projection algorithm and projected gradient framework that the source adopts directly to enforce centroid sparsity in high dimensions.
Paper: An Efficient k-Means Clustering Algorithm: Analysis and Implementation, Tapas Kanungo et al. (2002). It establishes the foundational algorithmic and computational benchmarks for accelerating Lloyd's classic k-means clustering on large datasets.
Paper: Refining Initial Points for K-Means Clustering, P. Bradley et al. (1998). It provides foundational sub-sampling strategies for k-means initialization to prevent convergence to poor local minima.
Paper: A Framework for Clustering Evolving Data Streams, Charu C. Aggarwal et al. (2003). It introduces stream-based statistical maintenance mechanisms that motivate the online and mini-batch centroid updates used in modern scalable clustering.

Paper: MLlib: Machine Learning in Apache Spark, Xiangrui Meng et al. (2015). It incorporates and scales streaming mini-batch k-means algorithms natively within Apache Spark's distributed machine learning library.
Paper: Scaling distributed machine learning with the parameter server, Mu Li et al. (2014). It presents a distributed parameter server architecture designed to scale large asynchronous mini-batch and stochastic gradient optimizations across industrial clusters.
Paper: Unsupervised Deep Embedding for Clustering Analysis, Junyuan Xie et al. (2015). It extends mini-batch stochastic gradient clustering by jointly optimizing deep neural feature representations and centroid assignments.
Paper: Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, John Duchi et al. (2011). It introduces adaptive subgradient methods that advance stochastic optimization and projected gradient routines on high-dimensional sparse data.
Paper: Stop Indexing at Full Precision: Revisiting Clustering for Vector Embeddings, Leonardo Kuffo et al. (2026). It investigates low-precision quantization and dimension pruning to further accelerate scalable k-means clustering for modern web-scale vector embedding indexes.

Abstract

We present two modifications to the popular k-means clustering algorithm to address the extreme requirements for latency, scalability, and sparsity encountered in user-facing web applications. First, we propose the use of mini-batch optimization for k-means clustering. This reduces computation cost by orders of magnitude compared to the classic batch algorithm while yielding significantly better solutions than online stochastic gradient descent. Second, we achieve sparsity with projected gradient descent, and give a fast ϵ-accurate projection onto the L1-ball. Source code is freely available: http://code.google.com/p/sofia-ml

Topics

http k-means clustering algorithm optimization optimization problems projected gradient source codes stochastic stochastic gradient descent ajax adaptive learning rates

Keywords

web-scale k-means clustering mini-batch optimization sparse cluster centers L1 ball projection triangle inequality gradient descent

Categories and Subject Descriptors
General Terms
Keywords
1. CLUSTERING AND THE WEB
2. MINI-BATCH K-MEANS
3. SPARSE CLUSTER CENTERS
4. REFERENCES

Knowls

Knowl 1 — Mini-Batch k-Means Algorithm
algorithm
Mini-Batch $k$ -Means optimizes the standard $k$ -means objective by taking stochastic gradient descent steps over small random subsets of examples rather than single examples or the entire dataset. It tracks per-center sample counts to maintain per-center learning rates, reducing stochastic noise relative to single-sample online stochastic gradient descent while avoiding full batch passes over large datasets.
Input: Number of clusters $k$ , mini-batch size $b$ , iteration limit $t$ , dataset $X \subset \mathbb{R}^m$
Output: Set of cluster centers $C = \{c_1, \dots, c_k\} \subset \mathbb{R}^m$
Initialize each $c \in C$ with an example picked uniformly at random from $X$
Initialize per-center counts $v[c] \leftarrow 0$ for each $c \in C$
for $i = 1$ to $t$ do
     $M \leftarrow$ sample of $b$ examples picked uniformly at random from $X$
    for each $x \in M$ do
         $d[x] \leftarrow \arg\min_{c \in C} \|c - x\|_2$
    end for
    for each $x \in M$ do
         $c \leftarrow d[x]$
         $v[c] \leftarrow v[c] + 1$
         $\eta \leftarrow \frac{1}{v[c]}$
         $c \leftarrow (1 - \eta)c + \eta x$
    end for
end for
return $C$
Nearest-center assignments are cached for the entire mini-batch prior to updating cluster centers to prevent within-batch assignment drift. The per-center learning rate $\eta = \frac{1}{v[c]}$ ensures that each center update corresponds to an exact running average of all data points assigned to that center over the course of training.
Knowl 2 — Fast Approximate L1-Ball Projection (epsilon-L1)
algorithm
The $\epsilon$ -L1 algorithm projects a vector $c \in \mathbb{R}^m$ onto an $L_1$ -ball of radius $\lambda > 0$ within a multiplicative tolerance parameter $\epsilon > 0$ , yielding a projected vector whose $L_1$ norm lies in the interval $[\lambda, \lambda(1 + \epsilon)]$ . It employs bisection search to determine the soft-thresholding parameter $\theta$ .
Input: Vector $c \in \mathbb{R}^m$ , target $L_1$ radius $\lambda > 0$ , tolerance $\epsilon > 0$
Output: Projected sparse vector $c \in \mathbb{R}^m$
if $\|c\|_1 \le \lambda + \epsilon$ then
    return $c$
end if
upper $\leftarrow \|c\|_\infty$
lower $\leftarrow 0$
current $\leftarrow \|c\|_1$
while current $> \lambda(1 + \epsilon)$ or current $< \lambda$ do
     $\theta \leftarrow \frac{\text{upper} + \text{lower}}{2.0}$
    current $\leftarrow \sum_{i: c_i \neq 0} \max(0, |c_i| - \theta)$
    if current $\le \lambda$ then
        upper $\leftarrow \theta$
    else
        lower $\leftarrow \theta$
    end if
end while
for $i = 1$ to $m$ do
     $c_i \leftarrow \text{sign}(c_i) \cdot \max(0, |c_i| - \theta)$
end for
return $c$
Compared to exact linear-time $L_1$ projection methods that require order statistics or sorting, the bisection approach requires only basic sequential array scans and is faster in practical execution due to favorable memory access patterns.
Knowl 3 — Sparse Mini-Batch k-Means via Projected Gradient Descent
model/method
In high-dimensional applications such as document clustering, feature frequencies often follow power-law distributions, causing standard cluster centers to contain many near-zero values for rare terms. Sparse cluster centers reduce storage requirements and network transmission overhead.

Sparse mini-batch $k$ -means incorporates sparsity constraints through projected gradient descent: following each mini-batch gradient step, every cluster center $c \in C$ is projected onto an $L_1$ -ball of radius $\lambda > 0$ :

$c \leftarrow \arg\min_{c' \in \mathbb{R}^m, \|c'\|_1 \le \lambda} \|c' - c\|_2^2$

This projection step can be executed either using an exact linear-time $L_1$ projection algorithm or via the approximate $\epsilon$ -L1 bisection procedure.
Knowl 4 — Empirical Convergence Speed and Quality of Mini-Batch k-Means on RCV1
empirical result
Mini-Batch $k$ -Means with batch size $b = 1000$ was evaluated on the RCV1 text classification benchmark (781,265 training examples and 23,149 test examples) against Lloyd's classic batch $k$ -means algorithm and online stochastic gradient descent (SGD, batch size $b = 1$ ) across cluster counts $k \in \{3, 10, 50\}$ , initialized with identical random seeds.
1. Computation Speed: Mini-Batch $k$ -Means converged several orders of magnitude faster than full batch $k$ -means, computing high-quality cluster centers for nearly one million documents in a fraction of a CPU second on a standard 2.4 GHz processor. It also executed multiple times faster than batch $k$ -means accelerated via triangle inequalities.
2. Clustering Quality: Mini-Batch $k$ -Means achieved significantly lower test objective error than online single-sample SGD, which suffered from persistent stochastic variance and converged to poorer local optima.

Knowl 5 — Comparison of L1-Constrained Mini-Batch k-Means Methods on RCV1

data/table

Sparse mini-batch $k$ -means was evaluated on the RCV1 dataset (781,265 training examples, 23,149 test examples) with $k = 10$ clusters, mini-batch size $b = 1000$ , $t = 16$ iterations, and projection tolerance $\epsilon = 0.01$ . The table compares unconstrained full batch $k$ -means, mini-batch $k$ -means with exact linear-time $L_1$ -ball projection (LTL1P), and mini-batch $k$ -means with approximate bisection projection ( $\epsilon$ -L1) across two $L_1$ radii $\lambda \in \{5.0, 1.0\}$ :

Method	$\lambda$	# Non-zeros	Test Objective	CPU Seconds
Full batch	–	200,319	0 (baseline)	133.96
LTL1P	5.0	46,446	.004 (.002–.006)	0.51
$\epsilon$ -L1	5.0	44,060	.007 (.005–.008)	0.27
LTL1P	1.0	3,181	.018 (.016–.019)	0.48
$\epsilon$ -L1	1.0	2,547	.028 (.027–.029)	0.19

The test objective column reports fractional error relative to the converged full batch baseline, including the mean and 95% range across trials.

The results show that $L_1$ projection reduces non-zero feature entries by 77% to over 98% with less than 3% degradation in test objective value. Furthermore, the approximate $\epsilon$ -L1 projection runs roughly twice as fast as the exact LTL1P projection algorithm (0.19--0.27 CPU seconds versus 0.48--0.51 CPU seconds) and yields sparser cluster representations.

Coverage note — No substantial contributed material was omitted; all algorithms, methods, and empirical comparisons from the paper are represented.

References

1.L. Bottou and Y. Bengio. Convergence properties of the kmeans algorithm. In Advances in Neural Information Processing Systems. 1995.
2.J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra. Efficient projections onto the $l_1$ -ball for learning in high dimensions. In ICML '08: Proceedings of the 25th international conference on Machine learning, 2008.
3.C. Elkan. Using the triangle inequality to accelerate k-means. In ICML '03: Proceedings of the 20th international conference on Machine learning, 2003.
4.D. D. Lewis, Y. Yang, T. G. Rose, and F. Li. Rcv1: A new benchmark collection for text categorization research. J. Mach. Learn. Res., 5, 2004.
5.D. Witten and R. Tibshirani. A framework for feature selection in clustering. To Appear: Journal of the American Statistical Association, 2010.
6.X. Wu and V. Kumar. The Top Ten Algorithms in Data Mining. Chapman & Hall/CRC, 2009.

Citation

MLA

Sculley, D. “Web-scale K-means Clustering”. Proceedings of the 19th International Conference on World Wide Web, 2010, pp. 1177–78, https://doi.org/10.1145/1772690.1772862.

APA

Sculley, D. (2010). Web-scale k-means clustering. Proceedings of the 19th International Conference on World Wide Web, 1177–1178. https://doi.org/10.1145/1772690.1772862

Chicago

Sculley, D. 2010. “Web-scale K-means Clustering”. Proceedings of the 19th International Conference on World Wide Web, 1177–78. https://doi.org/10.1145/1772690.1772862.

Harvard

Sculley, D. (2010) “Web-scale k-means clustering”, Proceedings of the 19th international conference on World wide web. ACM, pp. 1177–1178. Available at: https://doi.org/10.1145/1772690.1772862.

Vancouver

1. Sculley D (2010) Web-scale k-means clustering. In: Proceedings of the 19th international conference on World wide web. ACM, pp 1177–1178

BibTeX

@inproceedings{Sculley_2010, series={WWW ’10}, title={Web-scale k-means clustering}, url={http://dx.doi.org/10.1145/1772690.1772862}, DOI={10.1145/1772690.1772862}, booktitle={Proceedings of the 19th international conference on World wide web}, publisher={ACM}, author={Sculley, D.}, year={2010}, month=Apr, pages={1177–1178}, collection={WWW ’10} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Web-scale k-means clustering

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Mini-Batch k-Means Algorithm

Knowl 2 — Fast Approximate L1-Ball Projection (epsilon-L1)

Knowl 3 — Sparse Mini-Batch k-Means via Projected Gradient Descent

Knowl 4 — Empirical Convergence Speed and Quality of Mini-Batch k-Means on RCV1

Knowl 5 — Comparison of L1-Constrained Mini-Batch k-Means Methods on RCV1

References

Citation

BibTeX

Access the Paper