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)

Paper ID: 1980
Venue: PODS
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,143 | 23.55%
DOI: 10.1145/3695830

Incoming Non-self Citations Over Time

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

Authors

1. Sainyam Galhotra (Cornell University)
2. Rahul Raychaudhury (Duke University)
3. Stavros Sintos (University of Illinois Chicago)

BibTeX Citation

@inproceedings{galhotra_pods24,
        address = {New York, NY, USA},
        series = {{PODS} '24},
        title = {{k-Clustering with Comparison and Distance Oracles}},
        url = {https://dl.acm.org/doi/10.1145/3695830},
        doi = {10.1145/3695830},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Galhotra, Sainyam and Raychaudhury, Rahul and Sintos, Stavros},
        year = {2024}
}

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
351	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00020424271
743	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014421358
4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB	6.7407122e-05
4,610	Top-k Sorting Under Partial Order Information	2018	SIGMOD	6.6079578e-05
4,821	Crowdsourced Top-k Queries by Confidence-Aware Pairwise Judgments	2017	SIGMOD	6.4935866e-05
5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS	6.2688519e-05
8,592	Robust Entity Resolution using Random Graphs	2018	SIGMOD	5.4058393e-05
8,741	Improvements on the k-center Problem for Uncertain Data	2018	PODS	5.3766157e-05
9,818	Hierarchical Entity Resolution using an Oracle	2022	SIGMOD	5.214913e-05
9,820	How to Design Robust Algorithms using Noisy Comparison Oracle	2021	VLDB	5.214913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,211	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB
2	5,314	Optimal Differentially Private Algorithms for k-Means Clustering	2018	PODS
3	4,366	Solving k-center Clustering (with Outliers) in MapReduce and Streaming, almost as Accurately as Sequentially	2019	VLDB
4	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
5	2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
6	6,345	Clustering Uncertain Graphs	2018	VLDB
7	10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS
8	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
9	8,848	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD
10	9,820	How to Design Robust Algorithms using Noisy Comparison Oracle	2021	VLDB