k-Means Projective Clustering

Summary: Propose a new projective-clustering objective that explicitly trades off subspace dimension vs clustering/reconstruction error, enabling automatic per-cluster dimension selection. Extend k-means to arbitrary subspaces with local-minima-avoidance heuristics; empirically outperforms prior methods. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1317
Venue: PODS
Year: 2004
Pagerank: 5.093636e-05
Overall Rank: 12,764 | 12.43%
DOI: 10.1145/1055558.1055581

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Pankaj K. Agarwal (Duke University)
2. Nabil H. Mustafa (Duke University)

BibTeX Citation

@inproceedings{agarwal_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{k-Means Projective Clustering}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055581},
        doi = {10.1145/1055558.1055581},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Agarwal, Pankaj K. and Mustafa, Nabil H.},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
88	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00035240327
304	Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications	1998	SIGMOD	0.00021917388
351	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00020424271
1,602	Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces	2000	VLDB	0.00010239526
1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD	0.00010128564
1,833	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD	9.6566846e-05
2,158	What is the nearest neighbor in high dimensional spaces?	2000	VLDB	9.0622995e-05
3,550	A Monte Carlo Algorithm for Fast Projective Clustering	2002	SIGMOD	7.3200789e-05
3,663	Optimal Grid-Clustering: Towards Breaking the Curse of Dimensionality in High-Dimensional Clustering	1999	VLDB	7.2151113e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,602	Marigold: Efficient k-means Clustering in High Dimensions	2023	VLDB
2	5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS
3	11,161	Efficient Algorithm for K-Multiple-Means	2024	SIGMOD
4	12,602	Detecting Clusters in Moderate-to-High Dimensional Data: Subspace Clustering, Pattern-based Clustering, and Correlation Clustering	2008	VLDB
5	12,572	Constrained Locally Weighted Clustering	2008	VLDB
6	9,575	Local Search Methods for k-Means with Outliers	2017	VLDB
7	8,751	Advancing Data Clustering via Projective Clustering Ensembles	2011	SIGMOD
8	1,646	Fast Algorithms for Projected Clustering	1999	SIGMOD
9	8,778	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB
10	1,833	Finding Generalized Projected Clusters in High Dimensional Spaces	2000	SIGMOD