Spectral Approaches to Nearest Neighbor Search

Amirali Abdullah, Alexandr Andoni, Ravindran Kannan +1

We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset $P$ in ${\mathbb{R}}^d$…