FANNG: Fast Approximate Nearest Neighbour Graphs
We present a new method for approximate nearest neighbour search on large datasets of high dimensional feature vectors, such as SIFT or GIST descriptors. Our approach constructs a directed graph that can be efficiently explored for nearest neighbour queries. Each vertex in this graph represents a feature vector from the dataset being searched. The directed edges are computed by exploiting the fact that, for these datasets, the intrinsic dimensionality of the local manifold-like structure formed by the elements of the dataset is significantly lower than the embedding space. We also provide an efficient search algorithm that uses this graph to rapidly find the nearest neighbour to a query with high probability. We show how the method can be adapted to give a strong guarantee of 100% recall where the query is within a threshold distance of its nearest neighbour. We demonstrate that our method is significantly more efficient than existing state of the art methods. In particular, our GPU implementation can deliver 90% recall for queries on a data set of 1 million SIFT descriptors at a rate of over 1.2 million queries per second on a Titan X. Finally we also demonstrate how our method scales to datasets of 5M and 20M entries.
Code (0)
등록된 구현이 없습니다.
Tasks
GPUSimilar Papers 제목 키워드 기반
Faster and More Robust Mesh-based Algorithms for Obstacle k-Nearest Neighbour
We are interested in the problem of finding $k$ nearest neighbours in the plane and in the presence of polygonal obstacles ($\textit{OkNN}$). Widely used algorithms for OkNN are based on incremental visibility graphs, wh…
Nearest Neighbour with Bandit Feedback
In this paper we adapt the nearest neighbour rule to the contextual bandit problem. Our algorithm handles the fully adversarial setting in which no assumptions at all are made about the data-generation process. When comb…
Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation
Approximate k-Nearest Neighbour (ANN) methods are often used for mining information and aiding machine learning on large scale high-dimensional datasets. ANN methods typically differ in the index structure used for accel…
Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours
We study the approximate nearest neighbour method for cost-sensitive classification on low-dimensional manifolds embedded within a high-dimensional feature space. We determine the minimax learning rates for distributions…
General ClassificationBeyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport
Nearest neighbour graphs are widely used to capture the geometry or topology of a dataset. One of the most common strategies to construct such a graph is based on selecting a fixed number k of nearest neighbours (kNN) fo…