Query-Adaptive Reciprocal Hash Tables for Nearest Neighbor Search

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• Binary hashing is successful for approximate nearest neighbor search.
• Multiple hash tables improve search but lack unified construction and ranking.

Purpose of the Study:

• Develop a unified approach for constructing informative multiple hash tables.
• Introduce a generic, query-adaptive ranking scheme for multiple table search.
• Address binary quantization loss in hashing techniques.

Main Methods:

• Table construction as a selection problem using normalized dominant set on candidate hash functions.
• Reciprocal hash tables constructed in a boosting manner to reduce redundancy.
• Query-adaptive bitwise weighting scheme for fine-grained bucket ranking.
• Fast, reciprocal table lookup algorithm within adaptive weighted Hamming radius.

Main Results:

• Proposed techniques significantly outperform naive construction and state-of-the-art hashing algorithms.
• Demonstrated effectiveness on several large-scale benchmarks.
• Achieved improved accuracy and efficiency in approximate nearest neighbor search.

Conclusions:

• The proposed general construction and query-adaptive search methods are compatible with diverse hashing algorithms.
• The techniques effectively mitigate binary quantization loss.
• Offers a significant advancement in multiple hash table construction and search.