AAAI Publications, Twenty-Second International Joint Conference on Artificial Intelligence

Font Size: 
Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph
Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, Hong Zhang

Last modified: 2011-06-28

Abstract


We introduce a new nearest neighbor search al-gorithm. The algorithm builds a nearest neighborgraph in an offline phase and when queried witha new point, performs hill-climbing starting froma randomly sampled node of the graph. We pro-vide theoretical guarantees for the accuracy and thecomputational complexity and empirically showthe effectiveness of this algorithm.

Full Text: PDF