# How to Design Robust Algorithms using Noisy Comparison Oracle

Raghavendra Addanki  UMass Amherst<EMAIL_ADDRESS>,  Sainyam Galhotra
UMass Amherst<EMAIL_ADDRESS>and  Barna Saha  UC Berkeley
<EMAIL_ADDRESS>
###### Abstract.

Metric based comparison operations such as finding maximum, nearest and
farthest neighbor are fundamental to studying various clustering techniques
such as $k$-center clustering and agglomerative hierarchical clustering. These
techniques crucially rely on accurate estimation of pairwise distance between
records. However, computing exact features of the records, and their pairwise
distances is often challenging, and sometimes not possible. We circumvent this
challenge by leveraging weak supervision in the form of a comparison oracle
that compares the relative distance between the queried points such as ‘Is
point $u$ closer to $v$ or $w$ closer to $x$?’.

However, it is possible that some queries are easier to answer than others
using a comparison oracle. We capture this by introducing two different noise
models called adversarial and probabilistic noise. In this paper, we study
various problems that include finding maximum, nearest/farthest neighbor
search under these noise models. Building upon the techniques we develop for
these comparison operations, we give robust algorithms for $k$-center
clustering and agglomerative hierarchical clustering. We prove that our
algorithms achieve good approximation guarantees with a high probability and
analyze their query complexity. We evaluate the effectiveness and efficiency
of our techniques empirically on various real-world datasets.

PVLDB Reference Format:
Raghavendra Addanki, Sainyam Galhotra, Barna Saha. PVLDB, 14(9): XXX-XXX,
2021. doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-
NC-ND 4.0 International License. Visit
https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this
license. For any use beyond those covered by this license, obtain permission
by emailing<EMAIL_ADDRESS>Copyright is held by the owner/author(s).
Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB
Endowment, Vol. 14, No. 9 ISSN 2150-8097. doi:XX.XX/XXX.XX

##  1\. Introduction

Many real world applications such as data summarization, social network
analysis, facility location crucially rely on metric based comparative
operations such as finding maximum, nearest neighbor search or ranking. As an
example, data summarization aims to identify a small representative subset of
the data where each representative is a summary of similar records in the
dataset. Popular clustering algorithms such as $k$-center clustering and
hierarchical clustering are often used for data summarization
(kleindessner2019fair, ; girdhar2012efficient, ). In this paper, we study
fundamental metric based operations such as finding maximum, nearest neighbor
search, and use the developed techniques to study clustering algorithms such
as $k$-center clustering and agglomerative hierarchical clustering.

Clustering is often regarded as a challenging task especially due to the
absence of domain knowledge, and the final set of clusters identified can be
highly inaccurate and noisy (ben2018, ). It is often hard to compute the exact
features of points and thus pairwise distance computation from these feature
vectors could be highly noisy. This will render the clusters computed based on
objectives such as $k$-center unreliable.

Figure 1. Data summarization example

To address these challenges, there has been a recent interest to leverage
supervision from crowd workers (abstracted as an oracle) which provides
significant improvement in accuracy but at an added cost incurred by human
intervention (verroios2015entity, ; galhotra2018robust, ;
vinayak2016crowdsourced, ). For clustering, the existing literature on oracle
based techniques mostly use _optimal cluster queries_ , that ask questions of
the form ‘do the points u and v belong to the same optimal
cluster?’(ashtiani2016clustering, ; vinayak2016crowdsourced, ;
mazumdar2017clustering, ; emamjomeh2018adaptive, ). The goal is to minimize
the number of queries aka query complexity while ensuring high accuracy of
clustering output. This model is relevant for applications where the oracle
(human expert or a crowd worker) is aware of the optimal clusters such as in
entity resolution (verroios2015entity, ; galhotra2018robust, ). However, in
most applications, the clustering output depends highly on the required number
of clusters and the presence of other records. Without a holistic view of the
entire dataset, answering optimal queries may not be feasible for any
realistic oracle. Let us consider an example data summarization task that
highlights some of the challenges.

###### Example 1.1.

Consider a data summarization task over a collection of images (shown in
Figure 1). The goal is to identify $k$ images (say $k=3$) that summarize the
different locations in the dataset. The images $1,2$ refer to the Eiffel tower
in Paris, $3$ is the Colosseum in Rome, $4$ is the replica of Eiffel tower at
Las Vegas, USA, $5$ is Venice and $6$ is the Leaning tower of Pisa. The ground
truth output in this case would be $\\{\\{1,2\\},\\{3,5,6\\},\\{4\\}\\}$. We
calculated pairwise similarity between images using the visual features
generated from Google Vision API (googlevision, ). The pair $(1,4)$ exhibits
the highest similarity of $0.87$, while all other pairs have similarity lower
than $0.85$. Distance between a pair of images $u$ and $v$, denoted as
$d(u,v)$, is defined as $(1-$similarity between $u$ and $v$). We ran a user
experiment by querying crowd workers to answer simple Yes/No questions to help
summarize the data (Please refer to Section 6.2 for more details).

In this example, we make the following observations.

$\bullet$ Automated clustering techniques generate noisy clusters.:

Consider the greedy approach for $k$-center clustering
(gonzalez1985clustering, ) which sequentially identifies the farthest record
as a new cluster center. In this example, records $1$ and $4$ are placed in
the same cluster by the greedy $k$-center clustering, thereby leading to poor
performance. In general, automated techniques are known to generate erroneous
similarity values between records due to missing information or even presence
of noise (wang2012crowder, ; vesdapunt2014crowdsourcing, ; firmanier, ). Even
Google’s landmark detection API (googlevision, ) did not identify the location
of images $4$ and $5$.

$\bullet$ Answering pairwise optimal cluster query is infeasible.:

Answering whether $1$ and $3$ belong to the same optimal cluster when
presented in isolation is impossible unless the crowd worker is aware of other
records present in the dataset, and the granularity of the optimum clusters.
Using the pair-wise Yes/No answers obtained from the crowd workers for the
${6\choose 2}$ pairs in this example, the identified clusters achieved $0.40$
F-score for $k=3$. Please refer to Section 6.2 for additional details.

$\bullet$ Comparing relative distance between the locations is easy.:

Answering _relative distance_ queries of the form ‘Is $1$ closer to $3$, or is
$5$ closer to $6$?’ does not require any extra knowledge about other records
in the dataset. For the $6$ images in the example, we queried relative
distance queries and the final clusters constructed for $k=3$ achieved an
F-score of $1$.

In summary, we observe that humans have an innate understanding of the domain
knowledge and can answer _relative distance queries_ between records easily.
Motivated by the aforementioned observations, we consider a _quadruplet_
comparison oracle that compares the relative distance between two pairs of
points $(u_{1},u_{2})$ and $(v_{1},v_{2})$ and outputs the pair with smaller
distance between them breaking ties arbitrarily. Such oracle models have been
studied extensively in the literature (ilvento2019metric, ;
emamjomeh2018adaptive, ; chatziafratis2018hierarchical, ;
ghoshdastidar2019foundations, ; ukkonen2017crowdsourced, ;
tamuz2011adaptively, ; hopkins2020noise, ). Even though quadruplet queries are
easier than binary optimal queries, some oracle queries maybe harder than the
rest. In a comparison query, if there is a significant gap between the two
distances being compared, then such queries are easier to answer (DKMR15, ;
braverman2008noisy, ). However, when the two distances are close, the chances
of an error could increase. For example, ‘Is location in image $1$ closer to
$3$, or $2$ is closer to $6$?’ maybe difficult to answer.

To capture noise in quadruplet comparison oracle answers, we consider two
noise models. In the first noise model, when the pairwise distances are
comparable, the oracle can return the pair of points that are farther instead
of closer. Moreover, we assume that the oracle has access to all previous
queries and can answer queries by acting adversarially. More formally, there
is a parameter $\mu>0$ such that if
$\frac{\max{d(u_{1},u_{2}),d(v_{1},v_{2})}}{\min{d(u_{1},u_{2}),d(v_{1},v_{2})}}\leq(1+\mu)$,
then adversarial error may occur, otherwise the answers are correct. We call
this the "Adversarial Noise Model". In the second noise model called
"Probabilistic Noise Model", given a pair of distances, we assume that the
oracle answers correctly with a probability of $1-p$ for some fixed constant
$p<\frac{1}{2}$. We consider a persistent probabilistic noise model, where our
oracle answers are _persistent_ , i.e., query responses remain unchanged even
upon repeating the same query multiple times. Such noise models have been
studied extensively (mazumdar2017clustering, ; prelec2017solution, ;
ghoshdastidar2019foundations, ; braverman2008noisy, ; bressan2019correlation,
; galhotra2018robust, ) since the error due to oracles often does not change
with repetition, and in some cases increases upon repeated querying
(mazumdar2017clustering, ; prelec2017solution, ; galhotra2018robust, ). This
is in contrast to the noise models studied in (emamjomeh2018adaptive, ) where
response to every query is independently noisy. Persistent query models are
more difficult to handle than independent query models where repeating each
query is sufficient to generate the correct answer by majority voting.

###  1.1. Our Contributions

We present algorithms for finding the maximum, nearest and farthest neighbors,
$k$-center clustering and hierarchical clustering objectives under the
adversarial and probabilistic noise model using comparison oracle. We show
that our techniques have provable approximation guarantees for both the noise
models, are efficient and obtain good query complexity. We empirically
evaluate the robustness and efficiency of our techniques on real world
datasets.

(i) Maximum, Farthest and Nearest Neighbor: Finding maximum has received
significant attention under both adversarial and probabilistic models
(ajtai2009sorting, ; feige1994computing, ; geissmann2018optimal, ; DKMR15, ;
braverman2008noisy, ; geissmann2017sorting, ; klein2011tolerant, ;
geissmann2020optimal, ). In this paper, we provide the following results.

$\bullet$ Maximum under adversarial model.:

We present an algorithm that returns a value within $(1+\mu)^{3}$ of the
maximum among a set of $n$ values $V$ with probability $1-\delta$111$\delta$
is the confidence parameter and is standard in the literature of randomized
algorithms. using $O(n\log^{2}(1/\delta))$ oracle queries and running time
(Theorem 3.6).

$\bullet$ Maximum under probabilistic model.:

We present an algorithm that requires $O(n\log^{2}(n/\delta))$ queries to
identify $O(\log^{2}(n/\delta))$th rank value with probability $1-\delta$
(Theorem 3.7). In other words, in $O(n\log^{2}(n))$ time we can identify
$O(\log^{2}(n))$th value in the sorted order with probability
$1-\frac{1}{n^{c}}$ for any constant $c$.

To contrast our results with the state of the art, Ajtai et al.
(ajtai2009sorting, ) study a slightly different additive adversarial error
model where the answer of a maximum query is correct if the compared values
differ by $\theta$ (for some $\theta>0$) and otherwise the oracle answers
adversarially. Under this setting, they give an additive
$3\theta$-approximation with $O(n)$ queries. Although, our model cannot be
directly compared with theirs, we note that our model is scale invariant, and
thus, provides a much stronger bound when distances are small. As a
consequence, our algorithm can be used under additive adversarial model as
well, and obtaining the same approximation guarantees (Theorem 3.10).

For the probabilistic model, after a long series of works (braverman2008noisy,
; geissmann2017sorting, ; klein2011tolerant, ; geissmann2020optimal, ), only
recently an algorithm is proposed with query complexity $O(n\log{n})$ that
returns an $O(\log{n})$th rank value with probability $1-\frac{1}{n}$
(geissmann2018optimal, ). Previously, the best query complexity was
$O(n^{3/2})$ (geissmann2020optimal, ). While our bounds are slightly worse
than (geissmann2018optimal, ), our algorithm is significantly simpler.

Rest of the work in finding maximum allow repetition of queries and assume the
answers are independent (feige1994computing, ; DKMR15, ). As discussed
earlier, persistent errors are much more difficult to handle than independent
errors. In (feige1994computing, ), the authors present an algorithm that finds
maximum using $O(n\log 1/\delta)$ queries and succeeds with probability
$1-\delta$. Therefore, even under persistent errors, we obtain guarantees
close to the existing ones which assume independent error. The algorithms of
(feige1994computing, ; DKMR15, ) do not extend to our model.

$\bullet$ Nearest Neighbor.:

Nearest neighbor queries can be cast as “finding minimum” among a set of
distances. We can obtain bounds similar to finding maximum for the nearest
neighbor queries. In the adversarial model, we obtain an
$(1+\mu)^{3}$-approximation, and in the probabilistic model, we are guaranteed
to return an element with rank $O(\log^{2}({n}/\delta))$ with probability
$1-\delta$ using $O(n\log^{2}(1/\delta))$ and $O(n\log^{2}({n}/\delta))$
oracle queries respectively.

Prior techniques have studied nearest neighbor search under noisy distance
queries (mason2019learning, ), where the oracle returns a noisy estimate of a
distance between queried points, and repetitions are allowed. Neither the
algorithm of (mason2019learning, ), nor other techniques developed for maximum
(ajtai2009sorting, ; feige1994computing, ) and top-$k$ (DKMR15, ) extend for
nearest neighbor under our noise models.

$\bullet$ Farthest Neighbor.:

Similarly, the farthest neighbor query can be cast as finding maximum among a
set of distances, and the results for computing maximum extends to this
setting. However, computing the farthest neighbor is one of the basic
primitives for more complex tasks like $k$-center clustering, and for that,
the existing bounds under the probabilistic model that return an
$O(\log{n})$th rank element is insufficient. Since distances on a metric space
satisfies triangle inequality, we exploit it to get a constant approximation
to the farthest query under the probabilistic model and a mild distribution
assumption (Theorem 3.10).

(ii) $k$-center Clustering: $k$-center clustering is one of the fundamental
models of clustering and is very well-studied (williamson2011design, ;
vazirani2013approximation, ).

$\bullet$ $k$-center under adversarial model:

We design algorithm that returns a clustering that is a $2+\mu$ approximation
for small values of $\mu$ with probability $1-\delta$ using
$O(nk^{2}+nk\log^{2}(k/\delta))$ queries (Theorem 4.2). In contrast, even when
exact distances are known, $k$-center cannot be approximated better than a
$2$-factor unless $P=NP$ (vazirani2013approximation, ). Therefore, we achieve
near-optimal results.

$\bullet$ $k$-center under probabilistic noise model.:

For probabilistic noise, when optimal $k$-center clusters are of size at least
$\Omega(\sqrt{n})$, our algorithm returns a clustering that achieves constant
approximation with probability $1-\delta$ using $O(nk\log^{2}(n/\delta))$
queries (Theorem 4.4).

To the best of our knowledge, even though $k$-center clustering is an
extremely popular and basic clustering paradigm, it hasn’t been studied under
the comparison oracle model, and we provide the first results in this domain.

(iii) Single Linkage and Complete Linkage– Agglomerative Hierarchical
Clustering : Under adversarial noise, we show a clustering technique that
loses only a multiplicative factor of $(1+\mu)^{3}$ in each merge operation
and has an overall query complexity of $O(n^{2})$. Prior work
(ghoshdastidar2019foundations, ) considers comparison oracle queries to
perform average linkage in which the unobserved pairwise similarities are
generated according to a normal distribution. These techniques do not extend
to our noise models.

###  1.2. Other Related Work

For finding the maximum among a given set of values, it is known that
techniques based on tournament obtain optimal guarantees and are widely used
(DKMR15, ). For the problem of finding nearest neighbor, techniques based on
locality sensitive hashing generally work well in practice (arora2018hd, ).
Clustering points using $k$-center objective is NP-hard and there are many
well known heuristics and approximation algorithms (williamson2011design, )
with the classic greedy algorithm achieving an approximation ratio of $2$. All
these techniques are not applicable when pairwise distances are unknown. As
distances between points cannot always be accurately estimated, many recent
techniques leverage supervision in the form of an oracle. Most oracle based
clustering frameworks consider ‘optimal cluster’ queries
(mazumdar2017clustering, ; huleihel2019same, ; mazumdar2017query, ;
choudhury2019top, ; kasper, ) to identify ground truth clusters. Recent
techniques for distance based clustering objectives, such as $k$-means
(ashtiani2016clustering, ; chien2018query, ; kim2017relaxed, ; kim2017semi, )
and $k$-median (ailon2018approximate, ) use optimal cluster queries in
addition to distance information for obtaining better approximation
guarantees. As ‘optimal cluster’ queries can be costly or sometimes
infeasible, there has been recent interest in leveraging distance based
comparison oracles for other problems similar to our quadruplet oracles
(emamjomeh2018adaptive, ; ghoshdastidar2019foundations, ).

Distance based comparison oracles have been used to study a wide range of
problems and we list a few of them – learning fairness metrics
(ilvento2019metric, ), top-down hierarchical clustering with a different
objective (emamjomeh2018adaptive, ; chatziafratis2018hierarchical, ;
ghoshdastidar2019foundations, ), correlation clustering
(ukkonen2017crowdsourced, ) and classification (tamuz2011adaptively, ;
hopkins2020noise, ), identify maximum (guo2012so, ; venetis2012max, ), top-$k$
elements (klein2011tolerant, ; polychronopoulos2013human, ;
ciceri2015crowdsourcing, ; DKMR15, ; kou2017crowdsourced, ; dushkin2018top, ),
information retrieval (kazemi2018comparison, ), skyline computation
(verdugo2020skyline, ). To the best of our knowledge, there is no work that
considers quadruplet comparison oracle queries to perform $k$-center
clustering and single/complete linkage based hierarchical clustering.

