On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection

Summary: UniK unifies pruning-based accelerations for Lloyd's k-means into an evaluation framework with fine-grained performance breakdown. An optimized UniK-hybrid pruning strategy improves efficiency, with ML-based automatic selection of the best accelerator. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: ha43a427808b8bd76
Venue: VLDB
Year: 2021
Pagerank: 5.5076707e-05
Overall Rank: 7,502 | 49.57%
DOI: 10.14778/3425879.3425887

Incoming Non-self Citations Over Time

Authors

1. Sheng Wang (New York University)
2. Yuan Sun (Royal Melbourne Institute of Technology University)
3. Zhifeng Bao (Royal Melbourne Institute of Technology University)

BibTeX Citation

@article{wang_vldb21,
        title = {{On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection}},
        author = {Wang, Sheng and Sun, Yuan and Bao, Zhifeng},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {2},
        pages = {163--175},
        doi = {10.14778/3425879.3425887},
        url = {https://doi.org/10.14778/3425879.3425887},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,763	Marigold: Efficient k-means Clustering in High Dimensions	2023	VLDB	5.2832228e-05
11,062	Highly-Efficient Large-Scale k-means with Individual Fairness	2026	VLDB	4.9793485e-05
11,346	Federated and Balanced Clustering for High-dimensional Data	2025	VLDB	4.9793485e-05
11,711	Prerequisite-driven Fair Clustering on Heterogeneous Information Networks	2023	SIGMOD	4.9793485e-05
11,734	F3 KM: Federated, Fair, and Fast k-means	2023	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
78	Automatic Database Management System Tuning Through Large-scale Machine Learning	2017	SIGMOD	0.00036684414
437	QTune: A Query-Aware Database Tuning System with Deep Reinforcement Learning	2019	VLDB	0.00018315867
885	Framework for Evaluating Clustering Algorithms in Duplicate Detection	2009	VLDB	0.00013260551
2,128	Scalable K-Means++	2012	VLDB	8.9964096e-05
2,610	NG-DBSCAN: Scalable Density-Based Clustering for Arbitrary Data	2017	VLDB	8.2276558e-05
4,639	Pivot-based Metric Indexing	2017	VLDB	6.4903275e-05
5,011	Fast Large-Scale Trajectory Clustering	2020	VLDB	6.3148258e-05
8,941	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB	5.254732e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,304	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
2	8,941	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB
3	11,492	Improved Approximation Algorithms for Relational Clustering	2024	PODS
4	11,062	Highly-Efficient Large-Scale k-means with Individual Fairness	2026	VLDB
5	13,054	k-Means Projective Clustering	2004	PODS
6	11,527	Settling Time vs. Accuracy Tradeoffs for Clustering Big Data	2024	SIGMOD
7	11,585	Ensemble Clustering based on Meta-Learning and Hyperparameter Optimization	2024	VLDB
8	11,508	Efficient Algorithm for K-Multiple-Means	2024	SIGMOD
9	9,751	Local Search Methods for k-Means with Outliers	2017	VLDB
10	2,128	Scalable K-Means++	2012	VLDB