Fast Approximate Nearest-Neighbor Search using k-Nearest Neighbor Graph
Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi and Hong Zhang
We introduce a new nearest neighbor search algorithm. The algorithm builds a nearest neighbor graph in an offline phase and when queried with a new point, performs hill-climbing starting from a randomly sampled node of the graph. We provide theoretical guarantees for the accuracy and the computational complexity and empirically show the effectiveness of this algorithm.