Closely related to finding maximum, sorting has also been well studied under
various comparison oracle based noise models (braverman2008noisy, ;
braverman2016parallel, ). The work of (DKMR15, ) considers a different
probabilistic noise model with error varying as a function of difference in
the values but they assume that each query is independent and therefore
repetition can help boost the probability of success. Using a quadruplet
oracle, (ghoshdastidar2019foundations, ) studies the problem of recovering a
hierarchical clustering under a planted noise model and is not applicable for
single linkage.

##  2\. Preliminaries

Let $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ be a collection of $n$ records such
that each record maybe associated with a value $val(v_{i}),\forall i\in[1,n]$.
We assume that there exists a total ordering over the values of elements in
$V$. For simplicity we denote the value of record $v_{i}$ as $v_{i}$ instead
of $val(v_{i})$ whenever it is clear from the context.

Given this setting, we consider a comparison oracle that compares the values
of any pair of records $(v_{i},v_{j})$ and outputs Yes if $v_{i}\leq v_{j}$
and No otherwise.

###### Definition 2.1 (Comparison Oracle).

An oracle is a function $\operatorname*{\mathcal{O}}:V\times
V\rightarrow\\{\texttt{Yes},\texttt{No}\\}$. Each oracle query considers two
values as input and outputs
$\operatorname*{\mathcal{O}}(v_{1},v_{2})=\texttt{Yes}$ if $v_{1}\leq v_{2}$
and No otherwise.

Note that a comparison oracle is defined for any pair of values. Given this
oracle setting, we define the problem of identifying the maximum over the
records $V$.

###### Problem 2.2 (Maximum).

Given a collection of $n$ records $V=\\{v_{1},\ldots,v_{n}\\}$ and access to a
comparison oracle $\operatorname*{\mathcal{O}}$, identify the
$\arg\max_{v_{i}\in V}v_{i}$ with minimum number of queries to the oracle.

As a natural extension, we can also study the problem of identifying the
record corresponding to the smallest value in $V$.

###  2.1. Quadruplet Oracle Comparison Query

In applications that consider distance based comparison of records like
nearest neighbor identification, the records $V=\\{v_{1},\ldots,v_{n}\\}$ are
generally considered to be present in a high-dimensional metric space along
with a distance $d:V\times V\rightarrow\mathbb{R}^{+}$ defined over pairs of
records. We assume that the embedding of records in latent space is not known,
but there exists an underlying ground truth (arora2018hd, ). Prior techniques
mostly assume complete knowledge of accurate distance metric and are not
applicable in our setting. In order to capture the setting where we can
compare distances between pair of records, we define quadruplet oracle below.

###### Definition 2.3 ( Quadruplet Oracle).

An oracle is a function $\operatorname*{\mathcal{O}}:V\times V\times V\times
V\rightarrow\\{\texttt{Yes},\texttt{No}\\}$. Each oracle query considers two
pairs of records as input and outputs
$\operatorname*{\mathcal{O}}(v_{1},v_{2},v_{3},v_{4})=\texttt{Yes}$ if
$d(v_{1},v_{2})\leq d(v_{3},v_{4})$ and No otherwise.

The quadruplet oracle is similar to the comparison oracle discussed before
with a difference that the two values being compared are associated with pair
of records as opposed to individual records. Given this oracle setting, we
define the problem of identifying the farthest record over $V$ with respect to
a query point $q$ as follows.

###### Problem 2.4 (Farthest point).

Given a collection of $n$ records $V=\\{v_{1},\ldots,v_{n}\\}$, a query record
$q$ and access to a quadruplet oracle $\operatorname*{\mathcal{O}}$, identify
$\arg\max_{v_{i}\in V\setminus\\{q\\}}d(q,v_{i})$.

Similarly, the nearest neighbor query returns a point that satisfies
$\arg\min_{u_{i}\in V\setminus\\{q\\}}d(q,u_{i})$. Now, we formally define the
k-center clustering problem.

###### Problem 2.5 (k-center clustering).

Given a collection of $n$ records $V=\\{v_{1},\ldots,v_{n}\\}$ and access to a
comparison oracle $\operatorname*{\mathcal{O}}$, identify $k$ centers (say
$S\subseteq V$) and a mapping of records to corresponding centers,
$\pi:V\rightarrow S$, such that the maximum distance of any record from its
center, i.e., $\max_{v_{i}\in V}d(v_{i},\pi(v_{i}))$ is minimized.

We assume that the points $v_{i}\in V$ exist in a metric space and the
distance between any pair of points is not known. We denote the unknown
distance between any pair of points $(v_{i},v_{j})$ where $v_{i},v_{j}\in V$
as $d(v_{i},v_{j})$ and use $k$ to denote the number of clusters. Optimal
clusters are denoted as $C^{*}$ with $C^{*}(v_{i})\subseteq V$ denoting the
set of points belonging to the optimal cluster containing $v_{i}$. Similarly,
$C(v_{i})\subseteq V$ refers to the nodes belonging to the cluster containing
$v_{i}$ for any clustering given by $C(\cdot)$.

In addition to the k-center clustering, we study single linkage and complete
linkage–agglomerative clustering techniques where the distance metric over the
records is not known apriori. These techniques initialize each record $v_{i}$
in a separate singleton cluster and sequentially merge the pair of clusters
having the least distance between them. In case of single linkage, the
distance between two clusters $C_{1}$ and $C_{2}$ is characterized by the
closest pair of records defined as:

$d_{SL}(C_{1},C_{2})=\min_{v_{i}\in C_{1},v_{j}\in C_{2}}d(v_{i},v_{j})$

In complete linkage, the distance between a pair of clusters $C_{1}$ and
$C_{2}$ is calculated by identifying the farthest pair of records,
$d_{CL}(C_{1},C_{2})=\max_{v_{i}\in C_{1},v_{j}\in C_{2}}d(v_{i},v_{j}).$

###  2.2. Noise Models

The oracle models discussed in Problem 2.2, 2.4 and 2.5 assume that the oracle
answers every comparison query correctly. In real world applications, however,
the answers can be wrong which can lead to noisy results. To formalize the
notion of noise, we consider two different models. First, adversarial noise
model considers a setting where a comparison query can be adversarially wrong
if the two values being compared are within a multiplicative factor of
$(1+\mu)$ for some constant $\mu>0$.

$\operatorname*{\mathcal{O}}(v_{1},v_{2})=\begin{cases}\texttt{Yes}{},\text{
if }v_{1}<\frac{1}{(1+\mu)}v_{2}\\\ \texttt{No}{},\text{ if
}v_{1}>(1+\mu)v_{2}\\\ \text{adversarially incorrect if
}\frac{1}{(1+\mu)}\leq\frac{v_{1}}{v_{2}}\leq(1+\mu)\end{cases}$

The parameter $\mu$ corresponds to the degree of error. For example, $\mu=0$
implies a perfect oracle. The model extends to quadruplet oracle as follows.

$\operatorname*{\mathcal{O}}(v_{1},v_{2},v_{3},v_{4})=\begin{cases}\texttt{Yes}{},\text{
if }d(v_{1},v_{2})<\frac{1}{(1+\mu)}d(v_{3},v_{4})\\\ \texttt{No}{},\text{ if
}d(v_{1},v_{2})>(1+\mu)d(v_{3},v_{4})\\\ \text{adversarially incorrect
if}\frac{1}{(1+\mu)}\leq\frac{d(v_{1},v_{2})}{d(v_{3},v_{4})}\leq(1+\mu)\end{cases}$

The second model considers a probabilistic noise model where each comparison
query is incorrect independently with a probability $p<\frac{1}{2}$ and asking
the same query multiple times yields the same response. We discuss ways to
estimate $\mu$ and $p$ from real data in Section 6.

##  3\. Finding maximum

In this section, we present robust algorithms to identify the record
corresponding to the maximum value in $V$ under the adversarial noise model
and the probabilistic noise model. Later we extend the algorithms to find the
farthest and the nearest neighbor. We note that our algorithms for the
adversarial model are parameter free (do not depend on $\mu$) and the
algorithms for the probabilistic model can use $p=0.5$ as a worst case
estimate of the noise.

###  3.1. Adversarial Noise

Consider a trivial approach that maintains a running maximum value while
sequentially processing the records, i.e., if a larger value is encountered,
the current maximum value is updated to the larger value. This approach
requires $n-1$ comparisons. However, in the presence of adversarial noise, our
output can have a significantly lower value compared to the correct maximum.
In general, if $v_{max}$ is the true maximum of $V$, then the above approach
can return an approximate maximum whose value could be as low as
${v_{max}}/{(1+\mu)^{n-1}}$. To see this, assume $v_{1}=1$, and
$v_{i}=(1+\mu-\epsilon)^{i}$ where $\epsilon>0$ is very close to $0$. It is
possible that while comparing $v_{i}$ and $v_{i+1}$, the oracle returns
$v_{i}$ as the larger element. If this mistake is repeated for every $i$,
then, $v_{1}$ will be declared as the maximum element whereas the correct
answer is $v_{n}\approx v_{1}(1+\mu)^{n-1}$.

To improve upon this naive strategy, we introduce a natural keeping score
based idea where given a set $S\subseteq V$ of records, we maintain
$\texttt{Count}(v,S)$ that is equal to the number of values smaller than $v$
in $S$.

$\texttt{Count}(v,S)=\sum_{x\in
S\setminus\\{v\\}}1\\{\operatorname*{\mathcal{O}}(v,x)==\texttt{No}{}\\}$

It is easy to observe that when the oracle makes no mistakes,
$\texttt{Count}(s_{\text{max}},S)=|S|-1$ and obtains the highest score, where
$s_{\text{max}}$ is the maximum value in $S$. Using this observation, in
Algorithm 1, we output the value with the highest Count score.

Given a set of records $V$, we show in Lemma 3.1 that $\textsc{Count-Max}(V)$
obtained using Algorithm 1 always returns a good approximation of the maximum
value in $V$.

###### Lemma 3.1.

Given a set of values $V$ with maximum value $v_{\text{max}}$, $\textsc{Count-
Max}(V)$ returns a value $u_{\text{max}}$ where $u_{\text{max}}\geq
v_{\text{max}}/(1+\mu)^{2}$ using $O(|V|^{2})$ oracle queries.

Using Example 3.2, when $\mu=1$, we demonstrate that $(1+\mu)^{2}=4$
approximation ratio is achieved by Algorithm 1.

###### Example 3.2.

Let $S$ denote a set of four records $u,v,w$ and $t$ with ground truth values
$51$, $101$, $102$ and $202$, respectively. While identifying the maximum
value under adversarial noise with $\mu=1$, the oracle must return a correct
answer to $\operatorname*{\mathcal{O}}(u,t)$ and all other oracle query
answers can be incorrect adversarially. If the oracle answers all other
queries incorrectly, we have, Count values of $t,w,u,v$ are $1,1,2$, and $2$
respectively. Therefore, $u$ and $v$ are equally likely, and when Algorithm 1
returns $u$, we have a $202/51\approx 3.96$ approximation.

From Lemma 3.1, we have that $O(n^{2})$ oracle queries where $|V|=n$, are
required to get $(1+\mu)^{2}$ approximation. In order to improve the query
complexity, we use a tournament to obtain the maximum value. The idea of using
a _tournament_ for finding maximum has been studied in the past (DKMR15, ;
feige1994computing, ).

Algorithm 2 presents pseudo code of the approach that takes values $V$ as
input and outputs an approximate maximum value. It constructs a balanced
$\lambda$-ary tree $\mathcal{T}$ containing $n$ leaf nodes such that a random
permutation of the values $V$ is assigned to the leaves of $\mathcal{T}$. In a
tournament, the internal nodes of $\mathcal{T}$ are processed bottom-up such
that at every internal node $w$, we assign the value that is largest among the
children of $w$. To identify the largest value, we calculate
$\arg\max_{v\in\textit{children}(w)}\texttt{Count}(v,\textit{children}(w))$ at
the internal node $w$, where $\texttt{Count}(v,X)$ refers to the number of
elements in $X$ that are considered smaller than $v$. Finally, we return the
value at the root of $\mathcal{T}$ as our output. In Lemma 3.3, we show that
Algorithm 2 returns a value that is a $(1+\mu)^{2\log_{\lambda}n}$
multiplicative approximation of the maximum value.

1:Input : A set of values $S$

2:Output : An approximate maximum value of $S$

3:for $v\in S$ do

4: Calculate $\texttt{Count}(v,S)$

5:$u_{\text{max}}\leftarrow\text{arg max}_{v\in S}\texttt{Count}(v,S)$

6:return $u_{\text{max}}$

Algorithm 1 Count-Max(S) : finds the max. value by counting

###### Lemma 3.3.

Suppose $v_{max}$ is the maximum value among the set of records $V$. Algorithm
2 outputs a value $u_{max}$ such that
$u_{max}\geq\frac{v_{max}}{(1+\mu)^{2\log_{\lambda}n}}$ using $O(n\lambda)$
oracle queries.

According to Lemma 3.3, Algorithm 2 identifies a constant approximation when
$\lambda=\Theta(n)$, $\mu$ is a fixed constant and has a query complexity of
$\Theta(n^{2})$. By reducing the degree of the tournament tree from $\lambda$
to $2$, we can achieve $\Theta(n)$ query complexity, but with a worse
approximation ratio of $(1+\mu)^{\log n}$.

Now, we describe our main algorithm (Algorithm 4) that uses the the following
observation to improve the overall query complexity.

###### Observation 3.4.

At an internal node $w\in\mathcal{T}$, the identified maximum is incorrect
only if there exists $x\in\textit{children}(w)$ that is very close to the true
maximum (say $w_{max}$), i.e. $\frac{w_{\max}}{(1+\mu)}\leq
x\leq(1+\mu)w_{\max}$.

Based on the above observation, our Algorithm Max-Adv uses two steps to
identify a good approximation of $v_{\text{max}}$. Consider the case when
there are a lot of values that are close to $v_{\text{max}}$. In Algorithm
Max-Adv, we use a subset $\widetilde{V}\subseteq V$ of size $\sqrt{n}t$ (for a
suitable choice of parameter $t$) obtained using uniform sampling with
replacement. We show that using a sufficiently large subset $\widetilde{V}$,
obtained by sampling, we ensure that at least one value that is closer to
$v_{\text{max}}$ is in $\widetilde{V}$, thereby giving a good approximation of
$v_{\text{max}}$.

1:Input : Set of values $V$, Degree $\lambda$

2:Output : An approximate maximum value $u_{\text{max}}$

3:Construct a balanced $\lambda$-ary tree $\mathcal{T}$ with $|V|$ nodes as
leaves.

4:Let $\pi_{V}$ be a random permutation of $V$ assigned to leaves of
$\mathcal{T}$

5:for $i=1$ to $\log_{\lambda}|V|$ do

6: for internal node $w$ at level $\log_{\lambda}|V|-i$ do

7: Let $U$ denote the children of $w$.

8: Set the internal node $w$ to $\textsc{Count-Max}(U)$

9:$u_{\text{max}}\leftarrow$value at root of $\mathcal{T}$

10:return $u_{\text{max}}$

Algorithm 2 Tournament : finds the maximum value using a tournament tree

In order to handle the case when there are only a few values closer to
$v_{\text{max}}$, we divide the entire data set into $l$ disjoint parts (for a
suitable choice of $l$) and run the Tournament algorithm with degree
$\lambda=2$ on each of these parts separately (Algorithm 3). As there are very
few points close to $v_{\text{max}}$, the probability of comparing any such
value with $v_{\text{max}}$ is small, and this ensures that in the partition
containing $v_{\text{max}}$, Tournament returns $v_{\text{max}}$. We collect
the maximum values returned by Algorithm 2 from all the partitions and include
these values in $T$ in Algorithm Max-Adv. We repeat this procedure $t$ times
and set $l=\sqrt{n},t=2\log(2/\delta)$ to achieve the desired success
probability $1-\delta$. We combine the outputs of both the steps, i.e.,
$\widetilde{V}$ and $T$ and output the maximum among them using Count-Max.
This ensures that we get a good approximation as we use the best of both the
approaches.

1:Input : Set of values $V$, number of partitions $l$

2:Output : A set of maximum values from each partition

3:Randomly partition $V$ into $l$ equal parts $V_{1},V_{2},\cdots V_{l}$

4:for $i=1$ to $l$ do

5: $p_{i}\leftarrow\textsc{Tournament}(V_{i},2)$

6: $T\leftarrow T\cup\\{p_{i}\\}$

7:return $T$

Algorithm 3 Tournament-Partition

1:Input : Set of values $V$, number of iterations $t$, partitions $l$

2:Output : An approximate maximum value $u_{\text{max}}$

3:$i\leftarrow 1,T\leftarrow\phi$

4:Let $\widetilde{V}$ denote a sample of size $\sqrt{n}t$ selected uniformly
at random (with replacement) from $V$.

5:for $i\leq t$ do

6: $T_{i}\leftarrow\textsc{Tournament-Partition}(V,l)$

7: $T\leftarrow T\cup T_{i}$

8:$u_{\text{max}}\leftarrow\textsc{Count-Max}(\widetilde{V}\cup T)$

9:return $u_{\text{max}}$

Algorithm 4 Max-Adv : Maximum with Adversarial Noise

