Database Paper Browser

Back to papers

Scalable K-Means++

Summary: Introduces k-means||, a parallel init for k-means++ that reduces startup passes to a logarithmic number. Proves near-optimality after O(log k) rounds; in practice a constant number of passes suffices, with experiments showing k-means|| outperforms k-means++ in both sequential and parallel modes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
10507
Venue
VLDB
Year
2012
Pagerank
9.4341455e-05
Overall Rank
2,146 | 85.09%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
2,164 Elastic Machine Learning Algorithms in Amazon SageMaker 2020 SIGMOD 9.3953268e-05
2,660 Vertica-ML: Distributed Machine Learning in Vertica Database 2020 SIGMOD 8.3614044e-05
6,000 A New Sparse Data Clustering Method Based On Frequent Items 2023 SIGMOD 5.2365238e-05
6,745 On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection 2021 VLDB 4.9376468e-05
7,268 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 4.7769096e-05
8,512 Marigold: Efficient k-means Clustering in High Dimensions 2023 VLDB 4.4904708e-05
8,923 LOG-Means: Efficiently Estimating the Number of Clusters in Large Datasets 2020 VLDB 4.4229886e-05
9,426 Local Search Methods for k-Means with Outliers 2017 VLDB 4.3399748e-05
10,928 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.1905499e-05
11,342 Scalable Time Series Compound Infrastructure 2022 SIGMOD 4.1905499e-05
11,469 Fast Density-Peaks Clustering: Multicore-based Parallelization Approach 2021 SIGMOD 4.1905499e-05
11,650 CATAPULT: Data-driven Selection of Canned Patterns for Efficient Visual Graph Query Formulation 2019 SIGMOD 4.1905499e-05
11,968 ALID: Scalable Dominant Cluster Detection 2015 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
33 BIRCH: An Efficient Data Clustering Method for Very Large Databases 1996 SIGMOD 0.00077399244
340 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00026854084
645 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018727714
875 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00015679931
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
11,469 Fast Density-Peaks Clustering: Multicore-based Parallelization Approach 2021 SIGMOD 4.1905499e-05
5,417 Theoretically-Efficient and Practical Parallel DBSCAN 2020 SIGMOD 5.5162242e-05
11,860 K-means Split Revisited: Well-grounded Approach and Experimental Evaluation 2016 SIGMOD 4.1905499e-05
10,329 Highly-Efficient Large-Scale k-means with Individual Fairness 2026 VLDB 4.1905499e-05
10,974 Settling Time vs. Accuracy Tradeoffs for Clustering Big Data 2024 SIGMOD 4.1905499e-05
12,580 k-Means Projective Clustering 2004 PODS 4.1905499e-05
9,426 Local Search Methods for k-Means with Outliers 2017 VLDB 4.3399748e-05
4,077 Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially 2019 VLDB 6.4634641e-05
6,745 On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection 2021 VLDB 4.9376468e-05
10,946 Efficient Algorithm for K-Multiple-Means 2024 SIGMOD 4.1905499e-05