NV-tree: an efficient disk-based index for approximate search in very large high-dimensional collections

Area of Science:

• Computer Science
• Data Structures
• Database Systems

Background:

• Nearest neighbor search in high-dimensional data is computationally intensive.
• Existing methods often require large main memory or high-performance environments.
• Disk-based operations are typically avoided due to perceived slowness.

Purpose of the Study:

• To propose an efficient disk-based data structure for nearest neighbor search.
• To address the economic limitations of memory-intensive approaches for large datasets.
• To provide approximate nearest neighbor queries with minimal disk I/O.

Main Methods:

• Introduction of the NV-tree, a novel disk-based data structure.
• Evaluation of NV-tree performance on large, high-dimensional datasets.
• Comparison with Locality Sensitive Hashing (LSH) for epsilon-distance search.

Main Results:

• The NV-tree achieves good approximate nearest neighbor search results with a single disk operation.
• High recall is maintained, though initial results may contain false positives.
• Combining multiple NV-trees significantly reduces false positives while preserving high recall.
• NV-tree demonstrates comparable result quality to LSH but with substantially fewer disk reads.

Conclusions:

• The NV-tree is an efficient and economically viable solution for nearest neighbor search in large, high-dimensional datasets.
• It offers a practical alternative to memory-bound or high-performance computing approaches.
• The NV-tree's disk-based nature makes it suitable for scenarios where disk I/O is a critical factor.