Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph
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.
Summary¶
Introduces Graph Nearest Neighbor Search, which builds a k-nearest-neighbor graph offline and answers queries by greedy hill-climbing from random graph nodes. The paper provides theoretical accuracy and complexity guarantees and anticipates later graph-navigation approaches to approximate nearest-neighbor search.
Links¶
Knowledge Base
External
Tags¶
Similar Papers¶
1
78%
2
76%
Near-optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Near-Optimal Locality-Sensitive Hashing
3
75%
4
73%
5
70%