FANNG: Fast Approximate Nearest Neighbour Graphs
Authors:
- Ben HarwoodBHBen Harwood
- Tom DrummondTDTom Drummond
Top Cited Papers
- 12 December 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 5713-5722
Abstract
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.Keywords
This publication has 23 references indexed in Scilit:
- Permutation search methods are efficient, yet faster search is possibleProceedings of the VLDB Endowment, 2015
- Approximate nearest neighbor algorithm based on navigable small world graphsInformation Systems, 2014
- Fast and Accurate Image Matching with Cascade Hashing for 3D Reconstruction2014
- Locally Optimized Product Quantization for Approximate Nearest Neighbor Search2014
- Scalable Nearest Neighbor Algorithms for High Dimensional DataIEEE Transactions on Pattern Analysis and Machine Intelligence, 2014
- NV-Tree2011
- Efficient indexing for large scale visual search2009
- Optimised KD-trees for fast image descriptor matching2008
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Two algorithms for constructing a Delaunay triangulationInternational Journal of Parallel Programming, 1980