Asymmetric Mapping Quantization for Nearest Neighbor Search.

Area of Science:

• Computer Science
• Machine Learning
• Artificial Intelligence

Background:

• Nearest neighbor search is crucial for computer vision and machine learning.
• Linear scan methods are inefficient for large-scale, high-dimensional data.
• Approximate nearest neighbor (ANN) search is a key area of research.

Purpose of the Study:

• To propose a novel addition-based vector quantization algorithm for efficient ANN search.
• To address the limitations of existing methods in handling database vector norms.
• To enable ANN search on very large datasets through distributed learning.

Main Methods:

• Developed Asymmetric Mapping Quantization (AMQ) using addition-based vector quantization.
• Transformed L-2 distance computation to inner product similarity by using different mapping functions for query and database vectors.
• Proposed Distributed Asymmetric Mapping Quantization (DAMQ) for distributed learning on large datasets.

Main Results:

• AMQ efficiently conducts approximate nearest neighbor search.
• The proposed method avoids the need to evaluate the norm of database vectors, a common issue in other techniques.
• DAMQ demonstrates scalability for very large datasets.

Conclusions:

• AMQ offers an efficient and effective solution for approximate nearest neighbor search.
• The novel mapping strategy overcomes previous limitations in addition-based quantization.
• DAMQ extends AMQ's applicability to massive datasets, validated by experiments in ANN search and image retrieval.