Hash Bit Selection for Nearest Neighbor Search.

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• Gigantic-scale datasets pose storage and computation challenges for nearest neighbor search.
• Compact hashing methods approximate nearest neighbor search but face issues in feature, algorithm, and parameter selection.
• Existing hashing techniques require optimized bit selection for improved performance.

Purpose of the Study:

• To address critical design issues in compact hashing by proposing an optimal hash bit selection problem.
• To develop a framework for selecting optimal hash bits from various sources to enhance hashing performance.
• To improve the accuracy and efficiency of nearest neighbor search in large-scale datasets.

Main Methods:

• An optimal hash bit selection framework is proposed, using bit reliability and complementarity as criteria.
• A modified dynamic programming method is employed to balance search accuracy and time.
• Quadratic programming approximates high-order independence, reducing computational complexity.

Main Results:

• The proposed bit selection framework achieves superior performance compared to naive methods and state-of-the-art algorithms.
• Significant accuracy gains, ranging from 10% to 50%, were observed across various application scenarios.
• The method effectively balances search accuracy and computational time for large-scale data.

Conclusions:

• The developed optimal hash bit selection framework offers a robust solution for nearest neighbor search in massive datasets.
• This approach significantly enhances the accuracy and efficiency of compact hashing techniques.
• The findings provide valuable insights for designing high-performance hashing algorithms.