Toward Optimal Manifold Hashing via Discrete Locally Linear Embedding

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• Binary code learning (hashing) is crucial for large-scale visual search, approximating Euclidean distance with Hamming distance.
• Preserving manifold distance in Hamming space is a recent focus, but directly hashing manifold structures remains challenging.
• Existing two-step methods for manifold preservation are suboptimal and computationally expensive due to offline learning and similarity matrix calculation.

Purpose of the Study:

• To propose a novel hashing algorithm, Discrete Locality Linear Embedding Hashing (DLLH), that directly reconstructs manifold structure in Hamming space.
• To address the limitations of existing methods, including suboptimal two-step coding and time/memory inefficiency.
• To develop an efficient and effective hashing solution for large-scale visual search applications.

Main Methods:

• DLLH directly learns optimal hash codes by reconstructing the manifold structure within the Hamming space.
• A discrete optimization algorithm with iterative parameter updating is proposed for learning discrete locally linear embedding codes.
• An anchor-based acceleration scheme (Anchor-DLLH) is introduced to approximate large similarity matrices using low-rank matrix factorization.

Main Results:

• DLLH demonstrates superior performance compared to state-of-the-art hashing approaches.
• The proposed method effectively preserves local linear relationships of data points in the Hamming space.
• Experimental validation on CIFAR10, NUS-WIDE, and YouTube Face datasets confirms DLLH's effectiveness.

Conclusions:

• DLLH offers a novel and effective approach to directly preserve manifold structure in Hamming space for visual search.
• The discrete optimization and anchor-based acceleration schemes enhance the efficiency and performance of hashing.
• DLLH represents a significant advancement in binary code learning for large-scale visual search.