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,162 | k-Nearest Neighbors in Uncertain Graphs | 2010 | VLDB | 0.0001358105 |
| 3,505 | Consensus Answers for Queries over Probabilistic Databases | 2009 | PODS | 7.0337815e-05 |
| 6,019 | Uncertain Centroid based Partitional Clustering of Uncertain Data | 2012 | VLDB | 5.2415551e-05 |
| 9,135 | Sage: A System for Uncertain Network Analysis | 2022 | VLDB | 4.3888791e-05 |
| 12,299 | Exceeding Expectations and Clustering Uncertain Data | 2009 | PODS | 4.1945683e-05 |
| 12,311 | Large-Scale Uncertainty Management Systems: Learning and Exploiting Your Data (Tutorial Summary) | 2009 | SIGMOD | 4.1945683e-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.00077324389 |
| 101 | ULDBs: Databases with Uncertainty and Lineage | 2006 | VLDB | 0.0004955674 |
| 341 | CURE: An Efficient Clustering Algorithm for Large Databases | 1998 | SIGMOD | 0.00026810548 |
| 3,041 | Sketching Probabilistic Data Streams | 2007 | SIGMOD | 7.6697078e-05 |
| 3,385 | Estimating Statistical Aggregates on Probabilistic Data Streams | 2007 | PODS | 7.1580391e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,808 | A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries | 2001 | SIGMOD | 8.0870741e-05 |
| 7,633 | Mining Frequent Itemsets over Uncertain Databases | 2012 | VLDB | 4.6914549e-05 |
| 10,923 | k-Clustering with Comparison and Distance Oracles | 2024 | PODS | 4.1945683e-05 |
| 1,542 | Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases | 2008 | VLDB | 0.00011456321 |
| 10,003 | Clustering with Set Outliers and Applications in Relational Clustering | 2026 | PODS | 4.1945683e-05 |
| 10,924 | Improved Approximation Algorithms for Relational Clustering | 2024 | PODS | 4.1945683e-05 |
| 6,545 | Clustering Uncertain Graphs | 2018 | VLDB | 5.0193115e-05 |
| 3,636 | Efficient and Effective Algorithms for Clustering Uncertain Graphs | 2019 | VLDB | 6.8976555e-05 |
| 12,299 | Exceeding Expectations and Clustering Uncertain Data | 2009 | PODS | 4.1945683e-05 |
| 6,019 | Uncertain Centroid based Partitional Clustering of Uncertain Data | 2012 | VLDB | 5.2415551e-05 |