An Efficient k-Means Clustering Algorithm: Analysis and Implementation

By Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, Angela Y. Wu. 2002

5,640 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Optimization & Training, Algorithms & Complexity, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Optimization & Training

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

3D Instance Segmentation of MVS Buildings (2021, methodology): “Many clustering methods are available in the literature, such as Mean-shift [55] and K-means [56], but none of them is suitable for our multi-view scenario.”
Toward optimal fragment generations for ab initio protein structure assembly (2012, methodology): “We use two clustering algorithms, SPICKER42 and k - means,43 to generate the nonredundant (phi, psi) pairs at each position.”
Fair Clustering Through Fairlets (2018, methodology): “To solve the k -median problem we use the single swap algo-rithm due to Arya et al. (2004), which also gets a 5-approximation in the worst case, but performs much better in practice (Kanungo et al. , 2002).”
HELoC: Hierarchical Contrastive Learning of Source Code Representation (2022, methodology): “We use the K-means algorithm (K=104) to cluster the code into 104 clusters, following the settings described in InferCode [4].”
Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations (2006, background): “CVTs are indeed special as they enjoy very natural optimization properties which make them very popular in diverse scientific and engineering applications that include art design, astronomy, clustering, geometric modeling, image and data analysis, resource optimization, quadrature design, sensor net”
DeepSafe: A Data-driven Approach for Checking Adversarial Robustness in Neural Networks (2017, methodology): “Here we focus on a particularly popular clustering algorithm called kMeans [10] (although our approach could be implemented using different clustering algorithms as well).”
Simplifying Mixture Models Through Function Approximation (2006, methodology): “Unnecessary component summations in the model evaluation can then be circumvented by performing a neighborhood search through spatial data structures, such as the kd-trees 1045-9227/$26.00 © 2010 IEEE [25], [31].”
Data mining for yield enhancement in semiconductor manufacturing and an empirical study (2007, background): “Clustering problems arise in many different applications (Kanungo et al., 2002), such as data mining and knowledge discovery, data compression, vector quantization, pattern recognition and pattern classification.”
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering (2018, background): “In addition to the above cited coreset constructions, coresets for k-means in particular have also been studied empirically [1, 3, 25, 27, 33].”
Thirty Years of Machine Learning: The Road to Pareto-Optimal Wireless Networks (2019, background): “One of the popular low-complexity iterative refinement algorithms suitable for K-means clustering is Lloyd’s algorithm [242], which often yields satisfactory performance after a low number of iterations.”
A local search approximation algorithm for k-means clustering (2002, background): “These include the Euclidean k-medians and the Weber problem [3, 25], in which the objective is to minimize the sum of distances to the nearest center, and the Euclidean k-center problem [1], in which the objective is to minimize the maximum distance.”
Comparative Analysis of K-Means and Fuzzy C- Means Algorithms (2013, background): “The time complexity of K-means [15] is O(ncdi) and time complexity of FCM [4] is O(ndc2i).”
A Similarity Measure for Text Classification and Clustering (2014, background): “Such highdimensionality and sparsity can be a severe challenge for similarity measure which is an important operation in text processing algorithms [5], [6], [10], [11], [23], [24], [28], [30], [33], [34], [37], [41], [42], [47], [49], [50].”