Theoretical Guarantees. In order to prove approximation guarantee of Algorithm
4, we first argue that the sample $\widetilde{V}$ contains a good
approximation of the maximum value $v_{\text{max}}$ with a high probability.
Let $C$ denote the set of values that are very close to $v_{\text{max}}$.
$\text{Suppose }C=\\{u:{v_{\text{max}}}/{(1+\mu)}\leq u\leq
v_{\text{max}}\\}.$ In Lemma 3.5, we first show that $\widetilde{V}$ contains
a value $v_{j}\in\widetilde{V}$ such that
$v_{j}\geq{v_{\text{max}}}/{(1+\mu)}$, whenever the size of $C$ is large,
i.e., $|C|>{\sqrt{n}}/{2}$. Otherwise, we show that we can recover
$v_{\text{max}}$ correctly with probability $1-\delta/2$ whenever
$|C|\leq{\sqrt{n}}/{2}$.

###### Lemma 3.5.

  1. (1)

If $|C|>{\sqrt{n}}/{2}$, then there exists a value $v_{j}\in\widetilde{V}$
satisfying $v_{j}\geq{v_{\text{max}}}/{(1+\mu)}$ with probability of
$1-\delta/2$.

  2. (2)

Suppose $|C|\leq{\sqrt{n}}/{2}$. Then, $T$ contains $v_{\text{max}}$ with
probability at least $1-\delta/2$.

Now, we briefly provide a sketch of the proof of Lemma 3.5. Consider the first
step, where we use a uniformly random sample $\widetilde{V}$ of $\sqrt{n}t$
points from $V$ (obtained with replacement). When $|C|\geq{\sqrt{n}}/{2}$,
probability that $\widetilde{V}$ contains a value from $C$ is given by
$1-(1-|C|/n)^{|\widetilde{V}|}=1-\left(1-\frac{1}{2\sqrt{n}}\right)^{2\sqrt{n}\log(2/\delta)}\approx
1-\delta/2$.

In the second step, Algorithm 4 uses a modified tournament tree that
partitions the set $V$ into $l=\sqrt{n}$ parts of size ${n}/{l}=\sqrt{n}$ each
and identifies a maximum $p_{i}$ from each partition $V_{i}$ using Algorithm
2. We have that the expected number of elements from $C$ in a partition
$V_{i}$ containing $v_{\text{max}}$ is
${|C|}/{l}={\sqrt{n}}/{(2\sqrt{n})}={1}/{2}$. Thus by the Markov’s inequality,
the probability that $V_{i}$ contains a value from $C$ is $\leq{1}/{2}$. With
$1/2$ probability, $v_{\text{max}}$ will never be compared with any point from
$C$ in the partition $V_{i}$. To increase the success probability, we run this
procedure $t$ times and obtain all the outputs. Among the $t$ runs of
Algorithm 2, we argue that $v_{\text{max}}$ is never compared with any value
of $C$ in at least one of the iterations with a probability at least
$1-(1-1/2)^{2\log(2/\delta)}\geq 1-{\delta}/{2}$.

In Lemma 3.1, we show that using Count-Max we get a $(1+\mu)^{2}$
multiplicative approximation. Combining it with Lemma 3.5, we have that
$u_{\text{max}}$ returned by Algorithm 4 satisfies
$u_{\text{max}}\geq\frac{v_{\text{max}}}{(1+\mu)^{3}}$ with probability
$1-\delta$. For query complexity, Algorithm 3 identifies $\sqrt{n}t$ samples
denoted by $\widetilde{V}$. These identified values, along with $T$ are then
processed by Count-Max to identify the maximum $u_{max}$. This step requires
$O(|\widetilde{V}\cup T|^{2})=O(n\log^{2}(1/\delta))$ oracle queries.

###### Theorem 3.6.

Given a set of values $V$, Algorithm 4 returns a $(1+\mu)^{3}$ approximation
of maximum value with probability $1-\delta$ using $O(n\log^{2}(1/\delta))$
oracle queries.

###  3.2. Probabilistic Noise

We cannot directly extend the algorithms for the adversarial noise model to
probabilistic noise. Specifically, the theoretical guarantees of Lemma 3.3 do
not apply when the noise is probabilistic. In this section, we develop several
new ideas to handle probabilistic noise.

Let $\textrm{rank}(u,V)$ denote the index of $u$ in the non-increasing sorted
order of values in $V$. So, $v_{max}$ will have rank $1$ and so on. Our main
idea is to use an early stopping approach that uses a sample $S\subseteq V$ of
$O(\log(n/\delta))$ values selected randomly and for every value $u$ that is
not in $S$, we calculate $\texttt{Count}(u,S)$ and discard $u$ using a chosen
threshold for the Count scores. We argue that by doing so, it helps us
eliminate the values that are far away from the maximum in the sorted ranking.
This process is continued $\Theta(\log n)$ times to identify the maximum
value. We present the pseudo code in the Appendix and prove the following
approximation guarantee.

###### Theorem 3.7.

There is an algorithm that returns $u_{\text{max}}\in V$ such that
$\textrm{rank}(u_{\text{max}},V)=O(\log^{2}(n/\delta))$ with probability
$1-\delta$ and requires $O(n\log^{2}(n/\delta))$ oracle queries.

The algorithm to identify the minimum value is same as that of maximum with a
modification where Count scores consider the case of Yes (instead of No):
$\texttt{Count}(v,S)=\sum_{x\in
S\setminus\\{v\\}}\mathbf{1}\\{\operatorname*{\mathcal{O}}(v,x)==\texttt{Yes}{}\\}$

###  3.3. Extension to Farthest and Nearest Neighbor

Given a set of records $V$, the farthest record from a query $u$ corresponds
to the record $u^{\prime}\in V$ such that $d(u,u^{\prime})$ is maximum. This
query is equivalent to finding maximum in the set of distance values given by
$D(u)=\\{d(u,u^{\prime})\mid\forall u^{\prime}\in V\\}$ containing $n$ values
for which we already developed algorithms in Section 3. Since the ground truth
distance between any pair of records is not known, we require quadruplet
oracle (instead of comparison oracle) to identify the maximum element in
$D(u)$. Similarly, the nearest neighbor of query record $u$ corresponds to
finding the record with minimum distance value in $D(u)$. Algorithms for
finding maximum from previous sections, extend for these settings with similar
guarantees.

###### Example 3.8.

Figure 2 shows a worst-case example for the approximation guarantee to
identify the farthest point from $s$ (with $\mu=1$). Similar to Example 3.2,
we have, Count values of $t,w,u,v$ are $1,1,2,2$ respectively. Therefore, $u$
and $v$ are equally likely, and when Algorithm 1 outputs $u$, we have a
$\approx 3.96$ approximation.

$s$$51$$u$$50$$v$$1$$w$$100$$t$ Figure 2. Example for Lemma 3.1 with $\mu=1$.

For probabilistic noise, the farthest identified in Section 3.2 is guaranteed
to rank within the top-$O(\log^{2}n)$ values of set $V$ (Theorem 3.7). In this
section, we show that it is possible to compute the farthest point within a
small additive error under the probabilistic model, if the data set satisfies
an additional property discussed below. For the simplicity of exposition, we
assume $p\leq 0.40$, though our algorithms work for any value of $p<0.5$ (with
different constants).

One of the challenges in developing robust algorithms for farthest
identification is that every relative distance comparison of records from $u$
($\operatorname*{\mathcal{O}}(u,v_{i},u,v_{j})$ for some $v_{i},v_{j}\in V$)
may be answered incorrectly with constant error probability $p$ and the
success probability cannot be boosted by repetition. We overcome this
challenge by performing pairwise comparisons in a robust manner. Suppose the
desired failure probability is $\delta$, we observe that if
$\Theta(\log(1/\delta))$ records closest to the query $u$ are known (say $S$)
and $\max_{x\in S}\\{d(u,x)\\}\leq\alpha$ for some $\alpha>0$, then each
pairwise comparison of the form $\operatorname*{\mathcal{O}}(u,v_{i},u,v_{j})$
can be replaced by Algorithm PairwiseComp and use it to execute Algorithm 4.
Algorithm 5 takes the two records $v_{i}$ and $v_{j}$ as input along with $S$
and outputs Yes or No where Yes denotes that $v_{i}$ is closer to $u$. We
calculate $\texttt{FCount}(v_{i},v_{j})=\sum_{x\in
S}\mathbf{1}\\{\operatorname*{\mathcal{O}}(v_{i},x,v_{j},x)==\texttt{Yes}\\}$
as a robust estimate where the oracle considers $v_{i}$ to be closer to $x$
than $v_{j}$. If $\texttt{FCount}(v_{i},v_{j})$ is smaller than
$0.3|S|\leq(1-p)|S|/2$ then we output No and Yes otherwise. Therefore, every
pairwise comparison query is replaced with $\Theta(\log(1/\delta))$ quadruplet
queries using Algorithm 5.

We argue that Algorithm 5 will output the correct answer with a high
probability if $|d(u,v_{j})-d(u,v_{i})|\geq 2\alpha$ (See Fig 3). In Lemma
3.9, we show that, if $d(u,v_{j})>d(u,v_{i})+2\alpha$, then,
$\texttt{FCount}(v_{i},v_{j})\geq 0.3|S|$ with probability $1-\delta$.

###### Lemma 3.9.

Suppose $\max_{v_{i}\in S}d(u,v_{i})\leq\alpha$ and $|S|\geq 6\log(1/\delta)$.
Consider two records $v_{i}$ and $v_{j}$ such that
$d(u,v_{i})<d(u,v_{j})-2\alpha$ then $\texttt{FCount}(v_{i},v_{j})\geq 0.3|S|$
with a probability of $1-\delta$.

With the help of Algorithm 5, relative distance query of any pair of records
$v_{i},v_{j}$ from $u$ can be answered correctly with a high probability
provided $|d(u,v_{i})-d(u,v_{j})|\geq 2\alpha$. Therefore, the output of
Algorithm 5 is equivalent to an additive adversarial error model where any
quadruplet query can be adversarially incorrect if the distance
$|d(u,v_{i})-d(u,v_{j})|<2\alpha$ and correct otherwise. In the Appendix, we
show that Algorithm 4 can be extended to the additive adversarial error model,
such that each comparison $\O(u,v_{i},u,v_{j})$ is replaced by PairwiseComp
(Algorithm 5). We give an approximation guarantee, that loses an additive
$6\alpha$ following a similar analysis of Theorem 3.6.

$S$$v_{j}$$v_{i}$$u$$\alpha$$2\alpha$ In this example,
$\operatorname*{\mathcal{O}}(u,v_{i},u,v_{j})$ is answered correctly with a
probability $1-p$. To boost the correctness probability, FCount uses the
queries $\operatorname*{\mathcal{O}}(x,v_{i},x,v_{j})$, $\forall x$ in the red
region around $u$, denoted by $S$. Figure 3. Algorithm 5 returns ‘Yes’ as
$d(u,v_{i})<d(u,v_{j})-2\alpha$. Algorithm 5 PairwiseComp ($u,v_{i},v_{j},S$)

1:Calculate $\texttt{FCount}(v_{i},v_{j})=\sum_{x\in
S}\mathbf{1}\\{\operatorname*{\mathcal{O}}(x,v_{i},x,v_{j})==\texttt{Yes}\\}$

2:if $\texttt{FCount}(v_{i},v_{j})<0.3|S|$ then

3: return No

4:else return Yes

###### Theorem 3.10.

Given a query vertex $u$ and a set $S$ with $|S|=\Omega(\log(n/\delta))$ such
that $\max_{v\in S}d(u,v)\leq\alpha$ then the farthest identified using
Algorithm 4 (with PairwiseComp), denoted by $u_{\text{max}}$ is within
$6\alpha$ distance from the optimal farthest point, i.e.,
$d(u,u_{\text{max}})\geq\max_{v\in V}d(u,v)-6\alpha$ with a probability of
$1-\delta$. Further the query complexity is $O(n\log^{3}(n/\delta))$.

##  4\. $k$-center clustering

In this section, we present algorithms for $k$-center clustering and prove
constant approximation guarantees of our algorithm. Our algorithm is an
adaptation of the classical greedy algorithm for $k$-center
(gonzalez1985clustering, ). The greedy algorithm (gonzalez1985clustering, ) is
initialized with an arbitrary point as the first cluster center and then
iteratively identifies the next centers. In each iteration, it assigns all the
points to the current set of clusters, by identifying the closest center for
each point. Then, it finds the farthest point among the clusters and uses it
as the new center. This technique requires $O(nk)$ distance comparisons in the
absence of noise and guarantees $2$-approximation of the optimal clustering
objective. We provide the pseudocode for this approach in Algorithm 6. Using
an argument similar to the one presented for the worst case example in Section
3, we can show that if we use Algorithm 6 where we replace every comparison
with an oracle query, the generated clusters can be arbitrarily worse even for
small error. In order to improve its robustness, we devise new algorithms to
perform assignment of points to respective clusters and farthest point
identification. Missing Details from this section are discussed in Appendix 10
and 11.

1:Input : Set of points $V$

2:Output : Clusters $\mathcal{C}$

3:$s_{1}\leftarrow\text{arbitrary point from }V$, $S=\\{s_{1}\\}$,
$C=\\{\\{V\\}\\}$.

4:for $i=2$ to $k$ do

5: $s_{i}\leftarrow\textsc{Approx-Farthest}(S,C)$

6: $S\leftarrow S\cup\\{s_{i}\\}$

7: $\mathcal{C}\leftarrow\textsc{Assign}(S)$

8:return ${\mathcal{C}}$

Algorithm 6 Greedy Algorithm

###  4.1. Adversarial Noise

Now, we describe the two steps (Approx-Farthest and Assign) of the Greedy
Algorithm that will complete the description of Algorithm 6. To do so, we
build upon the results from previous section that give algorithms for
obtaining maximum/farthest point.

Approx-Farthest. Given a clustering $\mathcal{C}$, and a set of centers $S$,
we construct the pairs $(v_{i},s_{j})$ where $v_{i}$ is assigned to cluster
$C(s_{j})$ centered at $s_{j}\in S$. Using Algorithm 4, we identify the point,
center pair that have the maximum distance i.e. $\arg\max_{v_{i}\in
V}d(v_{i},s_{j})$, which corresponds to the farthest point. For the
parameters, we use $l=\sqrt{n}$, $t=\log(2k/\delta)$ and number of samples
$\widetilde{V}=\sqrt{n}t$.

Assign. After identifying the farthest point, we reassign all the points to
the centers (now including the farthest point as the new center) closest to
them. We calculate a movement score called MCount for every point with respect
to each center. $\texttt{MCount}(u,s_{j})=\sum_{s_{k}\in
S\setminus\\{s_{j}\\}}1\\{\operatorname*{\mathcal{O}}((s_{j},u),(s_{k},u))==\texttt{Yes}\\}$,
for any record $u\in V$ and $s_{j}\in S$. This step is similar to Count-Max
Algorithm. We assign the point $u$ to the center with the highest MCount
value.

###### Example 4.1.

Suppose we run k-center algorithm with $k=2$ and $\mu=1$ on the points in
Example 3.8. The optimal centers are $u$ and $t$ with radius $51$. On running
our algorithm, suppose $w$ is chosen as the first center and Approx-Farthest
calculates Count values similar to Example 3.2. We have, Count values of
$s,t,u,v$ are $1,2,3,0$ respectively. Therefore, our algorithm identifies $u$
as the second center, achieving $3$-approximation.

Theoretical Guarantees. We now prove the approximation guarantee obtained by
Algorithm 6.

In each iteration, we show that Assign reassigns each point to a center with
distance approximately similar to the distance from the closest center. This
is surprising given that we only use MCount scores for assignment. Similarly,
we show that Approx-Farthest (Algorithm 4) identifies a close approximation to
the true farthest point. Concretely, we show that every point is assigned to a
center which is a $(1+\mu)^{2}$ approximation; Algorithm 4 identifies farthest
point $w$ which is a $(1+\mu)^{5}$ approximation.

In every iteration of the Greedy algorithm, if we identify an
$\alpha$-approximation of the farthest point, and a $\beta$-approximation when
reassigning the points, then, we show that the clusters output are a
$2\alpha\beta^{2}$-approximation to the $k$-center objective. For complete
details, please refer Appendix 10. Combining all the claims, for a given error
parameter $\mu$, we obtain:

###### Theorem 4.2.

For $\mu<\frac{1}{18}$, Algorithm 6 achieves a $(2+O(\mu))$-approximation for
the $k$-center objective using $O(nk^{2}+nk\cdot\log^{2}(k/\delta))$ oracle
queries with probability $1-\delta$.

###  4.2. Probabilistic Noise

For probabilistic noise, each query can be incorrect with probability $p$ and
therefore, Algorithm 6 may lead to poor approximation guarantees. Here, we
build upon the results from section 3.3 and provide Approx-Farthest and Assign
algorithms. We denote the size of minimum cluster among optimum clusters
$C^{*}$ to be $m$, and total failure probability of our algorithms to be
$\delta$. We assume $p\leq 0.40$, a constant strictly less than $\frac{1}{2}$.
Let $\gamma=450$ be a large constant used in our algorithms which obtains the
claimed guarantees.

Overview. Algorithm 7 presents the pseudo-code of our algorithm that operates
in two phases. In the first phase (lines 3-12), we sample each point with a
probability ${\gamma\log(n/\delta)}/{m}$ to identify a small sample of
$\approx\frac{\gamma n\log(n/\delta)}{m}$ points (denoted by $\widetilde{V}$)
and use Algorithm 7 to identify $k$ centers iteratively. In this process, we
also identify a core for each cluster (denoted by $R$). Formally, core is
defined as a set of $\Theta({\log(n/\delta)})$ points that are very close to
the center with high probability. The cores are then used in the second phase
(line 15) for the assignment of remaining points.

