Local Search Methods for k-Means with Outliers

Summary: Proposes a simple local-search algorithm for k-means with outliers, delivering constant-factor guarantees for the inlier clustering. When paired with sketching techniques, it scales to large data and empirically dominates recent heuristics on synthetic and real-world benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11571
Venue: VLDB
Year: 2017
Pagerank: 4.3399748e-05
Overall Rank: 9,426 | 34.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,469	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1905499e-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
159	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00040135453
340	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026854084
697	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017964755
768	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016864875
1,375	SQLEM: Fast Clustering in SQL using the EM Algorithm	2000	SIGMOD	0.00012321024
2,146	Scalable K-Means++	2012	VLDB	9.4341455e-05
2,826	Finding Intensional Knowledge of Distance-Based Outliers	1999	VLDB	8.0562807e-05
4,549	Outlier Detection for High Dimensional Data	2001	SIGMOD	6.0866685e-05
5,768	Outlier-robust Clustering using Independent Components	2008	SIGMOD	5.3332593e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,479	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7135369e-05
5,768	Outlier-robust Clustering using Independent Components	2008	SIGMOD	5.3332593e-05
6,745	On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection	2021	VLDB	4.9376468e-05
12,580	k-Means Projective Clustering	2004	PODS	4.1905499e-05
768	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016864875
697	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017964755
10,002	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	4.1905499e-05
9,790	Distance-Based Outlier Detection: Consolidation and Renewed Bearing	2010	VLDB	4.2782534e-05
4,077	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.4634641e-05
9,923	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	4.2503475e-05