Approximation Algorithms for Clustering Uncertain Data

Summary: Defines assigned vs unassigned models for clustering uncertain points and reduces uncertain k-means/k-median to weighted deterministic instances. Gives first approximation algorithms for uncertain k-center: O(k/ε · log^2 n) centers for (1+ε) and 2k centers for constant-factor. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hc290700e77ef8a57
Venue: PODS
Year: 2008
Pagerank: 8.6376033e-05
Overall Rank: 2,319 | 84.46%
DOI: 10.1145/1376916.1376944

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (AT&T)
2. Andrew McGregor (University of California San Diego)

BibTeX Citation

@inproceedings{cormode_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{Approximation Algorithms for Clustering Uncertain Data}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376944},
        doi = {10.1145/1376916.1376944},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cormode, Graham and McGregor, Andrew},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,069	k-Nearest Neighbors in Uncertain Graphs	2010	VLDB	0.00012164865
3,553	Consensus Answers for Queries over Probabilistic Databases	2009	PODS	7.188315e-05
6,972	Exceeding Expectations and Clustering Uncertain Data	2009	PODS	5.6150492e-05
7,139	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB	5.580601e-05
8,932	Improvements on the k-center Problem for Uncertain Data	2018	PODS	5.2361195e-05
9,491	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1549931e-05
12,844	Large-Scale Uncertainty Management Systems: Learning and Exploiting Your Data (Tutorial Summary)	2009	SIGMOD	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
32	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00049559562
85	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00035848027
364	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00019916561
2,749	Sketching Probabilistic Data Streams	2007	SIGMOD	8.0426455e-05
3,049	Estimating Statistical Aggregates on Probabilistic Data Streams	2007	PODS	7.6987705e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,460	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS
2	11,549	k-Clustering with Comparison and Distance Oracles	2024	PODS
3	1,641	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
4	10,471	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS
5	11,550	Improved Approximation Algorithms for Relational Clustering	2024	PODS
6	6,489	Clustering Uncertain Graphs	2018	VLDB
7	3,644	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
8	8,932	Improvements on the k-center Problem for Uncertain Data	2018	PODS
9	6,972	Exceeding Expectations and Clustering Uncertain Data	2009	PODS
10	7,139	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB