Distance Encoded Product Quantization for Approximate K-Nearest Neighbor Search in High-Dimensional Space.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Approximate K-nearest neighbor (AKNN) search is crucial for high-dimensional, large-scale datasets.
• Product quantization (PQ) and its variants are popular for compact data encoding in AKNN.
• Existing PQ methods may suffer from increased distance estimation errors for points far from cluster centers.

Purpose of the Study:

• To investigate optimal bit-budget allocation for encoding in product quantization.
• To propose a novel compact code representation for improved distance estimation in AKNN.
• To enhance the accuracy of approximate K-nearest neighbor search algorithms.

Main Methods:

• Developed a novel compact code representation distributing bit-budget between cluster index and quantized distance per subspace.
• Proposed two specialized distance estimators tailored to the new representation.
• Extended the method to incorporate global residual distances.

Main Results:

• The proposed methods significantly improve search accuracy compared to existing techniques.
• Consistent performance gains observed across GIST, VLAD, and CNN feature benchmarks.
• Improved accuracy is attributed to more precise distance estimations.

Conclusions:

• The novel compact code representation and distance estimators enhance AKNN search accuracy.
• Distributing the bit-budget effectively is key to overcoming limitations of standard product quantization.
• The proposed approach offers a more robust solution for high-dimensional approximate nearest neighbor search.