 |
| Research article summary (published 29 Apr 2009): |
NV-tree: an efficient disk-based index for approximate search in very large high-dimensional collections.
Full Abstract
Over the last two decades, much research effort has been spent on nearest neighbor search in high-dimensional data sets. Most of the approaches published thus far have, however, only been tested on rather small collections. When large collections have been considered, high-performance environments have been used, in particular systems with a large main memory. Accessing data on disk has largely been avoided because disk operations are considered to be too slow. It has been shown, however, that using large amounts of memory is generally not an economic choice. Therefore, we propose the NV-tree, which is a very efficient disk-based data structure that can give good approximate answers to nearest neighbor queries with a single disk operation, even for very large collections of high-dimensional data. Using a single NV-tree, the returned results have high recall but contain a number of false positives. By combining two or three NV-trees, most of those false positives can be avoided while retaining the high recall. Finally, we compare the NV-tree to Locality Sensitive Hashing, a popular method for epsilon-distance search. We show that they return results of similar quality, but the NV-tree uses many fewer disk reads.
Author information
Author/s: Lejsek, Herwig (H); Asmundsson, Fridrik Heidar (FH); Jónsson, Björn thór (B); Amsaleg, Laurent (L);
Affiliation: Eff2 Technologies ehf., Kringlan1, IS-103 Reykjavík, Iceland. {herwig, fridrik}(-atsign-)eff2.net
Journal and publication information
Publication Type: Journal Article; Research Support, Non-U.S. Gov't
Journal: IEEE transactions on pattern analysis and machine intelligence (IEEE Trans Pattern Anal Mach Intell), published in United States. (Language: eng)
Reference: 2009-May; vol 31 (issue 5) : pp 869-83
Dates: Created 2009/03/20; Completed 2009/06/10;
PMID: 19299861, status: MEDLINE (last retrieval date: 6/10/2009, IMS Date: 10 Jun 2009 00:00:00)
Sourced from the National Library of Medicine. Abstract text and other information may be subject to copyright.
External Links for this article
(including full text providers, if available):
Click Electronic Full-text Provider Links to see options for finding the electronic full text links to this article. Note there may be a subscription or fee required for access to the full text. See our FAQ for information on finding FREE full text articles.
This article may also be located in paper journal collections available in many libraries. Use the Journal and Publication Information above to find the full article.
MeSH headings (categories)
This article was linked to the MESH Headings shown below.
Related articles
This article has not been indexed for related articles as yet, however you can still use the live related article search links below.
See a large map of 100+ related articles.