Equivalent Continuous Formulation of General Hashing Problem.

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• Hashing-based approximate nearest neighbor (ANN) search is crucial for efficient large-scale data retrieval.
• Existing methods often relax discrete constraints, leading to significant quantization errors and reduced binary code effectiveness.
• The NP-hard nature of discrete hashing necessitates robust optimization techniques.

Purpose of the Study:

• To develop an equivalent continuous formulation for the discrete hashing problem.
• To enable the application of continuous optimization methods to hashing without relaxation.
• To improve the accuracy and effectiveness of binary codes generated for ANN search.

Main Methods:

• Transformed the discrete hashing problem into a continuous optimization problem without relaxations.
• Utilized Difference of Convex functions (DC) programming to solve the continuous formulation.
• Applied the proposed continuous hashing scheme to existing supervised and unsupervised hashing models.

Main Results:

• The continuous formulation yields the same optimal solutions and values as the original discrete problem.
• The proposed DC programming-based algorithms effectively solve the continuous hashing problem.
• Evaluations on benchmark datasets demonstrate superior performance compared to state-of-the-art hashing methods.

Conclusions:

• The proposed equivalent continuous formulation overcomes limitations of relaxation-based hashing methods.
• DC programming provides an effective approach for solving the continuous hashing problem.
• This method offers a superior alternative for hashing-based approximate nearest neighbor search across various models.