The Road to the Closest Point is Paved by Good Neighbors

Abstract

Given a set $P$ of $n$ points in ${\Re }^d$, and a parameter $\epsilon \in (0,1)$, we present a new construction of a directed graph $G$, of size $O(n/{\epsilon }^d)$, such that $(1+\epsilon )$-ANN queries can be answered by performing a greedy walk on $G$, repeatedly moving to a neighbor that is (significantly) better than the current point. To the best of our knowledge, this is the first construction of a linear size with no dependency on the spread of the point set. The resulting query time, is $O({\epsilon }^{-d}\log \Psi )$, where $\Psi$ is the spread of $P$. The new construction is surprisingly simple and should be practical.