Extremely Low Bit-Rate Nearest Neighbor Search Using a Set Compression Tree.

Area of Science:

• Computer Science
• Data Structures
• Machine Learning

Background:

• Approximate nearest neighbor (ANN) search is crucial for large-scale vector datasets.
• Existing methods often struggle to balance memory efficiency with search accuracy.

Purpose of the Study:

• To develop a novel data structure for efficient ANN search on massive vector descriptor sets.
• To optimize for minimal memory footprint and high approximation accuracy.

Main Methods:

• Introduction of the Set Compression Tree (SCT), a novel encoding method for joint compression of descriptor sets.
• Implementation of encoding, decoding, and nearest neighbor search functionalities.
• Evaluation on standard benchmarks like SIFT1M and 80 Million Tiny Images.

Main Results:

• SCT achieves superior performance compared to state-of-the-art methods like Product Quantization and Locality Sensitive Hashing.
• Accurate compression of 1 million descriptors using only a few bits per descriptor.
• SCT demonstrates lower error rates even at significantly lower bit rates than competing methods.

Conclusions:

• Set Compression Tree (SCT) is an effective and memory-efficient solution for large-scale approximate nearest neighbor search.
• The joint compression strategy enables unprecedented compression rates without sacrificing accuracy.
• SCT offers a promising alternative for applications requiring fast and accurate similarity searches in massive datasets.