1:Input : Set of points $V$, smallest cluster size $m$.

2:Output : Clusters ${C}$

3:For every$\ u\in V$, include $u$ in $\widetilde{V}$ with probability
$\frac{\gamma\log(n/\delta)}{m}$

4:$s_{1}\leftarrow\text{select an arbitrary point from }\widetilde{V}$,
$S\leftarrow\\{s_{1}\\}$

5:${C(s_{1})}\leftarrow\widetilde{V}$

6:$R(s_{1})\leftarrow\textsc{Identify-Core}(C(s_{1}),s_{1})$

7:for $i=2$ to $k$ do

8: $s_{i}\leftarrow\textsc{Approx-Farthest}(S,C)$

9: ${C,R}\leftarrow\textsc{Assign}(S,s_{i},R)$

10: $S\leftarrow S\cup\\{s_{i}\\}$

11:$C\leftarrow\textsc{Assign-Final}(S,R,V\setminus\widetilde{V})$

12:return ${{C}}$

Algorithm 7 Greedy Clustering

Now, we describe the main challenge in extending Approx-Farthest and Assign
ideas of Algorithm 6. Given a cluster $C$ containing the center $s_{i}$, when
we find the Approx-Farthest, the ideas from Section 3.2 give a $O(\log^{2}n)$
rank approximation. As shown in section 3.3, we can improve the approximation
guarantee by considering a set of $\Theta(\log(n/\delta))$ points closest to
$s_{i}$, denoted by $R(s_{i})$ and call them core of $s_{i}$. We argue that
such an assumption of set $R$ is justified. For example, consider the case
when clusters are of size $\Theta(n)$ and sampling $k\log(n/\delta)$ points
gives us $\log(n/\delta)$ points from each optimum cluster; which means that
there are $\log(n/\delta)$ points within a distance of $2\operatorname{OPT}$
from every sampled point where $\operatorname{OPT}$ refers to the optimum
$k$-center objective.

Assign. Consider a point $s_{i}$ such that we have to assign points to form
the cluster $C(s_{i})$ centered at $s_{i}$. We calculate an assignment score
(called ACount in line 4) for every point $u$ of a cluster $C(s_{j})\setminus
R(s_{j})$ centered at $s_{j}$. ACount captures the total number of times $u$
is considered to belong to same cluster as that of $x$ for each $x$ in the
core $R(s_{j})$. Intuitively, points that belong to same cluster as that of
$s_{i}$ are expected to have higher ACount score. Based on the scores, we move
$u$ to $C(s_{i})$ or keep it in $C(s_{j})$.

Algorithm 8 $\textsc{Assign}(S,s_{i},R)$

1:$C(s_{i})\leftarrow\\{s_{i}\\}$

2:for $s_{j}\in S$ do

3: for $u\in C(s_{j})\setminus R(s_{j})$ do

4: $\texttt{ACount}(u,s_{i},s_{j})=\sum_{v_{k}\in
R(s_{j})}\mathbf{1}\\{\operatorname*{\mathcal{O}}(u,s_{i},u,v_{k})==\texttt{Yes}\\}$

5: if $\texttt{ACount}(u,s_{i},s_{j})>0.3|R(s_{j})|$ then

6: $C(s_{i})\leftarrow C(s_{i})\cup\\{u\\};C(s_{j})\leftarrow
C(s_{j})\setminus\\{u\\}$

7:$R(s_{i})\leftarrow\textsc{Identify-Core}(C(s_{i}),s_{i})$

8:return C, R

Algorithm 9 $\textsc{Identify-Core}(C(s_{i}),s_{i})$

1:for $u\in C(s_{i})$ do

2: Count(u)=$\sum_{x\in
C(s_{i})}1\\{\operatorname*{\mathcal{O}}(s_{i},x,s_{i},u)==\texttt{No}\\}$

3:$R(s_{i})$ denote set of ${8\gamma\log(n/\delta)}/9$ points with the highest
Count values.

4:return $R(s_{i})$

Identify-Core. After forming cluster $C(s_{i})$, we identify the _core_ of
$s_{i}$. For this, we calculate a score, denoted by Count and captures number
of times it is closer to $s_{i}$ compared to other points in $C(S_{i})$.
Intuitively, we expect points with high values of Count to belong to
$C^{*}(s_{i})$ i.e., optimum cluster containing $s_{i}$. Therefore we sort
these Count scores and return the highest scored points.

Approx-Farthest. For a set of clusters $\mathcal{C}$, and a set of centers
$S$, we construct the pairs $(v_{i},s_{j})$ where $v_{i}$ is assigned to
cluster $C(s_{j})$ centered at $s_{j}\in S$ and each center $s_{j}\in S$ has a
corresponding core $R(s_{j})$. The farthest point can be found by finding the
maximum distance (point, center) pair among all the points considered. To do
so, we use the ideas developed in section 3.3.

We leverage ClusterComp (Algorithm 10) to compare the distance of two points,
say $v_{i},v_{j}$ from their respective centers $s_{i},s_{j}$. ClusterComp
gives a robust answer to a pairwise comparison query to the oracle
$\operatorname*{\mathcal{O}}(v_{i},s_{i},v_{j},s_{j})$ using the cores
$R(s_{i})$ and $R(s_{j})$. ClusterComp can be used as a pairwise comparison
subroutine in place of PairwiseComp for the algorithm in Section 3 to
calculate the farthest point. For every $s_{i}\in S$, let
$\widetilde{R}(s_{i})$ denote an arbitrary set of $\sqrt{R(s_{i})}$ points
from $R(s_{i})$. For a ClusterComp comparison query between the pairs
$(v_{i},s_{i})$ and $(v_{j},s_{j})$, we use these subsets in Algorithm 10 to
ensure that we only make $\Theta(\log(n/\delta))$ oracle queries for every
comparison. However, when the query is between points of the same cluster, say
$C(s_{i})$, we use all the $\Theta(\log(n/\delta))$ points from $R(s_{i})$.
For the parameters used to find maximum using Algorithm 4, we use
$l=\sqrt{n}$, $t=\log(n/\delta)$.

###### Example 4.3.

Suppose we run $k$-center Algorithm 7 with $k=2$ and $m=2$ on the points in
Example 3.8. Let $w$ denote the first center chosen and Algorithm 7 identifies
the core $R(w)$ by calculating Count values. If
$\operatorname*{\mathcal{O}}(u,w,s,w)$ and
$\operatorname*{\mathcal{O}}(s,w,t,w)$ are answered incorrectly (with
probability $p$), we obtain Count values of $v,s,u,t$ as $3,2,1,0$
respectively; and $v$ is added to $R(w)$. We identify the second center $u$ by
calculating FCount for $s,u$ and $t$ (See Fig. 3). After assigning (using
Assign), the clusters identified are $\\{w,v\\},\\{u,s,t\\}$, achieving
$3$-approximation.

Algorithm 10 ClusterComp ($v_{i},s_{i},v_{j},s_{j}$)

1:comparisons $\leftarrow 0,\texttt{FCount}(v_{i},v_{j})\leftarrow 0$

2:if $s_{i}=s_{j}$ then

3: Let $\texttt{FCount}(v_{i},v_{j})=\sum_{x\in
R(s_{i})}\mathbf{1}\\{\operatorname*{\mathcal{O}}(v_{i},x,v_{j},x)==\texttt{Yes}\\}$

4: comparisons $\leftarrow|R(s_{i})|$

5:else Let
$\texttt{FCount}(v_{i},v_{j})=\sum_{x\in\widetilde{R}(s_{i}),y\in\widetilde{R}(s_{j})}\mathbf{1}\\{\operatorname*{\mathcal{O}}(v_{i},x,v_{j},y)==\texttt{Yes}\\}$

6: comparisons $\leftarrow|\widetilde{R}(s_{i})|\cdot|\widetilde{R}(s_{j})|$

7:if $\texttt{FCount}(v_{i},v_{j})<0.3\cdot\text{comparisons }$ then

8: return No

9:else return Yes

Assign-Final. After obtaining $k$ clusters on the set of sampled points
$\widetilde{V}$, we assign the remaining points using ACount scores, similar
to the one described in Assign. For every point that is not sampled, we first
assign it to $s_{1}\in S$, and if $\texttt{ACount}(u,s_{2},s_{1})\geq
0.3{|R(s_{1})|}$, we re-assign it to $s_{2}$, and continue this process
iteratively. After assigning all the points, the clusters are returned as
output.

### Theoretical Guarantees

Our algorithm first constructs a sample $\widetilde{V}\subseteq V$ and runs
the greedy algorithm on this sampled set of points. Our main idea to ensure
that good approximation of the $k$-center objective lies in identifying a good
core around each center. Using a sampling probability of
$\gamma\log(n/\delta)/m$ ensures that we have at least
$\Theta(\log(n/\delta))$ points from each of the optimal clusters in our
sampled set $\widetilde{V}$. By finding the closest points using Count scores,
we identify $O(\log(n/\delta))$ points around every center that are in the
optimal cluster. Essentially, this forms the core of each cluster. These cores
are then used for robust pairwise comparison queries (similar to Section 3.3),
in our Approx-Farthest and Assign subroutines. We give the following theorem,
which guarantees a constant, i.e., $O(1)$ approximation with high probability.

###### Theorem 4.4.

Given $p\leq 0.4$, a failure probability $\delta$, and
$m=\Omega({\log^{3}(n/\delta)}/{\delta})$. Then, Algorithm 7 achieves a
$O(1)$-approximation for the $k$-center objective using
$O(nk\log(n/\delta)+\frac{n^{2}}{m^{2}}k\log^{2}(n/\delta))$ oracle queries
with probability $1-O(\delta)$.

##  5\. Hierarchical Clustering

In this section, we present robust algorithms for agglomerative hierarchical
clustering using single linkage and complete linkage objectives. The naive
algorithms initialize every record as a singleton cluster and merge the
closest pair of clusters iteratively. For a set of clusters
$\mathcal{C}=\\{C_{1},\ldots,C_{t}\\}$, the distance between any pair of
clusters $C_{i}$ and $C_{j}$, for single linkage clustering, is defined as the
minimum distance between any pair of records in the clusters,
$d_{SL}(C_{1},C_{2})=\min_{v_{1}\in C_{1},v_{2}\in C_{2}}d(v_{1},v_{2})$. For
complete linkage, cluster distance is defined as the maximum distance between
any pair of records. All algorithms discussed in this section can be easily
extended for complete linkage, and therefore we study single linkage
clustering. The main challenge in implementing single linkage clustering in
the presence of _adversarial_ noise is identification of minimum value in a
list of at most ${n\choose 2}$ distance values. In each iteration, the closest
pair of clusters can be identified by using Algorithm 4 (with
$t=2\log(n/\delta)$) to calculate the minimum over the set containing pairwise
distances. For this algorithm, Lemma 5.1 shows that the pair of clusters
merged in any iteration are a constant approximation of the optimal merge
operation at that iteration. The proof of this lemma follows from Theorem 3.6.

###### Lemma 5.1.

Given a collection of clusters $\mathcal{C}=\\{C_{1},\ldots,C_{r}\\}$, our
algorithm to calculate the closest pair (using Algorithm 4) identifies $C_{1}$
and $C_{2}$ to merge according to single linkage objective if
$d_{SL}(C_{2},C_{2})\leq(1+\mu)^{3}\min_{C_{i},C_{j}\in\mathcal{C}}d(C_{i},C_{j})$
with $1-\delta/n$ probability and requires $O(n^{2}\log^{2}(n/\delta))$
queries.

1:Input : Set of points $V$

2:Output : Hierarchy $H$

3:$H\leftarrow\\{\\{v\\}\mid v\in V\\},\mathcal{C}\leftarrow\\{\\{v\\}\mid
v\in V\\}$

4:for $C_{i}\in\mathcal{C}$ do

5: $\widetilde{C_{i}}\leftarrow$NearestNeighbor of $C_{i}$ among
$\mathcal{C}\setminus\\{C_{i}\\}$ using Sec 3.3

6:while $|\mathcal{C}|>1$ do

7: Let $(C_{j},\widetilde{C_{j}})$ be the closest pair among
$(C_{i},\widetilde{C}_{i}),\forall C_{i}\in\mathcal{C}$

8: $C^{\prime}\leftarrow C_{j}\cup\widetilde{C_{j}}$

9: Update Adjacency list of $C^{\prime}$ with respect to $\mathcal{C}$

10: Add $C^{\prime}$ as parent of $\widetilde{C_{j}}$ and $C_{j}$ in $H$.

11:
$\mathcal{C}\leftarrow\left(\mathcal{C}\setminus\\{C_{j},\widetilde{C_{j}}\\}\right)\cup\\{C^{\prime}\\}$

12: $\widetilde{C^{\prime}}\leftarrow$ NearestNeighbor of $C^{\prime}$ from
its adjacency list

13:return $H$

Algorithm 11 Greedy Algorithm

Overview. Agglomerative clustering techniques are known to be inefficient.
Each iteration of merge operation compares at most ${n\choose 2}$ pairs of
distance values and the algorithm operates $n$ times to construct the
hierarchy. This yields an overall query complexity of $O(n^{3})$. To improve
their query complexity, SLINK algorithm (sibson1973slink, ) was proposed to
construct the hierarchy in $O(n^{2})$ comparisons. To implement this algorithm
with a comparison oracle, for every cluster $C_{i}\in\mathcal{C}$, we maintain
an adjacency list containing every cluster $C_{j}$ in $\mathcal{C}$ along with
a pair of records with the distance equal to the distance between the
clusters. For example, the entry for $C_{j}$ in the adjacency list of $C_{i}$
contains the pair of records $(v_{i},v_{j})$ such that
$d(v_{i},v_{j})=\min_{v_{i}\in C_{i},v_{j}\in C_{j}}d(v_{i},v_{j})$. Algorithm
11 presents the pseudo code for single linkage clustering under the
adversarial noise model. The algorithm is initialized with singleton clusters
where every record is a separate cluster. Then, we identify the closest
cluster for every $C_{i}\in\mathcal{C}$, and denote it by $\widetilde{C_{i}}$.
This step takes $n$ nearest neighbor queries, each requiring
$O(n\log^{2}(n/\delta))$ oracle queries. In every subsequent iteration, we
identify the closest pair of clusters (Using section 3.3), say $C_{j}$ and
$\widetilde{C_{j}}$ from $\mathcal{C}$.

After merging these clusters, the data structure is updated as follows. To
update the adjacency list, we need the pair of records with minimum distance
between the merged cluster $C^{\prime}\equiv C_{j}\cup\widetilde{C_{j}}$ and
every other cluster $C_{k}\in\mathcal{C}$. In the previous iteration of the
algorithm, we already have the minimum distance record pair for
$(C_{j},C_{k})$ and $(\widetilde{C_{j}},C_{k})$. Therefore a single query
between these two pairs of records is sufficient to identify the minimum
distance edge between $C^{\prime}$ and $C_{k}$ (formally:
$d_{SL}(C_{j}\cup\widetilde{C_{j}},C_{k})=\min\\{d_{SL}(C_{j},C_{k}),d_{SL}(\widetilde{C_{j}},C_{k})\\}$).
The nearest neighbor of the merged cluster is identified by running minimum
calculation over its adjacency list. In Algorithm 11, as we identify closest
pair of clusters, each iteration requires $O(n\log^{2}(n/\delta))$ queries. As
our Algorithm terminates in at most $n$ iterations, it has an overall query
complexity of $O(n^{2}\log^{2}(n/\delta))$. In Theorem 5.2, we given an
approximation guarantee for every merge operation of Algorithm 11.

###### Theorem 5.2.

In any iteration, suppose the distance between a cluster $C_{j}\in\mathcal{C}$
and its identified nearest neighbor $\widetilde{C_{j}}$ is
$\alpha$-approximation of its distance from the optimal nearest neighbor, then
the distance between pair of clusters merged by Algorithm 11 is
$\alpha(1+\mu)^{3}$ approximation of the optimal distance between the closest
pair of clusters in $\mathcal{C}$ with a probability of $1-\delta$ using
$O(n\log^{2}(n/\delta))$ oracle queries.

Probabilistic Noise model. The above discussed algorithms do not extend to the
probabilistic noise due to constant probability of error for each query.
However, when we are given a priori, a partitioning of $V$ into clusters of
size $>\log n$ such that the maximum distance between any pair of records in
every cluster is smaller than $\alpha$ (a constant), Algorithm 11 can be used
to construct the hierarchy correctly. For this case, the algorithm to identify
the closest and farthest pair of clusters is same as the one discussed in
Section 3.3.

Note that agglomerative clustering algorithms are known to require
$\Omega(n^{2})$ queries, which can be infeasible for million scale datasets.
However, blocking based techniques present efficient heuristics to prune out
low similarity pairs (papadakis2016comparative, ). Devising provable
algorithms with better time complexity is outside the scope of this work.

##  6\. Experiments

In this section, we evaluate the effectiveness of our techniques on various
real world datasets and answer the following questions. Q1: Is quadruplet
oracle practically feasible? How do the different types of queries compare in
terms of quality and time taken by annotators? Q2: Are proposed techniques
robust to different levels of noise in oracle answers? Q3: How does the query
complexity and solution quality of proposed techniques compare with optimum
for varied levels of noise?

