k-Clustering with Comparison and Distance Oracles
Summary: Clustering with oracle access (quadruplet and distance) when full data is unavailable. Constant-approx for k-center/k-median/k-means via O(nk) quadruplet and O(k^2) distance calls under adversarial/probabilistic noise; quadruplet-only sublinear-approx impossible for k-median/k-means; low-dimension gains with extra distance queries. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 341 | CURE: An Efficient Clustering Algorithm for Large Databases | 1998 | SIGMOD | 0.00026810548 |
| 859 | So Who Won? Dynamic Max Discovery with the Crowd | 2012 | SIGMOD | 0.00015870894 |
| 4,083 | Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially | 2019 | VLDB | 6.4638932e-05 |
| 4,918 | Top-k Sorting Under Partial Order Information | 2018 | SIGMOD | 5.8282325e-05 |
| 5,029 | Crowdsourced Top-k Queries by Confidence-Aware Pairwise Judgments | 2017 | SIGMOD | 5.7502622e-05 |
| 8,585 | Robust Entity Resolution using Random Graphs | 2018 | SIGMOD | 4.4905755e-05 |
| 9,683 | Hierarchical Entity Resolution using an Oracle | 2022 | SIGMOD | 4.3047774e-05 |
| 9,684 | How to Design Robust Algorithms using Noisy Comparison Oracle | 2021 | VLDB | 4.3047774e-05 |
Previous
Page 1 / 1
Next