Composite Quantization.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Approximate Nearest Neighbor (ANN) search is crucial for large-scale data retrieval.
• Existing compact coding methods face challenges in balancing accuracy and search efficiency.
• High-dimensional vector approximation requires efficient representation techniques.

Purpose of the Study:

• To develop a novel compact coding framework for accurate and efficient ANN search.
• To introduce a near-orthogonality constraint to optimize quantization and search performance.
• To theoretically and empirically validate the proposed composite quantization approach.

Main Methods:

• A composite quantization framework using multiple dictionaries to approximate high-dimensional vectors.
• Introduction of a near-orthogonality constraint to reduce distance computation cost to O(M).
• Theoretical justification via generalized triangle inequality, linking quantization error and search cost.

Main Results:

• Near-Orthogonal Composite Quantization (NOCQ) achieves accurate vector approximation with short codes.
• Search efficiency is guaranteed with distance computation reduced via a lookup scheme.
• Empirical validation on benchmark datasets demonstrates superior performance.

Conclusions:

• NOCQ offers a theoretically sound and empirically effective approach for ANN search.
• The method shows versatility, improving performance in inverted multi-index, inner-product search, and mobile query compression.
• This framework advances compact coding for efficient high-dimensional data retrieval.