FANNG: Fast approximate nearest neighbour graphs

Ben Harwood, Tom Drummond

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

17 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
Conference number: 29th
http://cvpr2016.thecvf.com/

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

Harwood, B., & Drummond, T. (2016). FANNG: Fast approximate nearest neighbour graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016): Las Vegas, Nevada, USA, 27-30 June, 2016 (pp. 5713-5722). Piscataway, NJ: IEEE Computer Society. https://doi.org/10.1109/CVPR.2016.616
Harwood, Ben ; Drummond, Tom. / FANNG : Fast approximate nearest neighbour graphs. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016): Las Vegas, Nevada, USA, 27-30 June, 2016. Piscataway, NJ : IEEE Computer Society, 2016. pp. 5713-5722
@inproceedings{c650bdbb128f4a258e20051afa991945,
title = "FANNG: Fast approximate nearest neighbour graphs",
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.",
author = "Ben Harwood and Tom Drummond",
year = "2016",
doi = "10.1109/CVPR.2016.616",
language = "English",
isbn = "9781467388528",
pages = "5713--5722",
booktitle = "2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016)",
publisher = "IEEE Computer Society",
address = "United States of America",

}

Harwood, B & Drummond, T 2016, FANNG: Fast approximate nearest neighbour graphs. in 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016): Las Vegas, Nevada, USA, 27-30 June, 2016. IEEE Computer Society, Piscataway, NJ, pp. 5713-5722, IEEE Conference on Computer Vision and Pattern Recognition 2016, Las Vegas, United States of America, 27/06/16. https://doi.org/10.1109/CVPR.2016.616

FANNG : Fast approximate nearest neighbour graphs. / Harwood, Ben; Drummond, Tom.

2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016): Las Vegas, Nevada, USA, 27-30 June, 2016. Piscataway, NJ : IEEE Computer Society, 2016. p. 5713-5722.

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

TY - GEN

T1 - FANNG

T2 - Fast approximate nearest neighbour graphs

AU - Harwood, Ben

AU - Drummond, Tom

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84986296783&partnerID=8YFLogxK

U2 - 10.1109/CVPR.2016.616

DO - 10.1109/CVPR.2016.616

M3 - Conference Paper

AN - SCOPUS:84986296783

SN - 9781467388528

SP - 5713

EP - 5722

BT - 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016)

PB - IEEE Computer Society

CY - Piscataway, NJ

ER -

Harwood B, Drummond T. FANNG: Fast approximate nearest neighbour graphs. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2016): Las Vegas, Nevada, USA, 27-30 June, 2016. Piscataway, NJ: IEEE Computer Society. 2016. p. 5713-5722 https://doi.org/10.1109/CVPR.2016.616