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: 11570
Venue: VLDB
Year: 2017
Pagerank: 4.3441378e-05
Overall Rank: 9,420 | 34.47%
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,466	Fast Density-Peaks Clustering: Multicore-based Parallelization Approach	2021	SIGMOD	4.1945683e-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
161	LOF: Identifying Density-Based Local Outliers	2000	SIGMOD	0.00039846974
341	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026810548
701	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017938417
774	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016865771
1,372	SQLEM: Fast Clustering in SQL using the EM Algorithm	2000	SIGMOD	0.00012318334
2,093	Scalable K-Means++	2012	VLDB	9.5588104e-05
2,822	Finding Intensional Knowledge of Distance-Based Outliers	1999	VLDB	8.0608136e-05
4,552	Outlier Detection for High Dimensional Data	2001	SIGMOD	6.0922282e-05
5,760	Outlier-robust Clustering using Independent Components	2008	SIGMOD	5.3382727e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,480	Towards Metric DBSCAN: Exact, Approximate, and Streaming Algorithms	2024	SIGMOD	4.7180617e-05
5,760	Outlier-robust Clustering using Independent Components	2008	SIGMOD	5.3382727e-05
4,652	On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection	2021	VLDB	6.0228549e-05
12,571	k-Means Projective Clustering	2004	PODS	4.1945683e-05
774	Algorithms for Mining Distance-Based Outliers in Large Datasets	1998	VLDB	0.00016865771
701	Efficient Algorithms for Mining Outliers from Large Data Sets	2000	SIGMOD	0.00017938417
10,003	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	4.1945683e-05
9,787	Distance-Based Outlier Detection: Consolidation and Renewed Bearing	2010	VLDB	4.2823546e-05
4,083	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.4638932e-05
9,924	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	4.2544238e-05