How to Design Robust Algorithms using Noisy Comparison Oracle

Summary: Robust max/nearest/farthest search under a noisy comparison oracle; two noise models: adversarial and probabilistic. Derives robust k-center and agglomerative clustering with approximation guarantees; analyzes query complexity, validated on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12544
Venue: VLDB
Year: 2021
Pagerank: 5.214913e-05
Overall Rank: 9,820 | 32.63%
DOI: 10.14778/3467861.3467862

Incoming Non-self Citations Over Time

Authors

1. Raghavendra Addanki (University of Massachusetts Amherst)
2. Sainyam Galhotra (University of Massachusetts Amherst)
3. Barna Saha (University of California Berkeley)

BibTeX Citation

@article{addanki_vldb21,
        title = {{How to Design Robust Algorithms using Noisy Comparison Oracle}},
        author = {Addanki, Raghavendra and Galhotra, Sainyam and Saha, Barna},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {10},
        pages = {1703--1716},
        doi = {10.14778/3467861.3467862},
        url = {https://doi.org/10.14778/3467861.3467862},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,818	Hierarchical Entity Resolution using an Oracle	2022	SIGMOD	5.214913e-05
10,382	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	5.093636e-05
11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS	5.093636e-05
11,641	Approximation Algorithms for Large Scale Data Analysis	2021	PODS	5.093636e-05

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
196	CrowdER: Crowdsourcing Entity Resolution	2012	VLDB	0.00025780596
439	Corleone: Hands-Off Crowdsourcing for Entity Matching	2014	SIGMOD	0.00018464913
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
743	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00014421358
1,443	Crowdsourcing Algorithms for Entity Resolution	2014	VLDB	0.00010773106
2,120	Comparative Analysis of Approximate Blocking Techniques for Entity Resolution	2016	VLDB	9.1406654e-05
3,602	Online Entity Resolution Using an Oracle	2016	VLDB	7.2691521e-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
8,592	Robust Entity Resolution using Random Graphs	2018	SIGMOD	5.4058393e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,244	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB
2	4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS
3	8,848	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD
4	10,151	Coresets for Robust Query Optimization	2026	PODS
5	2,253	Approximation Algorithms for Clustering Uncertain Data	2008	PODS
6	11,144	Improved Approximation Algorithms for Relational Clustering	2024	PODS
7	1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB
8	10,065	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD
9	10,176	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS
10	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS