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
10506
Venue
VLDB
Year
2012
Pagerank
9.5588104e-05
Overall Rank
2,093 | 85.45%
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,163 Elastic Machine Learning Algorithms in Amazon SageMaker 2020 SIGMOD 9.3949234e-05
2,642 Vertica-ML: Distributed Machine Learning in Vertica Database 2020 SIGMOD 8.3851878e-05
4,652 On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection 2021 VLDB 6.0228549e-05
5,996 A New Sparse Data Clustering Method Based On Frequent Items 2023 SIGMOD 5.2415551e-05
6,961 CATAPULT: Data-driven Selection of Canned Patterns for Efficient Visual Graph Query Formulation 2019 SIGMOD 4.8841486e-05
7,271 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 4.7813404e-05
8,670 Marigold: Efficient k-means Clustering in High Dimensions 2023 VLDB 4.4715132e-05
9,053 LOG-Means: Efficiently Estimating the Number of Clusters in Large Datasets 2020 VLDB 4.4039656e-05
9,420 Local Search Methods for k-Means with Outliers 2017 VLDB 4.3441378e-05
10,924 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.1945683e-05
11,340 Scalable Time Series Compound Infrastructure 2022 SIGMOD 4.1945683e-05
11,466 Fast Density-Peaks Clustering: Multicore-based Parallelization Approach 2021 SIGMOD 4.1945683e-05
11,960 ALID: Scalable Dominant Cluster Detection 2015 VLDB 4.1945683e-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.00077324389
341 CURE: An Efficient Clustering Algorithm for Large Databases 1998 SIGMOD 0.00026810548
644 Densest Subgraph in Streaming and MapReduce 2012 VLDB 0.00018748988
886 Fast Personalized PageRank on MapReduce 2011 SIGMOD 0.00015597161
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
11,466 Fast Density-Peaks Clustering: Multicore-based Parallelization Approach 2021 SIGMOD 4.1945683e-05
5,417 Theoretically-Efficient and Practical Parallel DBSCAN 2020 SIGMOD 5.5194222e-05
11,852 K-means Split Revisited: Well-grounded Approach and Experimental Evaluation 2016 SIGMOD 4.1945683e-05
10,317 Highly-Efficient Large-Scale k-means with Individual Fairness 2026 VLDB 4.1945683e-05
10,971 Settling Time vs. Accuracy Tradeoffs for Clustering Big Data 2024 SIGMOD 4.1945683e-05
12,571 k-Means Projective Clustering 2004 PODS 4.1945683e-05
9,420 Local Search Methods for k-Means with Outliers 2017 VLDB 4.3441378e-05
4,083 Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially 2019 VLDB 6.4638932e-05
4,652 On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection 2021 VLDB 6.0228549e-05
10,943 Efficient Algorithm for K-Multiple-Means 2024 SIGMOD 4.1945683e-05