Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph

Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, Hong Zhang

Abstract

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.
BibTeX
@inproceedings{hajebi2011fast,
  author = {Kiana Hajebi and Yasin Abbasi-Yadkori and Hossein Shahbazi and Hong Zhang},
  title = {{Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
}

Loading related content...

Figure