Supervised Discrete Hashing

TLDR

Learning‑based hashing has attracted broad interest for efficient storage and retrieval of high‑dimensional data, yet the discrete constraints on hash codes make optimization NP‑hard. This work introduces a supervised hashing framework that learns optimal binary hash codes tailored for linear classification. By adding an auxiliary variable, the objective is reformulated so that a regularization algorithm can efficiently solve the NP‑hard binary sub‑problem, yielding an analytical solution via cyclic coordinate descent. Experiments on four large image datasets show that the resulting Supervised Discrete Hashing method achieves superior retrieval performance compared to state‑of‑the‑art hashing techniques while remaining computationally efficient.

Abstract

Recently, learning based hashing techniques have attracted broad research interests because they can support efficient storage and retrieval for high-dimensional data such as images, videos, documents, etc. However, a major difficulty of learning to hash lies in handling the discrete constraints imposed on the pursued hash codes, which typically makes hash optimizations very challenging (NP-hard in general). In this work, we propose a new supervised hashing framework, where the learning objective is to generate the optimal binary hash codes for linear classification. By introducing an auxiliary variable, we reformulate the objective such that it can be solved substantially efficiently by employing a regularization algorithm. One of the key steps in this algorithm is to solve a regularization sub-problem associated with the NP-hard binary optimization. We show that the sub-problem admits an analytical solution via cyclic coordinate descent. As such, a high-quality discrete solution can eventually be obtained in an efficient computing manner, therefore enabling to tackle massive datasets. We evaluate the proposed approach, dubbed Supervised Discrete Hashing (SDH), on four large image datasets and demonstrate its superiority to the state-of-the-art hashing methods in large-scale image retrieval.