NV-Tree: nearest neighbors at the billion scale

Herwig Lejsek 1, * Björn Þór Jónsson 2 Laurent Amsaleg 3
* Auteur correspondant
3 TEXMEX - Multimedia content-based indexing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : This paper presents the NV-Tree (Nearest Vector Tree). It addresses the specific, yet important, problem of efficiently and effectively finding the approximate k-nearest neighbors within a collection of a few billion high-dimensional data points. The NV-Tree is a very compact index, as only six bytes are kept in the index for each high-dimensional descriptor. It thus scales extremely well when indexing large collections of high-dimensional descriptors. The NV-Tree efficiently produces results of good quality, even at such a large scale that the indices cannot be kept entirely in main memory any more. We demonstrate this with extensive experiments using a collection of 2.5 billion SIFT (Scale Invariant Feature Transform) descriptors.
Type de document :
Communication dans un congrès
1st ACM International Conference on Multimedia Retrieval, Apr 2011, Trento, Italy. 2011, 〈http://doi.acm.org/10.1145/1991996.1992050〉. 〈10.1145/1991996.1992050〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00644939
Contributeur : Laurent Amsaleg <>
Soumis le : vendredi 25 novembre 2011 - 15:27:41
Dernière modification le : mercredi 11 avril 2018 - 02:00:57

Identifiants

Citation

Herwig Lejsek, Björn Þór Jónsson, Laurent Amsaleg. NV-Tree: nearest neighbors at the billion scale. 1st ACM International Conference on Multimedia Retrieval, Apr 2011, Trento, Italy. 2011, 〈http://doi.acm.org/10.1145/1991996.1992050〉. 〈10.1145/1991996.1992050〉. 〈hal-00644939〉

Partager

Métriques

Consultations de la notice

332