  Nearest Neighbor Search (NNS) is a central task in knowledge representation,
learning, and reasoning. There is vast literature on efficient algorithms for
constructing data structures and performing exact and approximate NNS. This
paper studies NNS under Uncertainty (NNSU). Specifically, consider the setting
in which an NNS algorithm has access only to a stochastic distance oracle that
provides a noisy, unbiased estimate of the distance between any pair of points,
rather than the exact distance. This models many situations of practical
importance, including NNS based on human similarity judgements, physical
measurements, or fast, randomized approximations to exact distances. A naive
approach to NNSU could employ any standard NNS algorithm and repeatedly query
and average results from the stochastic oracle (to reduce noise) whenever it
needs a pairwise distance. The problem is that a sufficient number of repeated
queries is unknown in advance; e.g., a point maybe distant from all but one
other point (crude distance estimates suffice) or it may be close to a large
number of other points (accurate estimates are necessary). This paper shows how
ideas from cover trees and multi-armed bandits can be leveraged to develop an
NNSU algorithm that has optimal dependence on the dataset size and the
(unknown)geometry of the dataset.
