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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,159 | k-Nearest Neighbors in Uncertain Graphs | 2010 | VLDB | 0.00013584223 |
| 3,509 | Consensus Answers for Queries over Probabilistic Databases | 2009 | PODS | 7.0283775e-05 |
| 6,023 | Uncertain Centroid based Partitional Clustering of Uncertain Data | 2012 | VLDB | 5.2365238e-05 |
| 9,135 | Sage: A System for Uncertain Network Analysis | 2022 | VLDB | 4.3846727e-05 |
| 12,307 | Exceeding Expectations and Clustering Uncertain Data | 2009 | PODS | 4.1905499e-05 |
| 12,319 | Large-Scale Uncertainty Management Systems: Learning and Exploiting Your Data (Tutorial Summary) | 2009 | SIGMOD | 4.1905499e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 33 | BIRCH: An Efficient Data Clustering Method for Very Large Databases | 1996 | SIGMOD | 0.00077399244 |
| 103 | ULDBs: Databases with Uncertainty and Lineage | 2006 | VLDB | 0.00049520051 |
| 340 | CURE: An Efficient Clustering Algorithm for Large Databases | 1998 | SIGMOD | 0.00026854084 |
| 3,047 | Sketching Probabilistic Data Streams | 2007 | SIGMOD | 7.6537004e-05 |
| 3,391 | Estimating Statistical Aggregates on Probabilistic Data Streams | 2007 | PODS | 7.1427968e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,813 | A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries | 2001 | SIGMOD | 8.0816314e-05 |
| 7,633 | Mining Frequent Itemsets over Uncertain Databases | 2012 | VLDB | 4.6869557e-05 |
| 10,927 | k-Clustering with Comparison and Distance Oracles | 2024 | PODS | 4.1905499e-05 |
| 1,535 | Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases | 2008 | VLDB | 0.00011461371 |
| 10,002 | Clustering with Set Outliers and Applications in Relational Clustering | 2026 | PODS | 4.1905499e-05 |
| 10,928 | Improved Approximation Algorithms for Relational Clustering | 2024 | PODS | 4.1905499e-05 |
| 6,522 | Clustering Uncertain Graphs | 2018 | VLDB | 5.0230003e-05 |
| 3,622 | Efficient and Effective Algorithms for Clustering Uncertain Graphs | 2019 | VLDB | 6.9021704e-05 |
| 12,307 | Exceeding Expectations and Clustering Uncertain Data | 2009 | PODS | 4.1905499e-05 |
| 6,023 | Uncertain Centroid based Partitional Clustering of Uncertain Data | 2012 | VLDB | 5.2365238e-05 |