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: 12356
Venue: VLDB
Year: 2021
Pagerank: 4.3047774e-05
Overall Rank: 9,684 | 32.64%
DOI: 10.14778/3467861.3467862

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,683	Hierarchical Entity Resolution using an Oracle	2022	SIGMOD	4.3047774e-05
10,091	LLM-Powered Interactive Graph Search: A Scalable and Practical Approach	2026	SIGMOD	4.1945683e-05
10,923	k-Clustering with Comparison and Distance Oracles	2024	PODS	4.1945683e-05
11,443	Approximation Algorithms for Large Scale Data Analysis	2021	PODS	4.1945683e-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
263	CrowdER: Crowdsourcing Entity Resolution	2012	VLDB	0.00029862413
643	Corleone: Hands-Off Crowdsourcing for Entity Matching	2014	SIGMOD	0.00018754451
859	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00015870894
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
1,841	Crowdsourcing Algorithms for Entity Resolution	2014	VLDB	0.00010348858
2,514	Comparative Analysis of Approximate Blocking Techniques for Entity Resolution	2016	VLDB	8.6139012e-05
4,104	Online Entity Resolution Using an Oracle	2016	VLDB	6.4493809e-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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,358	Robust Statistical Analysis on Streaming Data with Near-Duplicates in General Metric Spaces	2025	PODS	4.1945683e-05
5,758	Top-k Nearest Neighbor Search In Uncertain Data Series	2015	VLDB	5.339397e-05
4,090	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4577834e-05
8,693	A Generalized Approach for Reducing Expensive Distance Calls for A Broad Class of Proximity Problems	2021	SIGMOD	4.466142e-05
1,860	Approximation Algorithms for Clustering Uncertain Data	2008	PODS	0.0001028857
10,924	Improved Approximation Algorithms for Relational Clustering	2024	PODS	4.1945683e-05
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
9,924	On Saving Outliers for Better Clustering over Noisy Data	2021	SIGMOD	4.2544238e-05
10,003	Clustering with Set Outliers and Applications in Relational Clustering	2026	PODS	4.1945683e-05
10,923	k-Clustering with Comparison and Distance Oracles	2024	PODS	4.1945683e-05