Coresets for Clustering Using Noisy Comparisons and Few Distance Queries

Coresets are a fundamental tool for scaling clustering algorithms, but standard constructions assume full access to the pairwise distances. In many modern settings, access to distances is costly and thus limited, and algorithms must instead rely on inexpensive comparison queries. We study coreset construction in the Rank-Measure (RM) model, where the algorithm can make noisy comparison queries to a quadruplet oracle alongside a small number of distance queries. In this model, we present the first algorithm to construct an $\epsilon$-coreset for $(k,z)$-clustering in Euclidean space. It matches the coreset-size bounds known in the classical model, while using only polylogarithmically many distance queries in the input size. Our approach is based on a uniform-sampling framework [Chen, SICOMP 2009], which decomposes the input into geometric rings and samples uniformly within each ring. We implement this approach using primarily noisy comparison queries, and then compress the result using a standard full-access coreset construction. In contrast, prior work in oracle-based clustering achieved only constant-factor guarantees. We complement our theoretical findings with experiments that demonstrate strong empirical performance against full-access baselines while using significantly fewer distance computations.