###  6.1. Experimental Setup

Datasets. We consider the following real-world datasets.
(1) cities dataset (uscities, ) comprises of $~{}36$K cities of the United
States. The different features of the cities include state, county, zip code,
population, time zone, latitude and longitude.
(2) caltech dataset comprises 11.4K images from 20 categories. The ground
truth distance between records is calculated using the hierarchical
categorization as described in (griffin2007caltech, ).
(3) amazon dataset contains $7$K images and textual descriptions collected
from amazon.com (he2016ups, ). For obtaining the ground truth distances we use
Amazon’s hierarchical catalog.
(4) monuments dataset comprises of $100$ images belonging to $10$ tourist
locations around the world.
(5) dblp contains 1.8M titles of computer science papers from different areas
(zhang2018taxogen, ). From these titles, noun phrases were extracted and a
dictionary of all the phrases was constructed. Euclidean distance in word2vec
embedding space is considered as the ground truth distance between concepts.

Baselines. We compare our techniques with the optimal solution (whenever
possible) and the following baselines. (a) Tour2 constructs a binary
tournament tree over the entire dataset to compare the values and the root
node corresponds to the identified maximum/minimum value (Algorithm 2 with
$\lambda=2$). This approach is an adaptation of the finding maximum algorithm
in (DKMR15, ) with a difference that each query is not repeated multiple times
to increase success probability. We also use them to identify the farthest and
nearest point in the greedy $k$-center Algorithm 6 and closest pair of
clusters in hierarchical clustering.

(b) Samp considers a sample of $\sqrt{n}$ records and identifies the
farthest/nearest by performing quadratic number of comparisons over the
sampled points using Count-Max. For $k$-center, Samp considers a sample of
$k\log n$ points to identify $k$ centers over these samples using the greedy
algorithm. It then assigns all the remaining points to the identified centers
by querying each record with every pair of center.

Calculating optimal clustering objective for $k$-center is NP-hard even in the
presence of accurate pairwise distance (williamson2011design, ). So, we
compare the solution quality with respect to the greedy algorithm on the
ground truth distances, denoted by TDist. For farthest, nearest neighbor and
hierarchical clustering, TDist denotes the optimal technique that has access
to ground truth distance between records.

Our algorithm is labelled Far for farthest identification, NN for nearest
neighbor, kC for $k$-center and HC for hierarchical clustering with subscript
$a$ denoting the adversarial model and $p$ denoting the probabilistic noise
model. All algorithms are implemented in C++ and run on a server with 64GB
RAM. The reported results are averaged over 100 randomly chosen iterations.
Unless specified, we set $t=1$ in Algorithm 4 and $\gamma=2$ in Algorithm 7.

Evaluation Metric. For finding maximum and nearest neighbors, we compare
different techniques by evaluating the true distance of the returned solution
from the queried points. For $k$-center, we use the objective value, i.e.,
maximum radius of the returned clusters as the evaluation metric and compare
against the true greedy algorithm (TDist) and other baselines. For datasets
where ground truth clusters are known (amazon, caltech and monuments), we use
F-score over intra-cluster pairs for comparing it with the baselines
(galhotra2018robust, ). For hierarchical clustering, we compute the pairs of
clusters merged in every iteration and compare the average true distance
between these clusters. In addition to the quality of returned solution, we
compare the query complexity and running time of the proposed techniques with
the baselines described above.

Noise Estimation. For cities, amazon, caltech, and monuments datasets, we ran
a user study on Amazon Mechanical Turk to estimate the noise in oracle answers
over a small sample of the dataset, often referred to as the validation set.
Using crowd responses, we trained a classifier (random forest (scikit, )
obtained the best results) using active learning to act as the quadruplet
oracle, and reduce the number of queries to the crowd. Our active learning
algorithm (modal, ) uses a batch of $20$ queries and we stop it when the
classifier accuracy on the validation set does not improve by more than $0.01$
(gokhale2014corleone, ). To efficiently construct a small set of candidates
for active learning and pruning low similarity pairs for dblp, we employ token
based blocking (papadakis2016comparative, ) for the datasets. For the
synthetic oracle, we simulate quadruplet oracle with different values of the
noise parameters.

###  6.2. User study

In this section, we evaluate the users ability to answer quadruplet queries
and compare it with other types of queries.

Setup. We ran a user study on Amazon Mechanical Turk platform for four
datasets cities, amazon, caltech and monuments. We consider the ground truth
distance between record pairs and discretize them into buckets, and assign a
pair of records to a bucket if the distance falls within its range. For every
pair of buckets, we query a random subset of $\log n$ quadruplet oracle
queries (where $n$ is size of dataset). Each query is answered by three
different crowd workers and a majority vote is taken as the answer to the
query.

(a) caltech

(b) amazon

Figure 4. Accuracy values (denoted by the color of a cell) for different
distance ranges observed during our user study. The diagonal entries refer to
the quadruplets with similar distance between the corresponding pairs and the
distance increases as we go further away from the diagonal.

####  6.2.1. Qualitative Analysis of Oracle

In Figure 4, for every pair of buckets, using a heat map, we plot the accuracy
of answers obtained from the crowd workers for quadruplet queries. For all
datasets, average accuracy of quadruplet queries is more than $0.83$ and the
accuracy is minimum whenever both pairs of records belong to the same bucket
(as low as $0.5$). However, we observe varied behavior across datasets as the
distance between considered pairs increases.

For the caltech dataset, we observe that when the ratio of the distances is
more than $1.45$ (indicated by a black line in the Figure 4(a)) , there is no
noise (or close to zero noise) observed in the query responses. As we observe
a sharp decline in noise as the distance between the pairs increases, it
suggests that adversarial noise is satisfied for this dataset. We observe a
similar pattern for the cities and monuments datasets. For the amazon dataset,
we observe that there is substantial noise across all distance ranges (See
Figure 4(b)) rather than a sharp decline, suggesting that the probabilistic
model is satisfied.

####  6.2.2. Comparison with pairwise querying mechanisms

To evaluate the benefit of quadruplet queries, we compare the quality of
quadruplet comparison oracle answers with the following pairwise oracle query
models. (a) Optimal cluster query: This query asks questions of type ‘do $u$
and $v$ refer to same/similar type?’. (b) Distance query: How similar are the
records $x$ and $y$? In this query, the annotator scores the similarity of the
pair within $1$ to $10$.

We make the following observations. (i) Optimal cluster queries are answered
correctly only if the ground truth clusters refer to different entities (each
cluster referring to a distinct entity). Crowd workers tend to answer ‘No’ if
the pair of records refer to different entities. Therefore, we observe high
precision (more than $0.90$) but low recall ($0.50$ on amazon and $0.30$ on
caltech for $k=10$) of the returned labels. (ii) We observed very high
variance in the distance estimation query responses. For all record pairs with
identical entities, the users returned distance estimates that were within
$20\%$ of the correct distances. In all other cases, we observe the estimates
to have errors of upto $50\%$. We provide more detailed comparison on the
quality of clusters identified by pairwise query responses along with
quadruplet queries in the next section.

(a) Farthest,higher is better (b) Nearest Neighbor (NN), lower is better

Figure 5. Comparison of farthest and NN techniques for crowdsourced oracle
queries.

###  6.3. Crowd Oracle: Solution Quality & Query Complexity

In this section, we compare the quality of our proposed techniques for the
datasets on which we performed the user study. Following the findings of
Section 6.2, we use probabilistic model based algorithm for amazon (with
$p=0.50$) and adversarial noise model based algorithm for caltech, monuments
and cities.

Figure 6. $k$-center clustering objective comparison for adversarial and
probabilistic noise model.

Finding Max and Farthest/Nearest Neighbor. Figure 5 compares the quality of
farthest and nearest neighbor (NN) identified by proposed techniques along
with other baselines. The values are normalized according to the maximum value
to present all datasets on the same scale. Across all datasets, the point
identified by Far and NN is closest to the optimal value, TDist. In contrast,
the farthest returned by Tour2 is better than that of Samp for cities dataset
but not for caltech, monuments and amazon. We found that this difference in
quality across datasets is due to varied distance distribution between pairs.
The cities dataset has a skewed distribution of distance between record pairs,
leading to a unique optimal solution to the farthest/NN problem. Due to this
reason, the set of records sampled by Samp does not contain any record that is
a good approximation of the optimal farthest. However, ground truth distances
between record pairs in amazon, monuments and caltech are less skewed with
more than $\log n$ records satisfying the optimal farthest point for all
queries. Therefore, Samp performs better than Tour2 on these datasets. We
observe Samp performs worse for NN because our sample does not always contain
the closest point.

$k$-center Clustering. We evaluate the F-score222Optimal clusters are
identified from the original source of the datasets (amazon and caltech) and
manually for monuments. of the clusters generated by our techniques along with
baselines and techniques for pairwise optimal query mechanism (denoted as
Oq)333 We report the results on the sample of queries asked to the crowd as
opposed to training a classifier because the classifier generates noisier
results and has poorer F-score than the quality of labels generated by
crowdsourcing. Table 1 presents the summary of our results for different
values of $k$. Across all datasets, our technique achieves more than $0.90$
F-score. On the other hand, Tour2 and Samp do not identify the ground truth
clusters correctly, leading to low F-score. Similarly, Oq achieves poor recall
(and hence low F-score) as it labels many record pairs to belong to separate
clusters. For example, a frog and a butterfly belong to the same optimal
cluster for caltech (k=10) but the two records are assigned to different
clusters by Oq.

(a) Single Linkage (b) Complete Linkage

Figure 7. Comparison of Hierarchical clustering techniques with crowdsourced
oracle.

Hierarchical Clustering. Figure 7 compares the average distance of the merged
clusters across different iterations of the agglomerative clustering
algorithm. Tour2 has $O(n^{3})$ complexity and does not run for cities dataset
in less than $48$ hrs. The objective value of different techniques are
normalized by the optimal value with Tdist denoting $1$. For all datasets, HC
performs better than Samp and Tour2. Among datasets, the quality of
hierarchies generated for monuments is similar for all techniques due to low
noise.

Technique | kC | Tour2 | Samp |  Oq*
---|---|---|---|---
caltech ($k=10$) | $\mathbf{1}$ | $0.88$ | $0.91$ | $0.45$
caltech ($k=15$) | $\mathbf{1}$ | $0.89$ | $0.88$ | $0.49$
caltech ($k=20$) | $\mathbf{0.99}$ | $0.93$ | $0.87$ | $0.58$
monuments ($k=5$) | $\mathbf{1}$ | $0.95$ | $0.97$ | 0.77
amazon ($k=7$) | $\mathbf{0.96}$ | $0.74$ | $0.57$ | $0.48$
amazon ($k=14$) | $\mathbf{0.92}$ | $0.66$ | $0.54$ | $0.72$
Table 1.  F-score comparison of k-center clustering. Oq is marked with $*$ as
it was computed on a sample of $150$ pairwise queries to the crowd3. All other
techniques were run on the complete dataset using a classifier.

Query Complexity. To ensure scalability, we trained active learning based
classifier for all the aforementioned experiments. In total, amazon, cities,
and caltech required $540$ (cost: $\$32.40$), $220$ (cost: $\$13.20$) and
$280$ (cost: $\$16.80$) queries to the crowd respectively.

###  6.4. Simulated Oracle: Solution Quality & Query Complexity

In this section, we compare the robustness of the techniques where the query
response is simulated synthetically for given $\mu$ and $p$.

Finding Max and Farthest/Nearest Neighbor. In Figure 8(a), $\mu=0$ denotes the
setting where the oracle answers all queries correctly. In this case, Far and
Tour2 identify the optimal solution but Samp does not identify the optimal
solution for cities. In both datasets, Far identifies the correct farthest
point for $\mu<1$. Even with an increase in noise ($\mu$), we observe that the
farthest is always at a distance within $4$ times the optimal distance (See
Fig 8(a)). We observe that the quality of farthest identified by Tour2 is
close to that of Far for smaller $\mu$ because the optimal farthest point
$v_{\text{max}}$ has only a few points in the confusion region $C$ (See
Section 3) that contains the points that are close to $v_{\text{max}}$. For
e.g., less than $10\%$ are present in $C$ when $\mu=1$ for cities dataset,
i.e., less than $10\%$ points return erroneous answer when compared with
$v_{\text{max}}$.

(a) cities–Adversarial  (b) cities–Probabilistic

Figure 8. Comparison of farthest identification techniques for adversarial and
probabilistic noise models.

In Figure 8(b), we compare the true distance of the identified farthest points
for the case of probabilistic noise with error probability $p$. We observe
that Farp identifies points with distance values very close to the farthest
distance Tdist, across all data sets and error values. This shows that Far
performs significantly better than the theoretical approximation presented in
Section 3. On the other hand, the solution returned by Samp is more than
$4\times$ smaller than the value returned by Farp for an error probability of
$0.3$. Tour2 has a similar performance as that of Farp for $p\leq 0.1$, but we
observe a decline in solution quality for higher noise ($p$) values.

In Figures 9(a), 9(b), we compare the true distance of the identified nearest
neighbor with different baselines.

NN shows superior performance as compared to Tour2 across all error values.
This justifies the lack of robustness of Tour2 as discussed in Section 3. The
solution quality of NN does not worsen with increase in error. We omit Samp
from the plots because the returned points had very poor performance (as bad
as 700 even in the absence of error). We observed similar behavior for other
datasets. In terms of query complexity, NN requires around $53\times 10^{3}$
queries for cities dataset and the number of queries grow linearly with the
dataset size. Among baselines, Tour2 uses $37\times 10^{3}$ queries and Samp
uses $18\times 10^{3}$.

(a) cities–Adversarial (b) cities–Probabilistic

Figure 9.  Comparison of nearest neighbor techniques for adversarial and
probabilistic noise model (lower is better).

“In conclusion, we observe that our techniques achieve the best quality across
all data sets and error values, while Tour2 performs similar to Far for low
error, and its quality degrades with increasing error."

$k$-center Clustering. Figure 6 compares the $k$-center objective of the
returned clusters for varying $k$ in the adversarial and probabilistic noise
model. Tdist denotes the best possible clustering objective, which is
guaranteed to be a 2-approximation of the optimal objective. The set of
clusters returned by kC are consistently very close to TDist across all
datasets, validating the theory. For higher values of $k$, kC approaches
closer to TDist, thereby improving the approximation guarantees. The quality
of clusters identified by kC are similar to that of Tour2 and Far for
adversarial noise (Figure 6a,b) but considerably better for probabilistic
noise (Figure 6c,d).

Running time. Table 2 compares the running time and the number of required
quadruplet comparisons for various problems under adversarial noise model with
$\mu=1$ for the largest dblp dataset. Far and NN requires less than $6$
seconds for both adversarial and probabilistic error models. Our $k$-center
clustering technique requires less than 450 min to identify $50$ centers for
dblp dataset across different noise models; the running time grows linearly
with $k$. While the running time of our algorithms are slightly higher than
Tour2 for farthest, nearest and $k$-center, Tour2 did not finish in $48$ hrs
due to $O(n^{3})$ running time for single and complete linkage hierarchical
clustering. We observe similar performance for the probabilistic noise model.
Note that even though the number of comparisons are in millions, this dataset
requires only $740$ queries to the crowd workers to train the classifier.

