FANNG: Fast approximate nearest neighbour graphs

Ben Harwood, Tom Drummond

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

24 Citations (Scopus)

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.

Original languageEnglish
Title of host publication2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016)
Subtitle of host publicationLas Vegas, Nevada, USA, 27-30 June, 2016
Place of PublicationPiscataway, NJ
PublisherIEEE Computer Society
Pages5713-5722
Number of pages10
ISBN (Electronic)9781467388511
ISBN (Print)9781467388528
DOIs
Publication statusPublished - 2016
EventIEEE Conference on Computer Vision and Pattern Recognition 2016 - Las Vegas, United States of America
Duration: 27 Jun 201630 Jun 2016
http://cvpr2016.thecvf.com/
https://ieeexplore.ieee.org/xpl/conhome/7776647/proceeding (Proceedings)

Conference

ConferenceIEEE Conference on Computer Vision and Pattern Recognition 2016
Abbreviated titleCVPR 2016
CountryUnited States of America
CityLas Vegas
Period27/06/1630/06/16
Internet address

Cite this