28622 articles – 22133 references  [version française]

hal-00644939, version 1

NV-Tree: nearest neighbors at the billion scale

Herwig Lejsek (Author to contact preferably) a, 1, Björn Þór Jónsson () b, 2, Laurent Amsaleg () 3

1st ACM International Conference on Multimedia Retrieval (2011)

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.

  • a –  Videntifier Technologies
  • b –  Reykjavík University
  • 1:  Videntifier Technologies
  • Videntifier Technologies
  • 2:  School of Computer Science [Reykjavik]
  • Reykjavík University
  • 3:  TEXMEX (INRIA - IRISA)
  • CNRS : UMR6074 – INRIA – Institut National des Sciences Appliquées (INSA) - Rennes – Université de Rennes 1
  • Domain : Computer Science/Databases
    Computer Science/Multimedia
 
  • hal-00644939, version 1
  • http://hal.inria.fr/hal-00644939
  • oai:hal.inria.fr:hal-00644939
  • From: Laurent Amsaleg <>
  • Submitted on: Friday, 25 November 2011 15:27:41
  • Updated on: Friday, 25 November 2011 15:27:41