Problem | Our Approach | Tour2 | Samp
---|---|---|---
| Time | # Comp | Time | # Comp | Time | # Comp
Farthest | 0.1 | 2.2M | 0.06 | 2M | 0.07 | 1M
Nearest | 0.075 | 2M | 0.07 | 2M | 0.61 | 1M
kC (k=50) | 450 | 120M | 375.3 | 95M | 477 | 105M
Single Linkage | 1813 | 990M | DNF | 1760 | 940M
Complete Linkage | 1950 | 940M | DNF | 1940 | 920M
Table 2. Running time (in minutes) and number of quadruplet comparisons
(denoted by # Comp, in millions) of different techniques for dblp dataset
under the adversarial noise model with $\mu=1$. DNF denotes ‘did not finish’.

##  7\. Conclusion

In this paper, we show how algorithms for various basic tasks such as finding
maximum, nearest neighbor, $k$-center clustering, and agglomerative
hierarchical clustering can be designed using distance based comparison oracle
in presence of noise. We believe our techniques can be useful for other
clustering tasks such as $k$-means and $k$-median, and we leave those as
future work.

## References

  * [1] Google vision api https://cloud.google.com/vision.
  * [2] United states cities database.  https://simplemaps.com/data/us-cities.
  * [3] Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar.  Approximate clustering with same-cluster queries.  In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94, page 40. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.
  * [4] Miklós Ajtai, Vitaly Feldman, Avinatan Hassidim, and Jelani Nelson.  Sorting and selection with imprecise comparisons.  In International Colloquium on Automata, Languages, and Programming, pages 37–48. Springer, 2009.
  * [5] Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya.  Hd-index: pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces.  Proceedings of the VLDB Endowment, 11(8):906–919, 2018.
  * [6] Hassan Ashtiani, Shrinu Kushagra, and Shai Ben-David.  Clustering with same-cluster queries.  In Advances in neural information processing systems, pages 3216–3224, 2016.
  * [7] Shai Ben-David.  Clustering-what both theoreticians and practitioners are doing wrong.  In Thirty-Second AAAI Conference on Artificial Intelligence, 2018\.
  * [8] Mark Braverman, Jieming Mao, and S Matthew Weinberg.  Parallel algorithms for select and partition with noisy comparisons.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 851–862, 2016.
  * [9] Mark Braverman and Elchanan Mossel.  Noisy sorting without resampling.  In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 268–276. Society for Industrial and Applied Mathematics, 2008.
  * [10] Marco Bressan, Nicolò Cesa-Bianchi, Andrea Paudice, and Fabio Vitale.  Correlation clustering with adaptive similarity queries.  In Advances in Neural Information Processing Systems, pages 12510–12519, 2019.
  * [11] Vaggos Chatziafratis, Rad Niazadeh, and Moses Charikar.  Hierarchical clustering with structural constraints.  arXiv preprint arXiv:1805.09476, 2018.
  * [12] I Chien, Chao Pan, and Olgica Milenkovic.  Query k-means clustering and the double dixie cup problem.  In Advances in Neural Information Processing Systems, pages 6649–6658, 2018.
  * [13] Tuhinangshu Choudhury, Dhruti Shah, and Nikhil Karamchandani.  Top-m clustering with a noisy oracle.  In 2019 National Conference on Communications (NCC), pages 1–6. IEEE, 2019.
  * [14] Eleonora Ciceri, Piero Fraternali, Davide Martinenghi, and Marco Tagliasacchi.  Crowdsourcing for top-k query processing over uncertain data.  IEEE Transactions on Knowledge and Data Engineering, 28(1):41–53, 2015.
  * [15] Susan Davidson, Sanjeev Khanna, Tova Milo, and Sudeepa Roy.  Top-k and clustering with noisy comparisons.  ACM Trans. Database Syst., 39(4), December 2015.
  * [16] Eyal Dushkin and Tova Milo.  Top-k sorting under partial order information.  In Proceedings of the 2018 International Conference on Management of Data, pages 1007–1019, 2018.
  * [17] Ehsan Emamjomeh-Zadeh and David Kempe.  Adaptive hierarchical clustering using ordinal queries.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 415–429. SIAM, 2018.
  * [18] Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal.  Computing with noisy information.  SIAM Journal on Computing, 23(5):1001–1018, 1994.
  * [19] Donatella Firmani, Barna Saha, and Divesh Srivastava.  Online entity resolution using an oracle.  PVLDB, 9(5):384–395, 2016.
  * [20] Sainyam Galhotra, Donatella Firmani, Barna Saha, and Divesh Srivastava.  Robust entity resolution using random graphs.  In Proceedings of the 2018 International Conference on Management of Data, pages 3–18, 2018.
  * [21] Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna.  Sorting with recurrent comparison errors.  In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [22] Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna.  Optimal sorting with persistent comparison errors.  In 27th Annual European Symposium on Algorithms (ESA 2019), volume 144, page 49. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019\.
  * [23] Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna.  Optimal dislocation with persistent errors in subquadratic time.  Theory of Computing Systems, 64(3):508–521, 2020.
  * [24] Debarghya Ghoshdastidar, Michaël Perrot, and Ulrike von Luxburg.  Foundations of comparison-based hierarchical clustering.  In Advances in Neural Information Processing Systems, pages 7454–7464, 2019.
  * [25] Yogesh Girdhar and Gregory Dudek.  Efficient on-line data summarization using extremum summaries.  In 2012 IEEE International Conference on Robotics and Automation, pages 3490–3496. IEEE, 2012.
  * [26] Chaitanya Gokhale, Sanjib Das, AnHai Doan, Jeffrey F Naughton, Narasimhan Rampalli, Jude Shavlik, and Xiaojin Zhu.  Corleone: Hands-off crowdsourcing for entity matching.  In Proceedings of the 2014 ACM SIGMOD international conference on Management of data, pages 601–612, 2014.
  * [27] Teofilo F Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293–306, 1985.
  * [28] Kasper Green Larsen, Michael Mitzenmacher, and Charalampos Tsourakakis.  Clustering with a faulty oracle.  In Proceedings of The Web Conference 2020, WWW ’20, page 2831–2834, New York, NY, USA, 2020. Association for Computing Machinery.
  * [29] Gregory Griffin, Alex Holub, and Pietro Perona.  Caltech-256 object category dataset.  2007\.
  * [30] Stephen Guo, Aditya Parameswaran, and Hector Garcia-Molina.  So who won? dynamic max discovery with the crowd.  In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 385–396, 2012.
  * [31] Ruining He and Julian McAuley.  Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering.  In proceedings of the 25th international conference on world wide web, pages 507–517, 2016.
  * [32] Max Hopkins, Daniel Kane, Shachar Lovett, and Gaurav Mahajan.  Noise-tolerant, reliable active classification with comparison queries.  arXiv preprint arXiv:2001.05497, 2020.
  * [33] Wasim Huleihel, Arya Mazumdar, Muriel Médard, and Soumyabrata Pal.  Same-cluster querying for overlapping clusters.  In Advances in Neural Information Processing Systems, pages 10485–10495, 2019.
  * [34] Christina Ilvento.  Metric learning for individual fairness.  arXiv preprint arXiv:1906.00250, 2019.
  * [35] Ehsan Kazemi, Lin Chen, Sanjoy Dasgupta, and Amin Karbasi.  Comparison based learning from weak oracles.  arXiv preprint arXiv:1802.06942, 2018.
  * [36] Taewan Kim and Joydeep Ghosh.  Relaxed oracles for semi-supervised clustering.  arXiv preprint arXiv:1711.07433, 2017.
  * [37] Taewan Kim and Joydeep Ghosh.  Semi-supervised active clustering with weak oracles.  arXiv preprint arXiv:1709.03202, 2017.
  * [38] Rolf Klein, Rainer Penninger, Christian Sohler, and David P Woodruff.  Tolerant algorithms.  In European Symposium on Algorithms, pages 736–747. Springer, 2011\.
  * [39] Matthäus Kleindessner, Pranjal Awasthi, and Jamie Morgenstern.  Fair k-center clustering for data summarization.  In International Conference on Machine Learning, pages 3448–3457, 2019.
  * [40] Ngai Meng Kou, Yan Li, Hao Wang, Leong Hou U, and Zhiguo Gong.  Crowdsourced top-k queries by confidence-aware pairwise judgments.  In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1415–1430, 2017.
  * [41] Blake Mason, Ardhendu Tripathy, and Robert Nowak.  Learning nearest neighbor graphs from noisy distance samples.  In Advances in Neural Information Processing Systems, pages 9586–9596, 2019.
  * [42] Arya Mazumdar and Barna Saha.  Clustering with noisy queries.  In Advances in Neural Information Processing Systems, pages 5788–5799, 2017.
  * [43] Arya Mazumdar and Barna Saha.  Query complexity of clustering with side information.  In Advances in Neural Information Processing Systems, pages 4682–4693, 2017.
  * [44] George Papadakis, Jonathan Svirsky, Avigdor Gal, and Themis Palpanas.  Comparative analysis of approximate blocking techniques for entity resolution.  Proceedings of the VLDB Endowment, 9(9):684–695, 2016.
  * [45] Vassilis Polychronopoulos, Luca De Alfaro, James Davis, Hector Garcia-Molina, and Neoklis Polyzotis.  Human-powered top-k lists.  In WebDB, pages 25–30, 2013.
  * [46] Dražen Prelec, H Sebastian Seung, and John McCoy.  A solution to the single-question crowd wisdom problem.  Nature, 541(7638):532–535, 2017.
  * [47] Robin Sibson.  Slink: an optimally efficient algorithm for the single-link cluster method.  The computer journal, 16(1):30–34, 1973.
  * [48] Omer Tamuz, Ce Liu, Serge Belongie, Ohad Shamir, and Adam Tauman Kalai.  Adaptively learning the crowd kernel.  In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 673–680, 2011.
  * [49] Antti Ukkonen.  Crowdsourced correlation clustering with relative distance comparisons.  In 2017 IEEE International Conference on Data Mining (ICDM), pages 1117–1122. IEEE, 2017.
  * [50] https://modal-python.readthedocs.io/en/latest/.  modal library.
  * [51] https://scikit-learn.org/stable/.  Scikit-learn.
  * [52] Vijay V Vazirani.  Approximation algorithms.  Springer Science & Business Media, 2013.
  * [53] Petros Venetis, Hector Garcia-Molina, Kerui Huang, and Neoklis Polyzotis.  Max algorithms in crowdsourcing environments.  In Proceedings of the 21st international conference on World Wide Web, pages 989–998, 2012.
  * [54] Victor Verdugo.  Skyline computation with noisy comparisons.  In Combinatorial Algorithms: 31st International Workshop, IWOCA 2020, Bordeaux, France, June 8–10, 2020, Proceedings, page 289. Springer.
  * [55] Vasilis Verroios and Hector Garcia-Molina.  Entity resolution with crowd errors.  In 2015 IEEE 31st International Conference on Data Engineering, pages 219–230. IEEE, 2015.
  * [56] Norases Vesdapunt, Kedar Bellare, and Nilesh Dalvi.  Crowdsourcing algorithms for entity resolution.  Proceedings of the VLDB Endowment, 7(12):1071–1082, 2014.
  * [57] Ramya Korlakai Vinayak and Babak Hassibi.  Crowdsourced clustering: Querying edges vs triangles.  In Advances in Neural Information Processing Systems, pages 1316–1324, 2016.
  * [58] Jiannan Wang, Tim Kraska, Michael J Franklin, and Jianhua Feng.  Crowder: Crowdsourcing entity resolution.  Proceedings of the VLDB Endowment, 5(11), 2012.
  * [59] David P Williamson and David B Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.
  * [60] Chao Zhang, Fangbo Tao, Xiusi Chen, Jiaming Shen, Meng Jiang, Brian Sadler, Michelle Vanni, and Jiawei Han.  Taxogen: Unsupervised topic taxonomy construction by adaptive term embedding and clustering.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2701–2709, 2018.

##  8\. Finding Maximum

###### Lemma 8.1.

(Hoeffding’s Inequality) If $X_{1},X_{2},\cdots,X_{n}$ are independent random
variables with $a_{i}\leq X_{i}\leq b_{i}$ for all $i\in[n]$, then

$\Pr\left[\left|\sum_{i}X_{i}-\operatorname*{{\bf{E}}}[X_{i}]\right|\geq
n\epsilon\right]\leq
2\exp\left(-\frac{2n^{2}\epsilon^{2}}{\sum_{i}(b_{i}-a_{i})^{2}}\right)$

###  8.1. Adversarial Noise

Let the maximum value among $V$ be denoted by $v_{\text{max}}$ and the set of
records for which the oracle answer can be incorrect is given by

$C=\\{u\mid u\in V,u\geq\frac{v_{\text{max}}}{1+\mu}\\}$

###### Claim 8.2.

For any partition $V_{i}$, $\textsc{Tournament}(V_{i})$ uses at most
$2|V_{i}|$ oracle queries.

###### Proof.

Consider the $i$th round in Tournament. We can observe that the number of
remaining values is at most $\frac{|V_{i}|}{2^{i}}$. So, we make
$\frac{|V_{i}|}{2^{i+1}}$ many oracle queries in this round. Total number of
oracle queries made is

$\sum_{i=0}^{\log n}\frac{|V_{i}|}{2^{i+1}}\leq 2|V_{i}|$

∎

###### Lemma 8.3.

Given a set of values $S$, $\textsc{Count-Max}(S)$ returns a $(1+\mu)^{2}$
approximation of maximum value of $S$ using $O(|S|^{2})$ oracle queries.

###### Proof.

Let $v_{\text{max}}=\max\\{x\in S\\}$. Consider a value $w\in S$ such that
$w<\frac{v_{\text{max}}}{(1+\mu)^{2}}$. We compare the Count values for
$v_{\text{max}}$ and $w$ given by,
$\texttt{Count}(v_{\text{max}},S)=\sum_{x\in
S}1\\{\operatorname*{\mathcal{O}}(v_{\text{max}},x)==\texttt{No}{}\\}$ and
$\texttt{Count}(w,S)=\sum_{x\in
S}1\\{\operatorname*{\mathcal{O}}(w,x)==\texttt{No}{}\\}$. We argue that $w$
can never be returned by Algorithm 1, i.e.,
$\texttt{Count}(w,S)<\texttt{Count}(v_{\text{max}},S)$.

$\displaystyle\texttt{Count}(v_{\text{max}},S)=\sum_{x\in
S}1\\{\operatorname*{\mathcal{O}}(v_{\text{max}},x)==\texttt{No}{}\\}$
$\displaystyle\geq\sum_{x\in
S\setminus\\{v_{\text{max}}\\}}1\\{x<v_{\text{max}}/(1+\mu)\\}$
$\displaystyle={1}\\{\operatorname*{\mathcal{O}}(v_{\text{max}},w)==\texttt{No}\\}\
\ +\sum_{x\in
S\setminus\\{v_{\text{max}},w\\}}1\\{x<v_{\text{max}}/(1+\mu)\\}$
$\displaystyle=1+\sum_{x\in
S\setminus\\{v_{\text{max}},w\\}}1\\{x<v_{\text{max}}/(1+\mu)\\}$
$\displaystyle\texttt{Count}(w,S)=\sum_{y\in
S}1\\{\operatorname*{\mathcal{O}}(w,y)==\texttt{No}{}\\}$
$\displaystyle=\sum_{y\in
S\setminus\\{w,v_{\text{max}}\\}}{1}\\{\operatorname*{\mathcal{O}}(w,y)==\texttt{No}\\}$
$\displaystyle\leq\sum_{y\in
S\setminus\\{w,v_{\text{max}}\\}}1\\{y\leq(1+\mu)w\\}$
$\displaystyle\leq\sum_{y\in
S\setminus\\{w,v_{\text{max}}\\}}1\\{y\leq{v_{\text{max}}}/{(1+\mu)}\\}$

Combining the two, we have :

$\texttt{Count}(v_{\text{max}},S)>\texttt{Count}(w,S)$

This shows that the Countof $v_{\text{max}}$ is strictly greater than the
count of any point $w$ with $w<\frac{v_{\text{max}}}{(1+\mu)^{2}}$. Therefore,
our algorithm would have output $v_{\text{max}}$ instead of $w$. For
calculating the Count for all values in $S$, we make at most $|S|^{2}$ oracle
queries as we compare every value with every other value. Finally, we output
the maximum value as the value with highest Count. Hence, the claim. ∎

###### Lemma 8.4 (Lemma 3.3 restated).

Suppose $v_{max}$ is the maximum value among the set of records $V$. Algorithm
2 outputs a value $u_{max}$ such that
$u_{max}\geq\frac{v_{max}}{(1+\mu)^{2\log_{\lambda}n}}$ using $O(n\lambda)$
oracle queries.

###### Proof.

From Lemma 8.3, we have that we lose a factor of $(1+\mu)^{2}$ in each level
of the tournament tree, we have that after $\log_{\lambda}n$ levels, the final
output will have an approximation guarantee of $(1+\mu)^{2\log_{\lambda}n}$.
The total number of queries used is given by :
$\sum_{i=0}^{\log_{\lambda}n}\frac{|V_{i}|}{\lambda}\lambda^{2}=O(n\lambda)$
where $V_{i}$ is the number of records at level $i$. ∎

###### Lemma 8.5.

Suppose $|C|>\sqrt{n}/2$. Let $\widetilde{V}$ denote a set of
$2\sqrt{n}\log(2/\delta)$ samples obtained by uniform sampling with
replacement from $V$. Then, $\widetilde{V}$ contains a $(1+\mu)$ approximation
of the maximum value $v_{\text{max}}$, with probability $1-\delta/2$.

###### Proof.

Consider the first step where we use a uniformly random sample $\widetilde{V}$
of $\sqrt{n}t=2\sqrt{n}\log(2/\delta)$ values from $V$ (obtained by sampling
with replacement). Given $|C|\geq\frac{\sqrt{n}}{2}$, probability that
$\widetilde{V}$ contains a value from $C$ is given by

$\Pr[\widetilde{V}\cap
C\neq\phi]=1-\left(1-\frac{|C|}{n}\right)^{|\widetilde{V}|}>1-\left(1-\frac{1}{2\sqrt{n}}\right)^{2\sqrt{n}\log(2/\delta)}>1-\delta/2$

So, with probability $1-\delta/2$, there exists a value $u\in
C\cap\widetilde{V}$. Hence, the claim. ∎

###### Lemma 8.6.

Suppose the partition $V_{i}$ contains the maximum value $v_{\text{max}}$ of
$V$. If $|C|\leq{\sqrt{n}}/2$, then, $\textsc{Tournament}(V_{i})$ returns the
$v_{\text{max}}$ with probability $1/2$.

###### Proof.

Algorithm 4 uses a modified tournament tree that partitions the set $V$ into
$l=\sqrt{n}$ parts of size $\frac{n}{l}=\sqrt{n}$ each and identifies a
maximum $p_{i}$ from each partition $V_{i}$ using Algorithm 2. If
$v_{\text{max}}\in V_{i}$, then,

$\operatorname*{{\bf{E}}}[|C\cap
V_{i}|]=\frac{|C|}{l}=\frac{\sqrt{n}}{2\sqrt{n}}=\frac{1}{2}$

Using Markov’s inequality, the probability that $V_{i}$ contains a value from
$C$ is given by :

$\Pr[|C\cap V_{i}|\geq 1]\leq\operatorname*{{\bf{E}}}[|C\cap
V_{i}|]\leq\frac{1}{2}$

Therefore, with at least a probability of $\frac{1}{2}$, $v_{\text{max}}$ will
never be compared with any point from $C$ in the partition $V_{i}$ containing
$v_{\text{max}}$. Hence, $v_{\text{max}}$ is returned by
$\textsc{Tournament}(V_{i})$ with probability $1/2$.

∎

###### Lemma 8.7 (Lemma 3.5 restated).

  1. (1)

If $|C|>{\sqrt{n}}/{2}$, then there exists a value $v_{j}\in\widetilde{V}$
satisfying $v_{j}\geq{v_{\text{max}}}/{(1+\mu)}$ with a probability of
$1-\delta/2$.

  2. (2)

Suppose $|C|\leq{\sqrt{n}}/{2}$. Then, $T$ contains $v_{\text{max}}$ with a
probability at least $1-\delta/2$.

###### Proof.

Claim (1) follows from Lemma 8.5.

In every iteration $i\leq t$ of Algorithm 4, we have that $v_{\text{max}}\in
T_{i}$ with probability $\frac{1}{2}$ (Using Lemma 8.6). To increase the
success probability, we run this procedure $t$ times and obtain all the
outputs. Among the $t=2\log(2/\delta)$ runs of Algorithm 2, we have that
$v_{\text{max}}$ is never compared with any value of $C$ in atleast one of the
iterations with a probability at least

$1-\left(1-1/2\right)^{2\log(2/\delta)}\geq 1-\frac{\delta}{2}$

Hence, $T=\cup_{i}T_{i}$ contains $v_{\text{max}}$ with a probability
$1-\frac{\delta}{2}$. ∎

###### Theorem 8.8 (Theorem 3.6 restated).

Given a set of values $V$, Algorithm 4 returns a $(1+\mu)^{3}$ approximation
of maximum value with probability $1-\delta$ using $O(n\log^{2}(1/\delta))$
oracle queries.

###### Proof.

In Algorithm 4, we first identify an approximate maximum value using Sampling.
If $|C|\geq\frac{\sqrt{n}}{2}$, then, from Lemma 8.5, we have that the value
returned is a $(1+\mu)$ approximation of the maximum value of $V$. Othwerwise,
from Lemma 8.7, $T$ contains $v_{\text{max}}$ with a probability $1-\delta/2$.
As we use Count-Max on the set $\widetilde{V}\cup T$, we know that the value
returned, i.e., $u_{\text{max}}$ is a $(1+\mu)^{2}$ of the maximum among
values from $\widetilde{V}\cup T$. Therefore,
$u_{\text{max}}\geq\frac{v_{\text{max}}}{(1+\mu)^{3}}$. Using union bound, the
total probability of failure is $\delta$.

For query complexity, Algorithm 3 obtains a set $\widetilde{V}$ of $\sqrt{n}t$
sample values. Along with the set $T$ obtained (where $|T|=\frac{nt}{l}$), we
use Count-Max on $\widetilde{V}\cup T$ to output the maximum $u_{\text{max}}$.
This step requires $O(|\widetilde{V}\cup
T|^{2})=O((\sqrt{n}t+\frac{nt}{l})^{2})$ oracle queries. In an iteration $i$,
for obtaining $T_{i}$, we make $O(\sum_{j}|V_{j}|)=O(n)$ oracle queries (Claim
8.2), and for $t$ iterations, we make $O(nt)$ queries. Using
$t=2\log(2/\delta),l=\sqrt{n}$, in total, we make
$O(nt+(\sqrt{n}t+\frac{nt}{l})^{2})=O(n\log^{2}(1/\delta))$ oracle queries.
Hence, the theorem.

∎

###  8.2. Probabilistic Noise

###### Lemma 8.9.

Suppose the maximum value $u_{\text{max}}$ is returned by Algorithm 2 with
parameters $(V,n)$. Then,
$\textrm{rank}(u_{\text{max}},V)=O(\sqrt{n\log(1/\delta)})$ with a probability
of $1-\delta$.

###### Proof.

We have for the maximum value $v_{\text{max}}$, expected count value :

$\displaystyle\operatorname*{{\bf{E}}}[\texttt{Count}(v_{\text{max}},V)]=\sum_{w\in
V}\mathbf{1}\\{\operatorname*{\mathcal{O}}(w,v_{\text{max}})==w\\}=(n-1)(1-p)$

Using Hoeffding’s inequality, with probability $1-\delta/2$ :

$\displaystyle\texttt{Count}(v_{\text{max}},V)\geq(n-1)(1-p)-\sqrt{((n-1)\log(2/\delta))/2}$

Consider a record $u\in V$ with rank at most $5\sqrt{2n\log(2/\delta)}$. Then,

$\displaystyle\operatorname*{{\bf{E}}}[\texttt{Count}(u,V)]$
$\displaystyle=\sum_{w\in
V}\mathbf{1}\\{\operatorname*{\mathcal{O}}(u,v_{\text{max}})==w\\}=(n-\textrm{rank}(u))(1-p)+(\textrm{rank}(u)-1)p$

Using Hoeffding’s inequality, with probability $1-\delta/2$ :

$\displaystyle\texttt{Count}(u,V)$
$\displaystyle<(n-1)(1-p)-(\textrm{rank}(u)-1)(1-2p)+\sqrt{0.5(n-1)\log(2/\delta)}$
$\displaystyle<(n-1)(1-p)-(5\sqrt{2n\log(2/\delta)}-1)(1-2p)+\sqrt{0.5(n-1)\log(2/\delta)}$
$\displaystyle<\texttt{Count}(v_{\text{max}},V)$

The last inequality is true for a value of $p\leq 0.4$. As Algorithm 2 returns
the record $u_{\text{max}}$ with maximum Count value, we have that
rank$(u_{\text{max}},V)=O(\sqrt{n\log(1/\delta)})$. Using union bound, for the
above conditions to be met, we have the claim. ∎

To improve the query complexity, we use an early stopping criteria that
discards a value $x$ using the $\texttt{Count}(x,V)$ when it determines that
$x$ has no chance of being the maximum. Algorithm 12 presents the psuedocode
for this modified count calculation. We sample $100\log(n/\delta)$ values
randomly, denoted by $S_{t}$ and compare every non-sampled point with $S_{t}$.
We argue that by doing so, it helps us eliminate the values that are far away
from the maximum in the sorted ranking. Using Algorithm 12, we compare the
Count scores with respect to $S_{t}$ of a value $u\in V\setminus S_{t}$ and if
$\texttt{Count}(u,S_{t})\geq 50\log(n/\delta)$, we make it available for the
subsequent iterations.

1:Input : A set $V$ of $n$ values, failure probability $\delta$.

2:Output : An approximate maximum value of $V$

3:$t\leftarrow 1$

4:while $t<\log(n)$ or $|V|>100\log(n/\delta)$ do

5: $S_{t}$ denote a set of $100\log(n/\delta)$ values obtained by sampling
uniformly at random from $V$ with replacement.

6: Set $X\leftarrow\phi$

7: for $u\in V\setminus S_{t}$ do

8: if $\texttt{Count}(u,S_{t})\geq 50\log(n/\delta)$ then

9: $X\leftarrow X\cup\\{u\\}$

10: $V\leftarrow X,t\leftarrow t+1$

11:$u_{\text{max}}\leftarrow\textsc{Count-Max}(V)$

12:return $u_{\text{max}}$

Algorithm 12 Count-Max-Prob : Maximum with Probabilistic Noise

As Algorithm 12 considers each value $u\in V\setminus S_{t}$ by iteratively
comparing it with each value $x\in S_{t}$ and the error probability is less
than $p$, the expected count of $v_{\text{max}}$ (if it is available) at any
iteration $t$ is $(1-p)|S_{t}|$. Accounting for the deviation around the
expected value, we have that the $\texttt{Count}(v_{\text{max}},S_{t})$ is at
least $50\log(n/\delta)$ when $p\leq 0.4$444The constants $50$, $100$ etc. are
not optimized and set just to satisfy certain concentration bounds.. If a
particular value $u$ has $\texttt{Count}(u,S_{t})<50\log(n/\delta)$ in any
iteration, i.e., then it can not be the largest value in $V$ and therefore, we
remove it from the set of possible candidates for maximum. Therefore, any
value that remains in $V$ after an iteration $t$, must have rank closer to
that of $v_{\text{max}}$. We argue that after every iteration, the number of
candidates remaining is at most $1/60$th of the possible candidates.

###### Lemma 8.10.

In an iteration $t$ containing $n_{t}$ remaining records, using Algorithm 5,
with probability $1-\delta/n$, we discard at least $\frac{59}{60}\cdot n_{t}$
records.

###### Proof.

Consider an iteration $t$ which has $n_{t}$ remaining records. Algorithm 5 and
a record $u$ with rank $\alpha\cdot n_{t}$. Now, we have :

$\operatorname*{{\bf{E}}}[\texttt{Count}(u,S_{t})]=((1-\alpha)(1-p)+\alpha
p)100\log(n/\delta)$

For $\alpha=0$, i.e., we have for maximum value $v_{\text{max}}$

$\operatorname*{{\bf{E}}}[\texttt{Count}(v_{\text{max}},S_{t})]=(1-p)100\log(n/\delta)$

Using $p\leq 0.4$ and Hoeffding’s inequality, with probability
$1-\delta/n^{2}$ , we have :

$\displaystyle\texttt{Count}(v_{\text{max}},S_{t})\geq(1-p)100\log(n/\delta)-\sqrt{100}\log(n/\delta)\geq
50\log(n/\delta)$

For $u$, we calculate the Count value. Using $p\leq 0.4$ and Hoeffding’s
inequality, with probability $1-\delta/n^{2}$ , we have :

$\displaystyle\texttt{Count}(u,S_{t})$ $\displaystyle<((1-\alpha)(1-p)+\alpha
p)100\log(n/\delta)+\sqrt{100((1-\alpha)(1-p)+\alpha p)}\log(n/\delta)$
$\displaystyle<((1-0.6\alpha)100+\sqrt{100(1-0.6\alpha)})\log(n/\delta)<50\log(n/\delta)$

Upon calculation, for $\alpha>\frac{59}{60}$, we have the above expression.
Therefore, using union bound, with probability $1-O(\delta/n)$, all records
$u$ with rank at least $\frac{59n_{t}}{60}$ satisfy :

$\texttt{Count}(u,S_{t})<\texttt{Count}(v_{\text{max}},S_{t})$

So, all such values can be removed. Hence, the claim. ∎

In the previous lemma, we argued that in every iteration, at least $1/60$th
fraction is removed and therefore in $\Theta(\log n)$ iterations, the
algorithm will terminate. In each iteration, we discard the sampled values
$S_{t}$ to ensure that there is no dependency between the Count scores, and
our guarantees hold. As we remove at most
$O(t\cdot\log(n/\delta))=O(\log^{2}(n/\delta))$ sampled points, our final
statement of the result is :

###### Lemma 8.11.

Query complexity of Algorithm 5 is $O(n\cdot\log^{2}(n/\delta))$ and
$u_{\text{max}}$ satisfies $\textrm{rank}(u_{\text{max}},V)\leq
O(\log^{2}(n/\delta))$ with probability $1-\delta$.

###### Proof.

From Lemma 8.10, we have with probability $1-\delta/n$, after iteration $t$,
at least $\frac{59n_{t}}{60}$ records removed along with the
$100\log(n/\delta)$ records that are sampled. Therefore, we have :

$n_{t+1}\leq\frac{n_{t}}{60}-100\log(n/\delta)$

After $\log(n/\delta)$ iterations, we have $n_{t+1}\leq 1$. As we have removed
$\log_{60}n\cdot 100\log(n/\delta)$ records that were sampled in total, these
could records with rank$\leq 100\log^{2}(n/\delta)$. So, the rank of
$u_{\text{max}}$ output is at most $100\log^{2}(n/\delta)$. In an iteration
$t$, the number of oracle queries calculating Count values is
$O(n_{t}\cdot\log(n/\delta))$. In total, Algorithm 5 makes
$O(n\log^{2}(n/\delta))$ oracle queries. Using union bound over
$\log(n/\delta)$ iterations, we get a total failure probability of $\delta$. ∎

###### Theorem 8.12 (Theorem 3.7 restated).

There is an algorithm that returns $u_{\text{max}}\in V$ such that
$\textrm{rank}(u_{\text{max}},V)=O(\log^{2}(n/\delta))$ with probability
$1-\delta$ and requires $O(n\log^{2}(n/\delta))$ oracle queries.

###### Proof.

The proof follows from Lemma 8.11 ∎

##  9\. Farthest and Nearest Neighbor

###### Lemma 9.1 (Lemma 3.9 restated).

Suppose $\max_{v_{i}\in S}d(u,v_{i})\leq\alpha$ and $|S|\geq 6\log(1/\delta)$.
Consider two records $v_{i}$ and $v_{j}$ such that
$d(u,v_{i})<d(u,v_{j})-2\alpha$ then $\texttt{FCount}(v_{i},v_{j})\geq 0.3|S|$
with a probability of $1-\delta$

###### Proof.

Since $d(u,v_{i})<d(u,v_{j})-2\alpha$, for a point $x\in S$,

$\displaystyle d(v_{j},x)$ $\displaystyle\geq d(u,v_{j})-d(u,x)$
$\displaystyle>d(u,v_{i})+2\alpha-d(u,x)$ $\displaystyle\geq
d(v_{i},x)-d(u,x)+2\alpha-d(u,x)$ $\displaystyle\geq
d(v_{i},x)+2\alpha-2d(u,x)$ $\displaystyle\geq d(v_{i},x)$

So, $O(v_{i},x,v_{j},x)$ is No with a probability $p$. As $p\leq 0.4$, we have
:

$\displaystyle\operatorname*{{\bf{E}}}[\texttt{FCount}(v_{i},v_{j})]$
$\displaystyle=(1-p)|S|$ $\displaystyle\Pr[\texttt{FCount}(v_{i},v_{j})\leq
0.3|S|]$ $\displaystyle\leq\Pr[\texttt{FCount}(v_{i},v_{j})\leq(1-p)|S|/2]$

From Hoeffding’s inequality (with binary random variables), we have with a
probability $\exp(-\frac{|S|(1-p)^{2}}{2})\leq\delta$ (using $|S|\geq
6\log(1/\delta)$, $p<0.4$) : $\texttt{FCount}(v_{i},v_{j})\leq(1-p)|S|/2$.
Therefore, with probability at most $\delta$, we have,
$\texttt{FCount}(v_{i},v_{j})\leq 0.3|S|$. ∎

For the sake of completeness, we restate the Count definition that is used in
Algorithm Count-Max. For every oracle comparison, we replace it with the
_pairwise comparison_ query described in Section 3.3. Let $u$ be a query point
and $S$ denote a set of $\Theta(\log(n/\delta))$ points within a distance of
$\alpha$ from $u$. We maintain a Count score for a given point $v_{i}\in V$ as
:

$\texttt{Count}(u,v_{i},S,V)=\sum_{v_{j}\in
V\setminus\\{v_{i}\\}}1\\{\textsc{Pairwise-
Comp}(u,v_{i},v_{j},S)==\texttt{No}{}\\}$

1:Input : A set of points $V$, and query point $u$ and a set $S$.

2:Output : An approximate farthest point from $u$

3:for $v_{i}\in V$ do

4: Calculate $\texttt{Count}(u,v_{i},S,V)$

5:$u_{\text{max}}\leftarrow\text{arg max}_{v\in S}\texttt{Count}(u,v_{i},S,V)$

6:return $u_{\text{max}}$

Algorithm 13 Count-Max(V) : finds the farthest point by counting in $V$

###### Lemma 9.2.

Given a query vertex $u$ and a set $S$ with $|S|=\Omega(\log(n/\delta))$ such
that $\max_{v\in S}d(u,v)\leq\alpha$. Then the farthest identified using
Algorithm 13 (with PairwiseComp), denoted by $u_{\text{max}}$ is within
$4\alpha$ distance from the optimal farthest point, i.e.,
$d(u,u_{\text{max}})\geq\max_{v\in V}d(u,v)-4\alpha$ with a probability of
$1-\delta$. Further the query complexity is $O(n^{2}\log(n/\delta))$.

###### Proof.

Let $v_{\text{max}}=\max_{v\in V}d(u,v)$. Consider a value $w\in V$ such that
$d(u,w)<d(u,v_{\text{max}})-4\alpha$. We compare the Count values for
$v_{\text{max}}$ and $w$ given by,
$\texttt{Count}(u,v_{\text{max}},S,V)=\sum_{v_{j}\in
V\setminus\\{v_{\text{max}}\\}}1\\{\textsc{Pairwise-
Comp}(u,v_{\text{max}},v_{j},S)==\texttt{No}{}\\}$ and
$\texttt{Count}(u,w,S,V)=\sum_{v_{j}\in
V\setminus\\{w\\}}1\\{\textsc{Pairwise-Comp}(u,w,v_{j},S)==\texttt{No}{}\\}$.
We argue that $w$ can never be returned by Algorithm 13, i.e.,
$\texttt{Count}(u,w,S,V)<\texttt{Count}(u,v_{\text{max}},S,V)$. Using Lemma
9.1 we have :

$\displaystyle\texttt{Count}(u,v_{\text{max}},S,V)$
$\displaystyle=\sum_{v_{j}\in
V\setminus\\{v_{\text{max}}\\}}1\\{\textsc{Pairwise-
Comp}(u,v_{\text{max}},v_{j},S)==\texttt{No}{}\\}$
$\displaystyle\geq\sum_{v_{j}\in
V\setminus\\{v_{\text{max}}\\}}1\\{d(u,v_{j})<d(u,v_{\text{max}})-2\alpha\\}$
$\displaystyle={1}\\{d(u,w)<d(u,v_{\text{max}})-2\alpha\\}\ \ +\sum_{v_{j}\in
V\setminus\\{v_{\text{max}},w\\}}1\\{d(u,v_{j})<d(u,v_{\text{max}})-2\alpha\\}$
$\displaystyle=1+\sum_{v_{j}\in
V\setminus\\{v_{\text{max}},w\\}}1\\{d(u,v_{j})<d(u,v_{\text{max}})-2\alpha\\}$
$\displaystyle\texttt{Count}(u,w,S,V)$ $\displaystyle=\sum_{v_{j}\in
V\setminus\\{w\\}}1\\{\textsc{Pairwise-Comp}(u,w,v_{j},S)==\texttt{No}{}\\}$
$\displaystyle\leq\sum_{v_{j}\in
V\setminus\\{w\\}}1\\{d(u,v_{j})<d(u,w)+2\alpha\\}$
$\displaystyle\leq\sum_{v_{j}\in
V\setminus\\{w,v_{\text{max}}\\}}1\\{d(u,v_{j})<d(u,v_{\text{max}})-2\alpha\\}$

Combining the two, we have :

$\texttt{Count}(u,v_{\text{max}},S,V)>\texttt{Count}(u,w,S,V)$

This shows that the Countof $v_{\text{max}}$ is strictly greater than the
count of any point $w$ when $d(u,w)<d(u,v_{\text{max}})-4\alpha$. Therefore,
our algorithm would have output $v_{\text{max}}$ instead of $w$. For
calculating the Count for all points in $V$, we make at most $|V|^{2}\cdot|S|$
oracle queries as we compare every point with every other point using
Algorithm 5. Finally, we output the point $u_{\text{max}}$ as the value with
highest Count. From Lemma 9.1, when $|S|=\Omega(\log(n/\delta))$, the answer
to any pairwise query is correct with a failure probability of $\delta/n^{2}$.
As there are $n^{2}$ pairwise comparisons, and each with failure probability
of $\delta/n^{2}$, from union bound, we have that that the total failure
probability is $\delta$. Hence, the claim. ∎

1:Input : Set of values $V$, Degree $\lambda$, query point $u$ and a set $S$.

2:Output : An approximate farthest point from $u$

3:Construct a balanced $\lambda$-ary tree $\mathcal{T}$ with $|V|$ nodes as
leaves.

4:Let $\pi_{V}$ be a random permutation of $V$ assigned to leaves of
$\mathcal{T}$

5:for $i=1$ to $\log_{\lambda}|V|$ do

6: for internal node $w$ at level $\log_{\lambda}|V|-i$ do

7: Let $U$ denote the children of $w$.

8: Set the internal node $w$ to $\textsc{Count-Max}(u,S,U)$

9:$u_{\text{max}}\leftarrow$ point at root of $\mathcal{T}$

10:return $u_{\text{max}}$

Algorithm 14 Tournament : finds the farthest point using a tournament tree

1:Input : Set of values $V$, number of partitions $l$, query point $u$ and a
set $S$.

2:Output : A set of farthest points from each partition

3:Randomly partition $V$ into $l$ equal parts $V_{1},V_{2},\cdots V_{l}$

4:for $i=1$ to $l$ do

5: $p_{i}\leftarrow\textsc{Tournament}(u,S,V_{i},2)$

6: $T\leftarrow T\cup\\{p_{i}\\}$

7:return $T$

Algorithm 15 Tournament-Partition

1:Input : Set of values $V$, number of iterations $t$, query point $u$ and a
set $S$.

2:Output : An approximate farthest point $u_{\text{max}}$

3:$i\leftarrow 1,T\leftarrow\phi$

4:Let $\widetilde{V}$ denote a sample of size $\sqrt{n}t$ selected uniformly
at random (with replacement) from $V$.

5:for $i\leq t$ do

6: $T_{i}\leftarrow\textsc{Tournament-Partition}(u,S,V,l)$

7: $T\leftarrow T\cup T_{i}$

8:$u_{\text{max}}\leftarrow\textsc{Count-Max}(u,S,\widetilde{V}\cup T)$

9:return $u_{\text{max}}$

Algorithm 16 Max-Prob : Maximum with Probabilistic Noise

Let the farthest point from query point $u$ among $V$ be denoted by
$v_{\text{max}}$ and the set of records for which the oracle answer can be
incorrect is given by

$C=\\{w\mid w\in V,d(u,w)\geq d(u,v_{\text{max}})-2\alpha\\}$

###### Lemma 9.3.

  1. (1)

If $|C|>{\sqrt{n}}/{2}$, then there exists a value $v_{j}\in\widetilde{V}$
satisfying $d(u,v_{j})\geq d(u,{v_{\text{max}}})-2\alpha$ with a probability
of $1-\delta/2$.

  2. (2)

Suppose $|C|\leq{\sqrt{n}}/{2}$. Then, $T$ contains $v_{\text{max}}$ with a
probability at least $1-\delta/2$.

###### Proof.

The proof is similar to Lemma 8.7. ∎

###### Theorem 9.4 (Theorem 3.10 restated).

Given a query vertex $u$ and a set $S$ with $|S|=\Omega(\log(n/\delta))$ such
that $\max_{v\in S}d(u,v)\leq\alpha$ then the farthest identified using
Algorithm 4 (with PairwiseComp), denoted by $u_{\text{max}}$ is within
$6\alpha$ distance from the optimal farthest point, i.e.,
$d(u,u_{\text{max}})\geq\max_{v\in V}d(u,v)-6\alpha$ with a probability of
$1-\delta$. Further the query complexity is $O(n\log^{3}(n/\delta))$.

###### Proof.

The proof is similar to Theorem 8.8. In Algorithm 16, we first identify an
approximate maximum value using Sampling. If $|C|\geq\frac{\sqrt{n}}{2}$,
then, from Lemma 9.3, we have that the value returned is a $2\alpha$ additive
approximation of the maximum value of $V$. Otherwise, from Lemma 9.3, $T$
contains $v_{\text{max}}$ with a probability $1-\delta/2$. As we use Count-Max
on the set $\widetilde{V}\cup T$, we know that the value returned, i.e.,
$u_{\text{max}}$ is a $4\alpha$ of the maximum among values from
$\widetilde{V}\cup T$. Therefore, $d(u,u_{\text{max}})\geq
d(u,v_{\text{max}})-6\alpha$. Using union bound over $n\cdot t$ comparisons,
the total probability of failure is $\delta$.

For query complexity, Algorithm 15 obtains a set $\widetilde{V}$ of
$\sqrt{n}t$ sample values. Along with the set $T$ obtained (where
$|T|=\frac{nt}{l}$), we use Count-Max on $\widetilde{V}\cup T$ to output the
maximum $u_{\text{max}}$. This step requires $O(|\widetilde{V}\cup
T|^{2}|S|)=O((\sqrt{n}t+\frac{nt}{l})^{2}\log(n/\delta))$ oracle queries. In
an iteration $i$, for obtaining $T_{i}$, we make
$O(\sum_{j}|V_{j}|\log(n/\delta))=O(n\log(n/\delta))$ oracle queries (Claim
8.2), and for $t$ iterations, we make $O(nt\log(n/\delta))$ queries. Using
$t=2\log(2n/\delta),l=\sqrt{n}$, in total, we make
$O(nt\log(n/\delta)+(\sqrt{n}t+\frac{nt}{l})^{2}\log(n/\delta))=O(n\log^{3}(n/\delta))$
oracle queries. Hence, the theorem. ∎

##  10\. $k$-center : Adversarial Noise

###### Lemma 10.1.

Suppose in an iteration $t$ of Greedy algorithm, centers are given by $S_{t}$
and we reassign points using Assign which is a $\beta$-approximation to the
correct assignment. In iteration $t+1$, using this assignment, if we obtain an
$\alpha$-approximate farthest point using Approx-Farthest, then, after $k$
iterations, Greedy algorithm obtains a $2\alpha\beta^{2}$-approximation for
the $k$-center objective.

###### Proof.

Consider an optimum clustering $C^{*}$ with centers $u_{1},u_{2},..,u_{k}$
respectively: $C^{*}(u_{1}),C^{*}(u_{2}),\cdots,C^{*}(u_{k})$. Let the centers
obtained by Algorithm 6 be denoted by $S$. If $|S\cap C^{*}(u_{i})|=1$ for all
$i$, then, for some point $x\in C^{*}(u_{i})$ assigned to $s_{j}\in S$ by
Algorithm Assign, we have

$d(x,S\cap C^{*}(u_{i}))\leq d(x,u_{i})+d(u_{i},S\cap C^{*}(u_{i}))\leq 2OPT$
$\Longrightarrow d(x,s_{j})\leq\beta\ \text{min}_{s_{k}\in S}\
d(x,s_{k})\leq\beta\ d(x,S\cap C^{*}(u_{i}))\leq 2\beta OPT$

Therefore, every point in $V$ is at a distance of at most $2\beta OPT$ from a
center assigned in $S$.

Suppose for some $j$ we have $|S\cap C^{*}(u_{j})|\geq 2$. Let $s_{1},s_{2}\in
S\cap C^{*}(u_{j})$ and $s_{2}$ appeared after $s_{1}$ in iteration $t+1$. As
$s_{1}\in S_{t}$, we have $\min_{w\in S_{t}}d(w,s_{2})\leq d(s_{1},s_{2})$. In
iteration $t$, we know that the farthest point $s_{2}$ is an
$\alpha$-approximation of the farthest point (say $f_{t}$). Moreover, suppose
$s_{2}$ assigned to cluster with center $s_{k}$ in iteration $t$ that is a
$\beta$-approximation of it’s true center. Therefore,

$\frac{1}{\alpha}\ {\min_{w\in S_{t}}d(w,f_{t})}\leq
d(s_{k},s_{2})\leq\beta\min_{w\in S_{t}}d(w,s_{2})\leq\beta d(s_{1},s_{2})$

Because $s_{1}$ and $s_{2}$ are in the same optimum cluster, from triangle
inequality we have $d(s_{1},s_{2})\leq 2OPT$. Combining all the above we get
$\min_{w\in S_{t}}d(w,f_{t})\leq 2\alpha\beta OPT$ which means that farthest
point of iteration $t$ is at a distance of $2\alpha\beta OPT$ from $S_{t}$. In
the subsequent iterations, the distance of any point to the final set of
centers, given by $S$ only gets smaller. Hence,

$\max_{v}\min_{w\in S}d(v,w)\leq\max_{v}\min_{w\in S_{t}}d(v,w)=\min_{w\in
S_{t}}d(f_{t},w)\leq 2\alpha\beta OPT$

However, when we output the final clusters and centers, the farthest point
after $k$-iterations (say $f_{k}$) could be assigned to center $v_{j}\in S$
that is a $\beta$-approximation of the distance to true center.

$d(f_{k},v_{j})\leq\beta\ \text{ min}_{w\in S}\ d(f_{k},w)\leq
2\alpha\beta^{2}\ OPT$

Therefore, every point is assigned to a cluster with distance at most
$2\alpha\beta^{2}\ OPT$. Hence the claim. ∎

###### Lemma 10.2.

Given a set $S$ of centers, Algorithm Assign assigns a point $u$ to a cluster
$s_{j}\in S$ such that $d(u,s_{j})\leq(1+\mu)^{2}\min_{s_{t}\in
S}\\{d(u,s_{t})\\}$ using $O(nk)$ queries.

###### Proof.

The proof is essentially the same as Lemma 8.3 and uses MCount instead of
Count. ∎

###### Lemma 10.3.

Given a set of centers $S$, Algorithm 4 identifies a point $v_{j}$ with
probability $1-\delta/k$, such that

$\min_{s_{j}\in S}d(v_{j},s_{j})\geq\max_{v_{t}\in V}\min_{s_{t}\in S}\frac{\
d(v_{t},s_{t})}{(1+\mu)^{5}}$

###### Proof.

Suppose $v_{t}$ is the farthest point assigned to center $s_{t}\in S$. Let
$v_{j}$, assigned to $s_{j}\in S$ be the point returned by Algorithm 4. From
Theorem 8.8, we have :

$\displaystyle d(v_{j},s_{j})$ $\displaystyle\geq\frac{\max_{v_{i}\in
V}d(v_{i},s_{i})}{(1+\mu)^{3}}$
$\displaystyle\geq\frac{d(v_{t},s_{t})}{(1+\mu)^{3}}\geq\frac{\text{min}_{s^{\prime}_{t}\in
S}\ d(v_{t},s^{\prime}_{t})}{(1+\mu)^{3}}$

Due to error in assignment, using Lemma 10.2

$d(v_{j},s_{j})\leq(1+\mu)^{2}\min_{s^{\prime}_{j}\in
S}d(v_{j},s^{\prime}_{j})$

Combining the above equations we have

$\min_{s^{\prime}_{j}\in
S}d(v_{j},s^{\prime}_{j})\geq\frac{\text{min}_{s^{\prime}_{t}\in S}\
d(v_{t},s^{\prime}_{t})}{(1+\mu)^{5}}$

For Approx-Farthest, we use $l=\sqrt{n}$ and $t=\log(2k/\delta)$ and
$\widetilde{V}=\sqrt{n}t$. So, following the proof in Theorem 3.6, we succeed
with probability $1-\delta/k$. Hence, the lemma. ∎

###### Lemma 10.4.

Given a current set of centers $S$,

  1. (1)

Assign assigns a point $u$ to a cluster $C(s_{i})$ such that
$d(u,s_{i})\leq(1+\mu)^{2}\min_{s_{j}\in S}\\{d(u,s_{j})\\}$ using $O(nk)$
oracle queries additionally.

  2. (2)

Approx-Farthest identifies a point $w$ in cluster $C(s_{i})$ such that $\text{
min}_{s_{j}\in S}\ d(w,s_{j})\geq\max_{v_{t}\in V}\min_{s_{t}\in S}{\
d(v_{t},s_{t})}/{(1+\mu)^{5}}$ with probability $1-\frac{\delta}{k}$ using
$O(n\log^{2}(k/\delta))$ oracle queries .

###### Proof.

(1) From Lemma 10.2, we have the claim. We assign a point to a cluster based
on the scores the cluster center received in comparison to other centers.
Except for the newly created center, we have previously queried every center
with every other center. Therefore, number of new oracle queries made for
every point is $O(k)$; that gives us a total of $O(nk)$ additional new queries
used by Assign.

(2) From Lemma 10.3, we have that $\text{ min}_{s_{j}\in S}\
d(w,s_{j})\geq\max_{v_{t}\in V}\min_{s_{t}\in S}\frac{\
d(v_{t},s_{t})}{(1+\mu)^{5}}$ with probability $1-\delta/k$. As the total
number of queries made by Algorithm 4 is $O(nt+(\frac{nt}{l}+\sqrt{n}t)^{2})$.
For Approx-Farthest, we use $l=\sqrt{n}$ and $t=\log(2k/\delta)$ and
$\widetilde{V}=\sqrt{n}t$, therefore, the query complexity is
$O(n\log^{2}(k/\delta))$. ∎

###### Theorem 10.5 (Theorem 4.2 restated).

For $\mu<\frac{1}{18}$, Algorithm 6 achieves a $(2+O(\mu))$-approximation for
the $k$-center objective using $O(nk^{2}+nk\cdot\log^{2}(k/\delta))$ oracle
queries with probability $1-\delta$.

###### Proof.

From the above discussed claim and Lemma 10.4, we have that Algorithm 6
achieves a $2(1+\mu)^{9}$ approximation for $k$-center objective. When
$\mu<\frac{1}{18}$, we can simplify the approximation factor to $2+18\mu$,
i.e., $2+O(\mu)$. From Lemma 10.4, we have that in each iteration, we succeed
with probability $1-\delta/k$. Using union bound, the failure probability is
given by $\delta$. For query complexity, as there are $k$ iterations, and in
each iteration we use Assign and Approx-Farthest, using Lemma 10.4, we have
the theorem. ∎

##  11\. $k$-center : Probabilistic Noise

###  11.1. Sampling

###### Lemma 11.1.

Consider the sample $\widetilde{V}\subseteq V$ of points obtained by selecting
each point with a probability $\frac{450\log(n/\delta)}{m}$. Then, we have
$\frac{400n\log(n/\delta)}{m}\leq|\widetilde{V}|\leq\frac{500n\log(n/\delta)}{m}$
and for every $i\in[k]$,
$|C^{*}(s_{i})\cap\widetilde{V}|\geq{400\log(n/\delta)}$ with probability
$1-O(\delta)$ for sufficiently large $\gamma>0$.

###### Proof.

We include every point in $\widetilde{V}$ with a probability
$\frac{450\log(n/\delta)}{m}$ where the size of the smallest cluster is $m$.
Using Chernoff bound, with probability $1-O(\delta)$, we have :

$\frac{400n\log(n/\delta)}{m}\leq|\widetilde{V}|\leq\frac{500n\log(n/\delta)}{m}$

Consider an optimal cluster $C^{*}(v_{i})$ with center $v_{i}$. As every point
is included with probability $\frac{450\log(n/\delta)}{m}$ :