A Survey on Learning to Hash

Introduction

The problem of nearest neighbor search, also known as similarity search, proximity search, or close item search, is aimed at finding an item, called nearest neighbor, which is the nearest to a query item under a certain distance measure from a search (reference) database. The cost of finding the exact nearest neighbor is prohibitively high in the case that the reference database is very large or that computing the distance between the query item and the database item is costly. The alternative approach, approximate nearest neighbor search, is more efficient and is shown to be enough and useful for many practical problems, thus attracting an enormous number of research efforts.

Hashing, a widely-studied solution to the approximate nearest neighbor search, aims to transform a data item to a low-dimensional representation, or equivalently a short code consisting of a sequence of bits, called hash code. There are two main categories of hashing algorithms: locality sensitive hashing and learning to hash. Locality sensitive hashing (LSH) is data-independent. Following the pioneering works , there are a lot of efforts, such as proposing random hash functions satisfying the locality sensitivity property for various distance measures , proving better search efficiency and accuracy , developing better search schemes , providing a similarity estimator with smaller variance , , , , smaller storage , , or faster computation of hash functions , , , . LSH has been adopted in many applications, e.g., fast object detection , image matching The detailed review on LSH can be found in .

Learning to hash, the interest of this survey, is a data-dependent hashing approach which aims to learn hash functions from a specific dataset so that the nearest neighbor search result in the hash coding space is as close as possible to the search result in the original space, and the search cost as well as the space cost are also small. The development of learning to hash has been inspired by the connection between the Hamming distance and the distance provided from the original space, e.g., the cosine distance shown in SimHash . Since the two early algorithms, semantic hashing and spectral hashing that learns projection vectors instead of the random projections as done in , learning to hash has been attracting a large amount of research interest in computer vision and machine learning and has been applied to a wide-range of applications such as large scale object retrieval , image classification and detection , and so on.

The main methodology of learning to hash is similarity preserving, i.e., minimizing the gap between the similarities computed/given in the original space and the similarities in the hash coding space in various forms. The similarity in the original space might be from the semantic (class) information, or from the distance (e.g., Euclidean distance) computed in the original space, which is of broad interest and widely studied in real applications, e.g., large scale image search and image classification. Hence the later is the main focus in this paper.

This survey categorizes the algorithms according to the similarity preserving manner into: pairwise similarity preserving, multiwise similarity preserving, implicit similarity preserving, quantization which we will show is also a form of pairwise similarity preserving, as well as an end-to-end hash learning strategy learning the hash codes directly from the object, e.g., image, under the deep learning framework instead of first learning the representations and then learning the hash codes from the representations. In addition, we discuss other problems including evaluation datasets and evaluation schemes, and so on. Meanwhile, we present the empirical observation that the quantization approach outperforms other approaches and give some analysis about this observation.

In comparison to other surveys on learning to hash , this survey focuses more on learning to hash, discusses more on quantization-based solutions. Our categorization methodology is helpful for readers to understand connections and differences between existing algorithms. In particular, we point out the empirical observation that quantization is superior in terms of search accuracy, search efficiency and space cost

Background

Exact nearest neighbor search is defined as searching an item $\operatorname{NN}(\mathbf{q})$ (called nearest neighbor) for a query item $\mathbf{q}$ from a set of $N$ items $\mathcal{X}=\{\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{N}\}$ so that $\operatorname{NN}(\mathbf{q})=\arg\min_{\mathbf{x}\in\mathcal{X}}\operatorname{dist}(\mathbf{q},\mathbf{x})$, where $\operatorname{dist}(\mathbf{q},\mathbf{x})$ is a distance computed between $\mathbf{q}$ and $\mathbf{x}$. A straightforward generalization is $K$-nearest neighbor search, where $K$ nearest neighbors are needed to be found.

There exist efficient algorithms (e.g., $k$-d trees) for exact nearest neighbor search in low-dimensional cases. In large scale high-dimensional cases, it turns out that the problem becomes hard and most algorithms even take higher computational cost than the naive solution, i.e., the linear scan. Therefore, a lot of recent efforts moved to searching approximate nearest neighbors: error-constrained nearest (near) neighbor search, and time-constrained approximate nearest neighbor search . The error-constrained search includes (randomized) $(1+\epsilon)$-approximate nearest neighbor search , (approximate) fixed-radius near neighbor ($R$-near neighbor) search , and so on.

Time-constrained approximate nearest neighbor search limits the time spent during the search and is studied mostly for real applications, though it usually lacks an elegant theory behind. The goal is to make the search as accurate as possible by comparing the returned $K$ approximate nearest neighbors and the $K$ exact nearest neighbors, and to make the query cost as small as possible. For example, when comparing the learning to hash approaches that use linear scan based on the Hamming distance for search, it is typically assumed that the search time is the same for the same code length by ignoring other small cost. When comparing the indexing structure algorithms, e.g., tree-based or neighborhood graph-based , the time-constrained search is usually transformed to another approximate way: terminate the search after examining a fixed number of data points.

2 Search with Hashing

The hashing approach aims to map the reference (and query) items to the target items so that approximate nearest neighbor search is efficiently and accurately performed by resorting to the target items and possibly a small subset of the raw reference items. The target items are called hash codes (a.k.a., hash values, or simply hashes). In this paper, we may also call it short/compact codes interchangeably.

The hash function is formally defined as: $y=h(\mathbf{x})$, where $y$ is the hash code, may be an integer, or a binary value: $1$ and (or $-1$), and $h(\cdot)$ is the hash function. In the application to approximate nearest neighbor search, usually several hash functions are used together to compute the compound hash code: $\mathbf{y}=\mathbf{h}(\mathbf{x})$, where $\mathbf{y}=[y_{1}~{}y_{2}~{}\cdots~{}y_{M}]^{\top}$ and $\mathbf{h}(\mathbf{x})=[h_{1}(\mathbf{x})~{}h_{2}(\mathbf{x})~{}\cdots~{}h_{M}(\mathbf{x})]^{\top}$. Here we use a vector $\mathbf{y}$ to represent the compound hash code for convenience.

There are two basic strategies for using hash codes to perform nearest (near) neighbor search: hash table lookup and hash code ranking. The search strategies are illustrated in Figure 1.

The main idea of hash table lookup for accelerating the search is reducing the number of the distance computations. The data structure, called hash table (a form of inverted index), is composed of buckets with each bucket indexed by a hash code. Each reference item $\mathbf{x}$ is placed into a bucket $\mathbf{h}(\mathbf{x})$. Different from the conventional hashing algorithm in computer science that avoids collisions (i.e., avoids mapping two items into some same bucket), the hashing approach using a hash table essentially aims to maximize the probability of collision of near items and at the same time minimize the probability of collision of the items that are far away. Given the query $\mathbf{q}$, the items lying in the bucket $\mathbf{h}(\mathbf{q})$ are retrieved as the candidates of the nearest items of $\mathbf{q}$. Usually this is followed by a reranking step: rerank the retrieved nearest neighbor candidates according to the true distances computed using the original features and attain the nearest neighbors.

To improve the recall, two ways are often adopted. The first way is to visit a few more buckets (but with a single hash table), whose corresponding hash codes are the nearest to (the hash code $\mathbf{h}(\mathbf{q})$ of) the query according to the distances in the coding space. The second way is to construct several (e.g., $L$) hash tables. The items lying in the $L$ hash buckets $\mathbf{h}_{1}(\mathbf{q}),\cdots,\mathbf{h}_{L}(\mathbf{q})$ are retrieved as the candidates of near items of $\mathbf{q}$ which are possibly ordered according to the number of hits of each item in the $L$ buckets. To guarantee the high precision, each of the $L$ hash codes, $\mathbf{y}_{l}$, needs to be a long code. This means that the total number of the buckets is too large to index directly, and thus the buckets that are non-empty are retained by using the conventional hashing over the hash codes $\mathbf{h}_{l}(\mathbf{x})$.

The second way essentially stores multiple copies of the id for each reference item. Consequently, the space cost is larger. In contrast, the space cost for the first way is smaller as it only uses a single table and stores one copy of the id for each reference item, but it needs to access more buckets to guarantee the same recall with the second way. The multiple assignment scheme is also studied: construct a single table, but assign a reference item to multiple hash buckets. In essence, it is shown that the second way, multiple hash tables, can be regarded as a form of multiple assignment.

Hash code ranking performs an exhaustive search: compare the query with each reference item by fast evaluating their distance (e.g., using distance table lookup or using the CPU instruction $\operatorname{\_\_popcnt}$ for Hamming distance) according to (the hash code of) the query and the hash code of the reference item, and retrieve the reference items with the smallest distances as the candidates of nearest neighbors. Usually this is followed by a reranking step: rerank the retrieved nearest neighbor candidates according to the true distances computed using the original features and attain the nearest neighbors.

This strategy exploits one main advantage of hash codes: the distance using hash codes is efficiently computed and the cost is much smaller than that of the distance computation in the original input space.

Comments: Hash table lookup is mainly used in locality sensitive hashing, and has been used for evaluating learning to hash in a few publications. It has been pointed in and also observed from empirical results that LSH-based hash table lookup, except min-hash, is rarely adopted in reality, while hash table lookup with quantization-based hash codes is widely used in the non-exhaustive strategy to retrieve coarse candidates . Hash code ranking goes through all the candidates and thus is inferior in search efficiency compared with hash table lookup which only checks a small subset of candidates, which are determined by a lookup radius.

A practical way is to do a non-exhaustive search which is suggested in : first retrieve a small set of candidates using the inverted index that can be viewed as a hash table, and then compute the distances of the query to the candidates using the hash codes which are longer, providing the top candidates subsequently reranked using the original features. Other research efforts include organizing the hash codes to avoid the exhaustive search with a data structure, such as a tree or a graph structure .

Learning to Hash

Learning to hash is the task of learning a (compound) hash function, $\mathbf{y}=\mathbf{h}(\mathbf{x})$, mapping an input item $\mathbf{x}$ to a compact code $\mathbf{y}$, aiming that the nearest neighbor search result for a query $\mathbf{q}$ is as close as possible to the true nearest search result and the search in the coding space is also efficient. A learning-to-hash approach needs to consider five problems: what hash function $\mathbf{h}(\mathbf{x})$ is adopted, what similarity in the coding space is used, what similarity is provided in the input space, what loss function is chosen for the optimization objective, and what optimization technique is adopted.

The hash function can be based on linear projection, kernels, spherical function, (deep) neural networks, a non-parametric function, and so on. One popular hash function is the linear hash function, e.g., :

where $\operatorname{sgn}(z)=1$ if $z\geqslant 0$ and $\operatorname{sgn}(z)=0$ (or equivalently $-1$) otherwise, $\mathbf{w}$ is the projection vector, and $b$ is the bias variable. The kernel function,

is also adopted in some approaches, e.g., , where $\{\mathbf{s}_{t}\}$ is a set of representative samples that are randomly drawn from the dataset or cluster centers of the dataset and $\{w_{t}\}$ are the weights. The non-parametric function based on nearest vector assignment is widely used for quantization-based solutions:

The form of hash function is an important factor influencing the search accuracy using the hash codes, as well as the time cost of computing hash codes. A linear function is efficiently evaluated, while the kernel function and the nearest vector assignment based function lead to better search accuracy as they are more flexible. Almost all the methods using a linear hash function can be extended to nonlinear hash functions, such as kernelized hash functions, or neural networks. Thus we do not use the hash function to categorize the hash algorithms.

2 Similarity

In the input space the distance $d^{o}_{ij}$ between any pair of items $(\mathbf{x}_{i},\mathbf{x}_{j})$ could be the Euclidean distance, $\|\mathbf{x}_{i}-\mathbf{x}_{j}\|_{2}$ or others. The similarity $s^{o}_{ij}$ is often defined as a function about the distance $d^{o}_{ij}$, and a typical function is the Gaussian function: $s^{o}_{ij}=g(d^{o}_{ij})=\exp{(-\frac{(d^{o}_{ij})^{2}}{2\sigma^{2}})}$. There exist other similarity forms, such as cosine similarity $\frac{\mathbf{x}_{i}^{\top}\mathbf{x}_{j}}{\|\mathbf{x}_{i}\|_{2}\|\mathbf{x}_{j}\|_{2}}$ and so on. Besides, the semantic similarity is often used for semantic similarity search. In this case, the similarity $s^{o}_{ij}$ is usually binary, valued $1$ if the two items $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ belong to the same semantic class, (or $-1$) otherwise. The hashing algorithms for semantic similarity usually can be applied to other distances, such as Euclidean distance, by defining a pseudo-semantic similarity: $s^{o}_{ij}=1$ for nearby points $(i,j)$ and $s^{o}_{ij}=0$ (or $-1$) for farther points $(i,j)$.

In the hash coding space, the typical distance $d^{h}_{ij}$ between $\mathbf{y}_{i}$ and $\mathbf{y}_{j}$ is the Hamming distance. It is defined as the number of bits where the values are different and is mathematically formulated as

which is equivalent to $d^{h}_{ij}=\|\mathbf{y}_{i}-\mathbf{y}_{j}\|_{1}$ if the code is valued by $1$ and . The distance for the codes valued by $1$ and $-1$ is similarly defined. The similarity based on the Hamming distance is defined as $s^{h}_{ij}=M-d^{h}_{ij}$ for the codes valued by $1$ and , computing the number of bits where the values are the same. The inner product $s^{h}_{ij}=\mathbf{y}_{i}^{\top}\mathbf{y}_{j}$ is used as the similarity for the codes valued by $1$ and $-1$. These measures are also extended to the weighted case: e.g., $d^{h}_{ij}=\sum_{m=1}^{M}\lambda_{m}\delta[y_{im}\neq y_{jm}]$ and $s^{h}_{ij}=\mathbf{y}_{i}^{\top}\boldsymbol{\Lambda}\mathbf{y}_{j}$, where $\boldsymbol{\Lambda}=\operatorname{Diag}(\lambda_{1},\lambda_{2},\cdots,\lambda_{M})$ is a diagonal matrix and each diagonal entry is the weight of the corresponding hash code.

Besides the Hamming distance/similarity and its variants, the Euclidean distance is typically used in quantization approaches, and is evaluated between the vectors corresponding to the hash codes, $d^{h}_{ij}=\|\mathbf{c}_{y_{i}}-\mathbf{c}_{y_{j}}\|_{2}$ (symmetric distance) or between the query $\mathbf{q}$ and the center that is the approximation to $\mathbf{x}_{j}$, $d^{h}_{qj}=\|\mathbf{q}-\mathbf{c}_{y_{j}}\|_{2}$ (asymmetric distance, which is preferred because the accuracy is higher and the time cost is almost the same). The distance is usually evaluated in the search stage efficiently by using a distance lookup table. There are also some works learning/optimizing the distances between hash codes after the hash codes are already computed.

3 Loss Function

The basic rule of designing the loss function is to preserve the similarity order, i.e., minimize the gap between the approximate nearest neighbor search result computed from the hash codes and the true search result obtained from the input space.

The widely-used solution is pairwise similarity preserving, making the distances or similarities between a pair of items from the input and coding spaces as consistent as possible. The multiwise similarity preserving solution, making the order among multiple items computed from the input and coding spaces as consistent as possible, is also studied. One class of solutions, e.g., spatial partitioning, implicitly preserve the similarities. The quantization-based solution and other reconstruction-based solutions aim to find the optimal approximation of the item in terms of the reconstruction error through a reconstruction function (e.g., in the form of a lookup table in quantization or an auto-encoder in ). Besides similarity preserving items, some approaches introduce bucket balance or its approximate variants as extra constraints, which is also important for obtaining better results or avoiding trivial solutions.

4 Optimization

The challenges for optimizing the hash function parameters lie in two main factors. One is that the problem contains the $\operatorname{sgn}$ function, which leads to a challenging mixed-binary-integer optimization problem. The other is that the time complexity is high when processing a large number of data points, which is usually handled by sampling a subset of points or a subset of constraints (or equivalent basic terms in the objective functions).

The ways to handle the $\operatorname{sgn}$ function are summarized below. The first way is the most widely-adopted continuous relaxation, including sigmoid relaxation, tanh relaxation, and directly dropping the sign function $\operatorname{sgn}(z)\approx z$. The relaxed problem is then solved using various standard optimization techniques. The second one is a two-step scheme with its extension to alternative optimization : optimizing the binary codes without considering the hash function, followed by estimating the function parameters from the optimized hash codes. The third one is discretization: drop the sign function $\operatorname{sgn}(z)\approx z$ and regard the hash code as an approximation of the hash function, which is formulated as a loss $(y-z)^{2}$. There also exist other ways only adopted in a few algorithms, e.g., transforming the problem into a latent structure-SVM formulation in , the coordinate-descent approach in (fixing all but one weight, optimize the original objective with respect to a single weight in each iteration), both of which do not conduct continuous relaxation.

5 Categorization

Our survey categorizes the existing algorithms to various classes: the pairwise similarity preserving class, the multiwise similarity preserving class, the implicit similarity preserving class, as well as the quantization class, according to what similarity preserving manner is adopted to formulate the objective function. We separate the quantization class from the pairwise similarity preserving class as they are very different in formulation though the quantization class can be explained from the perspective of pairwise similarity preserving. In the following description, we may call quantization as quantization-based hashing and other algorithms in which a hash function generates a binary value as binary code hashing. In addition, we will also discuss other studies on learning to hash. The summary of the representative algorithms is given in Table I.

The main reason we choose the similarity preserving manner to do the categorization is that similarity preservation is the essential goal of hashing. It should be noted that as pointed in , other factors, such as the hash function, or the optimization algorithm, is also important for the search performance.

Pairwise Similarity Preserving

The algorithms aligning the distances or similarities of a pair of items computed from the input space and the Hamming coding space are roughly divided in the following groups:

Similarity-distance product minimization (SDPM): $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}s_{ij}^{o}d_{ij}^{h}$. The distance in the coding space is expected to be smaller if the similarity in the original space is larger. Here $\mathcal{E}$ is a set of pairs of items that are considered.

Similarity-similarity product maximization (SSPM): $\operatorname{max}\sum_{(i,j)\in\mathcal{E}}s_{ij}^{o}s_{ij}^{h}$. The similarity in the coding space is expected to be larger if the similarity in the original space is larger.

Distance-distance product maximization (DDPM): $\operatorname{max}\sum_{(i,j)\in\mathcal{E}}d_{ij}^{o}d_{ij}^{h}$. The distance in the coding space is expected to be larger if the distance in the original space is larger.

Distance-similarity product minimization (DSPM): $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}d_{ij}^{o}s_{ij}^{h}$. The similarity in the coding space is expected to be smaller if the distance in the original space is larger.

Similarity-similarity difference minimization (SSDM): $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}(s_{ij}^{o}-s_{ij}^{h})^{2}$. The difference between the similarities is expected to be as small as possible.

Distance-distance difference minimization (DDDM): $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}(d_{ij}^{o}-d_{ij}^{h})^{2}$. The difference between the distances is expected to be as small as possible.

Normalized similarity-similarity divergence minimization (NSSDM): $\operatorname{min~{}KL}(\{\bar{s}_{ij}^{o}\},\{\bar{s}_{ij}^{h}\})=\operatorname{min}(-\sum_{(i,j)\in\mathcal{E}}\bar{s}_{ij}^{o}\operatorname{log}\bar{s}_{ij}^{h})$. Here $\bar{s}_{ij}^{o}$ and $\bar{s}_{ij}^{h}$ are normalized similarities in the input space and the coding space: $\sum_{ij}\bar{s}_{ij}^{o}=1$ and $\sum_{ij}\bar{s}_{ij}^{h}=1$.

The following reviews these groups of algorithms except the distance-similarity product minimization group for which we are not aware of any algorithm belonging to. It should be noted that merely optimizing the above similarity preserving function, e.g., SDPM and SSPM, is not enough and may lead to trivial solutions, and it is necessary to combine other constraints, which is detailed in the following discussion. We also point out the relation between similarity-distance product minimization and similarity-similarity product maximization, the relation between similarity-similarity product maximization and similarity-similarity difference minimization, as well as the relation between distance-distance product maximization and distance-distance difference minimization.

We first introduce spectral hashing and its extensions, and then review other forms.

The goal of spectral hashing is to minimize $\sum_{(i,j)\in\mathcal{E}}s_{ij}^{o}d_{ij}^{h}$, where the Euclidean distance in the hashing space, $d_{ij}^{h}=\|\mathbf{y}_{i}-\mathbf{y}_{j}\|_{2}^{2}$, is used for formulation simplicity and optimization convenience, and the similarity in the input space is defined as: $s_{ij}^{o}=\exp{(-\frac{\|\mathbf{x}_{i}-\mathbf{x}_{j}\|_{2}^{2}}{2\sigma^{2}})}$. Note that the Hamming distance in the search stage can be still used for higher efficiency as the Euclidean distance and the Hamming distance in the coding space are consistent: the larger the Euclidean distance, the larger the Hamming distance. The objective function can be written in a matrix form,

where $\mathbf{Y}=[\mathbf{y}_{1}~{}\mathbf{y}_{2}\cdots\mathbf{y}_{N}]$ is a matrix of $M\times N$, $\mathbf{S}=[s^{o}_{ij}]_{N\times N}$ is the similarity matrix, and $\mathbf{D}=\operatorname{diag}(d_{11},\cdots,d_{NN})$ is a diagonal matrix, $d_{nn}=\sum_{i=1}^{N}s^{o}_{ni}$.

There is a trivial solution to the problem (4): $\mathbf{y}_{1}=\mathbf{y}_{2}=\cdots=\mathbf{y}_{N}$. To avoid it, the code balance condition is introduced: the number of data items mapped to each hash code is the same. Bit balance and bit uncorrelation are used to approximate the code balance condition. Bit balance means that each bit has about $50\%$ chance of being $1$ or $-1$. Bit uncorrelation means that different bits are uncorrelated. The two conditions are formulated as,

where $\mathbf{1}$ is an $N$-dimensional all-$1$ vector, and $\mathbf{I}$ is an identity matrix of size $N$.

Under the assumption of separate multi-dimensional uniform data distribution, the hashing algorithm is given as follows,

Find the principal components of the $N$ $d$-dimensional reference data items using principal component analysis (PCA).

Compute the $M$ one-dimensional Laplacian eigenfunctions with the $M$ smallest eigenvalues along each PCA direction ($d$ directions in total).

Pick the $M$ eigenfunctions with the smallest eigenvalues among $Md$ eigenfunctions.

Threshold the eigenfunction at zero, obtaining the binary codes.

The one-dimensional Laplacian eigenfunction for the case of uniform distribution on $[r_{l},r_{r}]$ is $\phi_{m}(x)=\sin(\frac{\pi}{2}+\frac{m\pi}{r_{r}-r_{l}}x)$, and the corresponding eigenvalue is $\lambda_{m}=1-\exp{(-\frac{\epsilon^{2}}{2}|\frac{m\pi}{r_{r}-r_{l}}|^{2})}$, where $m$ ($=1,2,\cdots$) is the frequency and $\epsilon$ is a fixed small value. The hash function is formally written as $h(\mathbf{x})=\operatorname{sgn}(\sin(\frac{\pi}{2}+\gamma\mathbf{w}^{\top}\mathbf{x}))$, where $\gamma$ depends on the frequency $m$ and the range of the projection along the direction $\mathbf{w}$.

Analysis: In the case the spreads along the top $M$ PCA directions are the same, the hashing algorithm partitions each direction into two parts using the median (due to the bit balance requirement) as the threshold, which is equivalent to thresholding at the mean value under the assumption of uniform data distributions. In the case that the true data distribution is a multi-dimensional isotropic Gaussian distribution, the algorithm is equivalent to two quantization algorithms: iterative quantization , and isotropic hashing .

Regarding the performance, this method performs well for a short hash code but poor for a long hash code. The reason includes three aspects. First, the assumption that the data follow a uniform distribution does not hold in real cases. Second, the eigenvalue monotonously decreases with respect to $|\frac{m}{r_{r}-r_{l}}|^{2}$, which means that the PCA direction with a large spread ($|r_{r}-r_{l}|$) and a lower frequency ($m$) is preferred. Hence there might be more than one eigenfunction picked along a single PCA direction, which breaks the uncorrelation requirement. Last, thresholding the eigenfunction $\phi_{m}(x)=\sin(\frac{\pi}{2}+\frac{m\pi}{r_{r}-r_{l}}x)$ at zero leads to that near points may be mapped to different hash values and farther points may be mapped to the same hash value. As a result, the Hamming distance is not well consistent to the distance in the input space.

Extensions: There are some extensions using PCA. (1) Principal component hashing uses the principal direction to formulate the hash function; (2) Searching with expectations and transform coding that transforms the data using PCA and then adopts the rate distortion optimization (bits allocation) approach to determine which principal direction is used and how many bits are assigned to such a direction; (3) Double-bit quantization that handles the third drawback in spectral hashing by distributing two bits into each projection direction, conducting only $3$-cluster quantization, and assigning $01$, $00$, and $11$ to each cluster. Instead of PCA, ICA hashing adopts independent component analysis for hashing and uses bit balance and bit mutual information minimization for code balance.

There are many other extensions in a wide range, including similarity graph extensions , ,,,,, ,, hash function extensions ,, weighted Hamming distance , self-taught hashing , sparse hash codes , discrete hashing , and so on.

1.2 Variants

Linear discriminant analysis (LDA) hashing minimizes a form of the loss function: $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}s_{ij}^{o}d_{ij}^{h}$, where $d_{ij}^{h}=\|\mathbf{y}_{i}-\mathbf{y}_{j}\|_{2}^{2}$. Different from spectral hashing, (1) $s_{ij}^{o}=1$ if data items $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ are a similar pair, $(i,j)\in\mathcal{E}^{+}$, and $s_{ij}^{o}=-1$ if data items $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ are a dissimilar pair, $(i,j)\in\mathcal{E}^{-}$ (2) a linear hash function is used: $\mathbf{y}=\operatorname{sgn}(\mathbf{W}^{\top}\mathbf{x}+\mathbf{b})$, and (3) a weight $\alpha$ is imposed to $s_{ij}^{o}d_{ij}^{h}$ for the similar pair. As a result, the objective function is written as:

The projection matrix $\mathbf{W}$ and the threshold $\mathbf{b}$ are separately optimized: (1) to estimate the orthogonal matrix $\mathbf{W}$, drop the $\operatorname{sgn}$ function in Equation (6), leading to an eigenvalue decomposition problem; (2) estimate $\mathbf{b}$ by minimizing Equation (6) with fixed $\mathbf{W}$ through a simple $1$D search scheme. A similar loss function, contrastive loss, is adopted in with a different optimization technique.

The loss function in minimal loss hashing is in the form of $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}s_{ij}^{o}d_{ij}^{h}$. Similar to LDA hashing, $s_{ij}^{o}=1$ if $(i,j)\in\mathcal{E}^{+}$ and $s_{ij}^{o}=-1$ if $(i,j)\in\mathcal{E}^{-}$. Differently, the distance is hinge-like: $d^{h}_{ij}=\max(\|\mathbf{y}_{i}-\mathbf{y}_{j}\|_{1}+1,\rho)$ for $(i,j)\in\mathcal{E}^{+}$ and $d^{h}_{ij}=\min(\|\mathbf{y}_{i}-\mathbf{y}_{j}\|_{1}-1,\rho)$ for $(i,j)\in\mathcal{E}^{-}$. The intuition is that there is no penalty if the Hamming distance for similar pairs is small enough and if the Hamming distance for dissimilar pairs is large enough. The formulation, if $\rho$ is fixed, is equivalent to,

where $\rho$ is a hyper-parameter used as a threshold in the Hamming space to differentiate similar pairs from dissimilar pairs, $\lambda$ is another hyper-parameter that controls the ratio of the slopes for the penalties incurred for similar (or dissimilar) points. The hash function is in the linear form: $\mathbf{y}=\operatorname{sgn}(\mathbf{W}^{\top}\mathbf{x})$. The projection matrix $\mathbf{W}$ is estimated by transforming $\mathbf{y}=\operatorname{sgn}(\mathbf{W}^{\top}\mathbf{x})=\arg\max_{\mathbf{y}^{\prime}\in\mathcal{H}}\mathbf{h}^{\prime\top}\mathbf{W}^{\top}\mathbf{x}$ and optimizing using structured prediction with latent variables. The hyper-parameters $\rho$ and $\lambda$ are chosen via cross-validation.

Comments: Besides the optimization techniques, the main differences of the three representative algorithms, i.e., spectral hashing, LDA hashing, and minimal loss hashing, are twofold. First, the similarity in the input space in spectral hashing is defined as a continuous positive number computed from the Euclidean distance, while in LDA hashing and minimal loss hashing the similarity is set to $1$ for a similar pair and $-1$ for a dissimilar pair. Second, the distance in the hashing space for minimal loss hashing is different from spectral hashing and LDA hashing.

2 Similarity-Similarity Product Maximization

Semi-supervised hashing , , is the representative algorithm in this group. The objective function is $\operatorname{max}\sum_{(i,j)\in\mathcal{E}}s_{ij}^{o}s_{ij}^{h}$. The similarity $s_{ij}^{o}$ in the input space is $1$ if the pair of items $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ belong to the same class or are nearby points, and $-1$ otherwise. The similarity in the coding space is defined as $s_{ij}^{h}=\mathbf{y}_{i}^{\top}\mathbf{y}_{j}$. Thus, the objective function is rewritten as maximizing:

The hash function is in a linear form $\mathbf{y}=\mathbf{h}(\mathbf{x})=\operatorname{sgn}(\mathbf{W}^{\top}\mathbf{x})$. Besides, the bit balance is also considered, and is formulated as maximizing the variance, $\operatorname{trace}(\mathbf{Y}\mathbf{Y}^{\top})$, rather than letting the mean be , $\mathbf{Y}\mathbf{1}=0$. The overall objective is to maximize

subject to $\mathbf{W}^{\top}\mathbf{W}=\mathbf{I}$, which is a relaxation of the bit uncorrelation condition. The estimation of $\mathbf{W}$ is done by directly dropping the $\operatorname{sgn}$ operator.

An unsupervised extension is given in : sequentially compute the projection vector $\{\mathbf{w}_{m}\}_{m=1}^{M}$ from $\mathbf{w}_{1}$ to $\mathbf{w}_{M}$ by optimizing the problem 9. In particular, the first iteration computes the PCA direction as the first $\mathbf{w}$, and at each of the later iterations, $s_{ij}^{o}=1$ if nearby points are mapped to different hash values in the previous iterations, and $s_{ij}^{o}=-1$ if far points are mapped to same hash values in the previous iterations. An extension of the semi-supervised hashing to nonlinear hash functions is presented in using the kernel hash function. An iterative two-step optimization using graph cuts is given in .

Comments: It is interesting to note that $\sum_{(i,j)\in\mathcal{E}}s^{o}_{ij}\mathbf{y}_{i}^{\top}\mathbf{y}_{j}=\texttt{const}-\frac{1}{2}\sum_{(i,j)\in\mathcal{E}}s^{o}_{ij}\|\mathbf{y}_{i}-\mathbf{y}_{j}\|_{2}^{2}=\texttt{const}-\frac{1}{2}\sum_{(i,j)\in\mathcal{E}}s^{o}_{ij}d_{ij}^{h}$ if $\mathbf{y}\in\{1,-1\}^{M}$, where const is a constant variable (and thus $\operatorname{trace}(\mathbf{Y}\mathbf{S}\mathbf{Y}^{\top})=\texttt{const}-\operatorname{trace}(\mathbf{Y}(\mathbf{D}-\mathbf{S})\mathbf{Y}^{\top})$). In this case, similarity-similarity product maximization is equivalent to similarity-distance product minimization.

3 Distance-Distance Product Maximization

The mathematical formulation of distance-distance product maximization is $\operatorname{max}\sum_{(i,j)\in\mathcal{E}}d_{ij}^{o}d_{ij}^{h}$. Topology preserving hashing formulates the objective function by starting with this rule:

where $\mathbf{L}_{d}=\operatorname{Diag}\{\mathbf{D}^{o}\mathbf{1}\}-\mathbf{D}^{o}$ and $\mathbf{D}^{o}=[d^{o}_{ij}]_{N\times N}$.

In addition, similarity-distance product minimization is also considered:

The overall formulation is given as follows,

where $\alpha\mathbf{I}$ is introduced as a regularization term, $\operatorname{trace}(\mathbf{Y}\mathbf{Y}^{\top})$, maximizing the variances, which is the same for semi-supervised hashing for bit balance. The problem is optimized by dropping the $\operatorname{sgn}$ operator in the hash function $\mathbf{y}=\operatorname{sgn}(\mathbf{W}^{\top}\mathbf{x})$ and letting $\mathbf{W}^{\top}\mathbf{X}\mathbf{L}\mathbf{X}^{\top}\mathbf{W}$ be an identity matrix.

4 Distance-Distance Difference Minimization

Binary reconstructive embedding belongs to this group: $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}(d_{ij}^{o}-d_{ij}^{h})^{2}$. The Euclidean distance is used in both the input and coding spaces. The objective function is formulated as follows,

where $\{\mathbf{s}_{mt}\}_{t=1}^{T_{m}}$ are sampled data items, $K(\cdot,\cdot)$ is a kernel function, and $\{w_{mt}\}$ are the weights to be learnt.

Instead of relaxing or dropping the $\operatorname{sgn}$ function, a coordinate descent optimization scheme is presented in : fix all but one weight $w_{mt}$ and optimize the problem 13 with respect to $w_{mt}$. There is an exact, optimal update to this weight $w_{mt}$ (fixing all the other weights), which is achieved with the time complexity $O(N\log N+|\mathcal{E}|)$. Alternatively, a two-step solution is presented in : first relax the binary variables to $(0,1)$ and optimize the problem via an augmented Lagrangian formulation and a nonnegative matrix factorization formulation.

Comments: We have the following equation,

This shows that the difference between distance-distance difference minimization and distance-distance product maximization lies on $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}(d_{ij}^{h})^{2}$, minimizing the distances between the data items in the hash space. This could be regarded as a regularizer, complementary to distance-distance product maximization $\operatorname{max}\sum_{(i,j)\in\mathcal{E}}d_{ij}^{o}d_{ij}^{h}$ which tends to maximize the distances between the data items in the hash space.

5 Similarity-Similarity Difference Minimization

Similarity-similarity difference minimization is mathematically formulated as $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}(s_{ij}^{o}-s_{ij}^{h})^{2}$. Supervised hashing with kernels , one representative approach in this group, aims to minimize an objective function,

where $s^{o}_{ij}=1$ if $(i,j)$ is similar, and $s^{o}_{ij}=-1$ if it is dissimilar. $\mathbf{y}=\mathbf{h}(\mathbf{x})$ is a kernel hash function. Kernel reconstructive hashing extends this technique using a normalized Gaussian kernel similarity. Scalable graph hashing uses the feature transformation to approximate the similarity matrix (graph) without explicitly computing the similarity matrix. Binary hashing solves the problem using a two-step approach, in which the first step adopts semi-definite relaxation and augmented lagrangian to estimate the discrete labels.

Comments: We have the following equation,

This shows that the difference between similarity-similarity difference minimization and similarity-similarity product maximization lies in $\operatorname{min}\sum_{(i,j)\in\mathcal{E}}(s_{ij}^{h})^{2}$, minimizing the similarities between the data items in the hash space, intuitively letting the hash codes be as different as possible. This could be regarded as a regularizer complementary to similarity-similarity product maximization $\operatorname{max}\sum_{(i,j)\in\mathcal{E}}s_{ij}^{o}s_{ij}^{h}$, which has a trivial solution: the hash codes are the same for all data points.

Extensions and variants: Multi-dimensional spectral hashing uses a similar objective function, but with a weighted Hamming distance,

where $\boldsymbol{\Lambda}$ is a diagonal matrix. Both $\boldsymbol{\Lambda}$ and hash codes $\{\mathbf{y}_{i}\}$ are needed to be optimized. The algorithm for solving the problem 22 to compute the hash codes is similar to that given in spectral hashing . Bilinear hyperplane hashing extends the formulation of supervised hashing with kernels by introducing a bilinear hyperplane hashing function. Label-regularized maximum margin hashing formulates the objective function from three components: the similarity-similarity difference, a hinge loss from the hash function, and the maximum margin part.

6 Normalized Similarity-Similarity Divergence Minimization

Spec hashing , belonging to this group, views each pair of data items as a sample and their (normalized) similarity as the probability, and finds the hash functions so that the probability distributions from the input space and the coding space are well aligned. The objective function is written as follows,

Here, $\bar{s}_{ij}^{o}$ is the normalized similarity in the input space, $\sum_{ij}\bar{s}_{ij}^{o}=1$. $\bar{s}^{h}_{ij}$ is the normalized similarity in the Hamming space, $\bar{s}^{h}_{ij}=\frac{1}{Z}\exp{(-\lambda d^{h}_{ij})}$, where $Z$ is a normalization variable $Z=\sum_{ij}\exp{(-\lambda d^{h}_{ij})}$.

Supervised binary hash code learning presents a supervised learning algorithm based on the Jensen-Shannon divergence which is derived from minimizing an upper bound of the probability of Bayes decision errors.

Multiwise Similarity Preserving

This section reviews the category of hashing algorithms that formulate the loss function by maximizing the agreement of the similarity orders over more than two items computed from the input space and the coding space.

Order preserving hashing aims to learn hash functions through aligning the orders computed from the original space and the ones in the coding space. Given a data point $\mathbf{x}_{n}$, the database points $\mathcal{X}$ are divided into $(M+1)$ categories, $(\mathcal{C}^{h}_{n0},\mathcal{C}^{h}_{n1},\cdots,\mathcal{C}^{h}_{nM})$, where $\mathcal{C}^{h}_{nm}$ corresponds to the items whose distance to the given point is $m$, and $(\mathcal{C}^{o}_{n0},\mathcal{C}^{o}_{n1},\cdots,\mathcal{C}^{o}_{nM})$, using the distances in the hashing space and the distances in the input (original) space, respectively. $(\mathcal{C}^{o}_{n0},\mathcal{C}^{o}_{n1},\cdots,\mathcal{C}^{o}_{nM})$ is constructed such that in the ideal case the probability of assigning an item to any hash code is the same. The basic objective function maximizing the alignment between the two categories is given as follows,

where $|\mathcal{C}^{o}_{nm}-\mathcal{C}^{h}_{nm}|$ is the cardinality of the difference of the two sets. The linear hash function $\mathbf{h}(\mathbf{x})$ is used and dropping the $\operatorname{sgn}$ function is adopted for optimization.

Instead of preserving the order, KNN hashing directly maximizes the kNN accuracy of the search result, which is solved by using the factorized neighborhood representation to parsimoniously model the neighborhood relationships inherent in the training data.

Triplet loss hashing formulates the hashing problem by maximizing the similarity order agreement defined over triplets of items, $\{(\mathbf{x},\mathbf{x}^{+},\mathbf{x}^{-})\}$, where the pair $(\mathbf{x},\mathbf{x}^{-})$ is less similar than the pair $(\mathbf{x},\mathbf{x}^{+})$. The triplet loss is defined as

The objective function is given as follows,

where $\mathbf{h}(\mathbf{x})=\mathbf{h}(\mathbf{x};\mathbf{W})$ is the compound hash function. The problem is optimized using the algorithm similar to minimal loss hashing . The extension to asymmetric Hamming distance is also discussed in . Binary optimized hashing also uses a triplet loss function, with a slight different distance measure in the Hamming space and a different optimization technique.

Top rank supervised binary coding presents another form of triplet losses in order to penalize the samples that are incorrectly ranked at the top of a Hamming-distance ranking list more than those at the bottom.

Listwise supervision hashing also uses triplets of items. The formulation is based on a triplet tensor $\mathbf{S}^{o}$ defined as follows,

The objective is to maximize triple-similarity-triple-similarity product:

where $s^{h}_{ijk}$ is a ranking triplet computed by the binary code using the cosine similarity, $s^{h}_{ijk}=\operatorname{sgn}(\mathbf{h}(\mathbf{q}_{i})^{\top}\mathbf{h}(\mathbf{x}_{j})-\mathbf{h}(\mathbf{q}_{i})^{\top}\mathbf{h}(\mathbf{x}_{k}))$. Through dropping the $\operatorname{sgn}$ function, the objective function is transformed to

which is solved by dropping the $\operatorname{sgn}$ operator in the hash function $\mathbf{h}(\mathbf{x})=\operatorname{sgn}(\mathbf{W}^{\top}\mathbf{x})$.

Comments: Order preserving hashing considers the relation between the search lists while triplet loss hashing and listwise supervision hashing consider triplewise relation. The central ideas of triplet loss hashing and listwise supervision hashing are very similar, and their difference lies in how to formulate the loss function besides the different optimization techniques they adopted.

Implicit Similarity Preserving

We review the category of hashing algorithms that focus on pursuing effective space partitioning without explicitly evaluating the relation between the distances/similarities in the input and coding spaces. The common idea is to partition the space, formulated as a classification problem, with the maximum margin criterion or the code balance condition.

Random maximum margin hashing learns a hash function with the maximum margin criterion. The point is that the positive and negative labels are randomly generated by randomly sampling $N$ data items and randomly labeling half of the items with $-1$ and the other half with $1$. The formulation is a standard SVM formulation that is equivalent to the following form,

where $\{\mathbf{x}_{i}^{+}\}$ are the positive samples and $\{\mathbf{x}_{i}^{-}\}$ are the negative samples. Note that this is different from PICODES as random maximum margin hashing adopts the hyperplanes learnt from SVM to form the hash functions while PICODES exploits the hyperplanes to check whether the hash codes are semantically separable rather than forming hash functions.

Complementary projection hashing , similar to complementary hashing , finds the hash function such that the items are as far away as possible from the partition plane corresponding to the hash function. It is formulated as $\mathcal{H}(\epsilon-|\mathbf{w}^{\top}\mathbf{x}+b|)$, where $\mathcal{H}(\cdot)=\frac{1}{2}(1+\operatorname{sgn}(\cdot))$ is the unit step function. Moreover, the bit balance condition, $\mathbf{Y}\mathbf{1}=0$, and the bit uncorrelation condition, the non-diagonal entries in $\mathbf{Y}\mathbf{Y}\top$ are , are considered. An extension is also given by using the kernel hash function. In addition, when learning the $m$th hash function, the data item is weighted by a variable, which is computed according to the previously computed $(m-1)$ hash functions.

Spherical hashing uses a hypersphere to partition the space. The spherical hash function is defined as $h(\mathbf{x})=1$ if $d(\mathbf{p},\mathbf{x})\leqslant t$ and $h(\mathbf{x})=0$ otherwise. The compound hash function consists of $M$ spherical functions, depending on $M$ pivots $\{\mathbf{p}_{1},\cdots,\mathbf{p}_{M}\}$ and $M$ thresholds $\{t_{1},\cdots,t_{M}\}$. The distance in the coding space is defined based on the distance: $\frac{\|\mathbf{y}_{1}-\mathbf{y}_{2}\|_{1}}{\mathbf{y}_{1}^{T}\mathbf{y}_{2}}$. Unlike the pairwise and multiwise similarity preserving algorithms, there is no explicit function penalizing the disagreement of the similarities computed in the input and coding spaces. The $M$ pivots and thresholds are learnt such that it satisfies a pairwise bit balance condition: $|\{\mathbf{x}~{}|~{}h_{m}(\mathbf{x})=1\}|=|\{\mathbf{x}~{}|~{}h_{m}(\mathbf{x})=0\}|$, and $|\{\mathbf{x}~{}|~{}h_{i}(\mathbf{x})=b_{1},h_{j}(\mathbf{x})=b_{2}\}|=\frac{1}{4}|\mathcal{X}|,b_{1},b_{2}\in\{0,1\},i\neq j$.

Quantization

The following provides a simple derivation showing that the quantization approach can be derived from the distance-distance difference minimization criterion. There is a similar statement in obtained from the statistical perspective: the distance reconstruction error is statistically bounded by the quantization error. Considering two points $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ and their approximations $\mathbf{z}_{i}$ and $\mathbf{z}_{j}$, we have

Thus, $|d^{o}_{ij}-d^{h}_{ij}|^{2}\leqslant 2(|\mathbf{x}_{j}-\mathbf{z}_{j}|^{2}_{2}+|\mathbf{x}_{i}-\mathbf{z}_{i}|^{2}_{2})$, and

This means that the distance-distance difference minimization rule is transformed to minimizing its upper-bound, the quantization error, which is described as a theorem below.

The distortion error in the quantization approach is an upper bound (with a scale) of the differences between the pairwise distances computed from the input features and from the approximate representation.

The quantization approach for hashing is roughly divided into two main groups: hypercubic quantization, in which the approximation $\mathbf{z}$ is equal to the hash code $\mathbf{y}$, and Cartesian quantization, in which the approximation $\mathbf{z}$ corresponds to a vector formed by the hash code $\mathbf{y}$, e.g., $\mathbf{y}$ represents the index of a set of candidate approximations. In addition, we will review the related reconstruction-based hashing algorithms.

Hypercubic quantization refers to a category of algorithms that quantize a data item to a vertex in a hypercubic, i.e., a vector belonging to a set $\{[y_{1}~{}y_{2}~{}\cdots~{}y_{M}]^{\top}~{}|~{}y_{m}\in\{-1,1\}\}$ or the rotated hypercubic vertices. It is in some sense related to $1$-bit compressive sensing : Its goal is to design a measurement matrix $\mathbf{A}$ and a recovery algorithm such that a k-sparse unit vector $\mathbf{x}$ can be efficiently recovered from the sign of its linear measurements, i.e., $\mathbf{b}=\operatorname{sgn}(\mathbf{A}\mathbf{x})$, while hypercubic quantization aims to find the matrix $\mathbf{A}$ which is usually a rotation matrix, and the codes $\mathbf{b}$, from the input $\mathbf{x}$.

The widely-used scalar quantization approach with only one bit assigned to each dimension can be viewed as a hypercubic quantization approach, and can be derived by minimizing

subject to $\mathbf{y}_{i}\in\{1,-1\}$. The local digit coding approach also belongs to this category.

Iterative quantization , preprocesses the data, by reducing the dimension using PCA to $M$ dimensions, $\mathbf{v}=\mathbf{P}^{\top}\mathbf{x}$, where $\mathbf{P}$ is a matrix of size $d\times M$ ($M\leqslant d$) computed using PCA, and then finds an optimal rotation $\mathbf{R}$ followed by a scalar quantization. The formulation is given as,

where $\mathbf{R}$ is a matrix of $M\times M$, $\mathbf{V}=[\mathbf{v}_{1}\mathbf{v}_{2}\cdots\mathbf{v}_{N}]$ and $\mathbf{Y}=[\mathbf{y}_{1}\mathbf{y}_{2}\cdots\mathbf{y}_{N}]$.

The problem is solved via alternative optimization. There are two alternative steps. Fixing $\mathbf{R}$, $\mathbf{Y}=\operatorname{sgn}(\mathbf{R}^{\top}\mathbf{V})$. Fixing $\mathbf{B}$, the problem becomes the classic orthogonal Procrustes problem, and the solution is $\mathbf{R}=\hat{\mathbf{S}}\mathbf{S}^{\top}$, where $\mathbf{S}$ and $\hat{\mathbf{S}}$ is obtained from the SVD of $\mathbf{Y}\mathbf{V}^{\top}$, $\mathbf{Y}\mathbf{V}^{\top}=\mathbf{S}\boldsymbol{\Lambda}\hat{\mathbf{S}}^{\top}$.

Comments: We present an integrated objective function that is able to explain the necessity of PCA dimension reduction. Let $\bar{\mathbf{y}}$ be a $d$-dimensional vector, which is a concatenated vector from $\mathbf{y}$ and an all-zero subvector: $\bar{\mathbf{y}}=[\mathbf{y}^{\top}0...0]^{\top}$. The integrated objective function is written as follows:

where $\bar{\mathbf{Y}}=[\bar{\mathbf{y}}_{1}\bar{\mathbf{y}}_{2}\cdots\bar{\mathbf{y}}_{N}]$, $\mathbf{X}=[\mathbf{x}_{1}\mathbf{x}_{2}\cdots\mathbf{x}_{N}]$, and $\bar{\mathbf{R}}$ is a rotation matrix of $d\times d$. Let $\bar{\mathbf{P}}$ be the projection matrix of $d\times d$, computed using PCA, $\bar{\mathbf{P}}=[\mathbf{P}\mathbf{P}_{\perp}]$, and $\mathbf{P}_{\perp}$ is a matrix of $d\times(d-M)$. It can be derived that, the solutions for $\mathbf{y}$ of the two problems in 37 and 36 are the same, and $\bar{\mathbf{R}}=\bar{\mathbf{P}}\operatorname{diag}(\mathbf{R},\mathbf{I}_{(d-M)\times(d-M)})$.

1.2 Extensions and Variants

Harmonious hashing modifies iterative quantization by adding an extra constraint: $\mathbf{Y}\mathbf{Y}^{\top}=\sigma\mathbf{I}$. The problem is solved by relaxing $\mathbf{Y}$ to continuous values: fixing $\mathbf{R}$, let $\mathbf{R}^{\top}\mathbf{V}=\mathbf{\mathbf{U}\boldsymbol{\Lambda}\mathbf{V}^{\top}}$, then $\mathbf{Y}=\sigma^{1/2}\mathbf{U}\mathbf{V}^{\top}$; fixing $\mathbf{\mathbf{Y}}$, $\mathbf{R}=\hat{\mathbf{S}}\mathbf{S}^{\top}$, where $\mathbf{S}$ and $\hat{\mathbf{S}}$ is obtained from the SVD of $\mathbf{Y}\mathbf{V}^{\top}$, $\mathbf{Y}\mathbf{V}^{\top}=\mathbf{S}\boldsymbol{\Lambda}\hat{\mathbf{S}}^{\top}$. The hash function is finally computed as $\mathbf{y}=\operatorname{sgn}(\mathbf{R}^{\top}\mathbf{v})$.

Isotropic hashing finds a rotation following PCA preprocessing such that $\mathbf{R}^{\top}\mathbf{V}\mathbf{V}^{\top}\mathbf{R}=\boldsymbol{\Sigma}$ becomes a matrix with equal diagonal values, i.e., $[\boldsymbol{\Sigma}]_{11}=[\boldsymbol{\Sigma}]_{22}=\cdots=[\boldsymbol{\Sigma}]_{MM}$. The objective function is written as $\|\mathbf{R}^{\top}\mathbf{V}\mathbf{V}^{\top}\mathbf{R}-\mathbf{Z}\|_{F}=0$, where $\mathbf{Z}$ is a matrix with all the diagonal entries equal to an unknown variable $\sigma$. The problem can be solved by two algorithms: lift and projection, and gradient flow.

Comments: The goal of making the variances along the $M$ directions being the same is to make the bits in the hash codes equally contributing to the distance evaluation. In the case that the data items satisfy the isotropic Gaussian distribution, the solution from isotropic hashing is equivalent to iterative quantization.

Similar to iterative quantization, the PCA preprocessing in isotropic hashing is also interpretable: finding a global rotation matrix $\bar{\mathbf{R}}$ such that the first $M$ diagonal entries of $\bar{\boldsymbol{\Sigma}}=\bar{\mathbf{R}}^{\top}\mathbf{X}\mathbf{X}^{\top}\bar{\mathbf{R}}$ are equal, and their sum is as large as possible, which is formally written as follows,

Other extensions include cosine similarity preserving quantization (Angular quantization ), nonlinear embedding replacing PCA embedding , matrix hashing , and so on. Quantization is also applied to supervised problems: Supervised discrete hashing , present an SVM-like formulation to minimize the quantization loss and the classification loss in the hash coding space, and jointly optimize the hash function parameters and the SVM weights. Intuitively, the goal of these methods is that the hash codes are semantically separable, which is guaranteed through maximizing the classification performance.

2 Cartesian Quantization

Cartesian quantization refers to a class of quantization algorithms in which the composed dictionary $\mathcal{C}$ is formed from a Cartesian product of a set of small source dictionaries $\{\mathcal{C}_{1},\mathcal{C}_{2},\cdots,\mathcal{C}_{P}\}$: $\mathcal{C}=\mathcal{C}_{1}\times\mathcal{C}_{2}\times\cdots\times\mathcal{C}_{P}=\{(\mathbf{c}_{1i_{1}},\mathbf{c}_{2i_{2}},\cdots,\mathbf{c}_{Pi_{P}})\}$, where $\mathcal{C}_{p}=\{\mathbf{c}_{p0},\mathbf{c}_{p2},\cdots,\mathbf{c}_{p(K_{p}-1)}\}$, $i_{p}\in\{0,1,\cdots,K_{p}-1\}$.

The benefits include that (1) $P$ small dictionaries, with totally $\sum_{p=1}^{P}K_{p}$ dictionary items, generate a larger dictionary with $\prod_{p=1}^{P}K_{p}$ dictionary items; (2) the (asymmetric) distance from a query $\mathbf{q}$ to the composed dictionary item $(\mathbf{c}_{1i_{1}},\mathbf{c}_{2i_{2}},\cdots,\mathbf{c}_{Pi_{P}})$ (an approximation of a data item) is computed from the distances $\{\operatorname{dist}(\mathbf{q},\mathbf{c}_{1i_{1}}),\cdots,\operatorname{dist}(\mathbf{q},\mathbf{c}_{Pi_{P}})\}$ through a sum operation, thus the cost of the distance computation between a query and a data item is $O(P)$, if the distances between the query and the source dictionary items are precomputed; and (3) the query cost with a set of $N$ database items is reduced from $Nd$ to $NP$ through looking up a distance table which is efficiently computed between the query and the $P$ source dictionaries.

Product quantization , which initiates the quantization-based compact coding solution to similarity search, forms the $P$ source dictionaries by dividing the feature space into $P$ disjoint subspaces, accordingly dividing the database into $P$ sets, each set consisting of $N$ subvectors $\{\mathbf{x}_{p1},\cdots,\mathbf{x}_{pN}\}$, and then quantizing each subspace separately into (usually $K_{1}=K_{2}=\cdots=K_{P}=K$) clusters. Let $\{\mathbf{c}_{p1},\mathbf{c}_{p2},\cdots,\mathbf{c}_{pK}\}$ be the cluster centers of the $p$th subspace. The operation forming an item in the dictionary from a P-tuple $(\mathbf{c}_{1i_{1}},\mathbf{c}_{2i_{2}},\cdots,\mathbf{c}_{Pi_{P}})$ is the concatenation $[\mathbf{c}_{1i_{1}}^{\top}\mathbf{c}_{2i_{2}}^{\top}\cdots\mathbf{c}_{Pi_{P}}^{\top}]^{\top}$. A data point assigned to the nearest dictionary item $(\mathbf{c}_{1i_{1}},\mathbf{c}_{2i_{2}},\cdots,\mathbf{c}_{Pi_{P}})$ is represented by a compact code $(i_{1},i_{2},\cdots,i_{P})$, whose length is $P\log_{2}K$. The distance $\operatorname{dist}(\mathbf{q},\mathbf{c}_{pi_{p}})$ between a query $\mathbf{q}$ and the dictionary element in the $p$th dictionary is computed as $\|\mathbf{q}_{p}-\mathbf{c}_{pi_{p}}\|_{2}^{2}$, where $\mathbf{q}_{p}$ is the subvector of $\mathbf{q}$ in the $p$th subspace.

Mathematically, product quantization can be viewed as minimizing the following objective function,

Here $\mathbf{C}$ is a matrix of $d\times PK$ in the form of

where $\mathbf{C}_{p}=[\mathbf{c}_{p1}\mathbf{c}_{p2}\cdots\mathbf{c}_{pK}]$. $\mathbf{b}_{n}=[\mathbf{b}_{n1}^{\top}\mathbf{b}_{n2}^{\top}\cdots\mathbf{b}_{nP}^{\top}]^{\top}$ is the composition vector, and its subvector $\mathbf{b}_{np}$ of length $K$ is an indicator vector with only one entry being $1$ and all others being , showing which element is selected from the $p$th source dictionary for quantization.

Extensions: Distance-encoded product quantization extends product quantization by encoding both the cluster index and the distance between the cluster center and the point. The cluster index is encoded in a way similar to that in product quantization. The way of encoding the distance between a point and its cluster center is as follows: the points belonging to one cluster are partitioned (quantized) according to the distances to the cluster center, the points in each partition are represented by the corresponding partition index, and accordingly the distance of each partition to the cluster center is also recorded with the partition index.

Cartesian $k$-means and optimized production quantization extend product quantization and introduce a rotation $\mathbf{R}$ into the objective function,

The introduced rotation does not affect the Euclidean distance as the Euclidean distance is invariant to the rotation, and helps to find an optimized subspace partition for quantization. Locally optimized product quantization applies optimized production quantization to the search algorithm with the inverted index, where there is a quantizer for each inverted list.

2.2 Composite Quantization

In composite quantization , the operation forming an item in the dictionary from a P-tuple $(\mathbf{c}_{1i_{1}},\mathbf{c}_{2i_{2}},\cdots,\mathbf{c}_{Pi_{P}})$ is the summation $\sum_{p=1}^{P}\mathbf{c}_{pi_{p}}$. In order to compute the distance from a query $\mathbf{q}$ to the composed dictionary item formed by $(\mathbf{c}_{1i_{1}},\mathbf{c}_{2i_{2}},\cdots,\mathbf{c}_{Pi_{P}})$ from the distances $\{\operatorname{dist}(\mathbf{q},\mathbf{c}_{1i_{1}}),\cdots,\operatorname{dist}(\mathbf{q},\mathbf{c}_{1i_{1}})\}$, a constraint is introduced: the summation of the inner products of all pairs of elements that are used to approximate the vector $\mathbf{x}_{n}$ but from different dictionaries, $\sum_{i=1}^{P}\sum_{j=1,\neq i}^{P}\mathbf{c}_{ik_{in}}\mathbf{c}_{jk_{jn}}$, is constant.

Here, ${\mathbf{C}_{p}}$ is a matrix of size $d\times K$, and each column corresponds to an element of the $p$th dictionary $\mathcal{C}_{p}$.

Sparse composite quantization improves composite quantization by constructing a sparse dictionary, $\sum_{p=1}^{P}\sum_{k=1}^{K}\|\mathbf{c}_{pk}\|_{0}\leqslant S$, with $S$ being a parameter controlling the sparsity degree, resulting in a great reduction of the distance table computation cost which takes almost the same as the most efficient approach: product quantization.

Connection with product quantization: It is shown in that both product quantization and Cartesian $k$-means can be regarded as constrained versions of composite quantization. Composite quantization attains smaller quantization errors, yielding better search accuracy with similar search efficiency. A $2$D illustration of the three algorithms is given in Figure 2, where $2$D points are grouped into $9$ groups. It is observed that composition quantization is more flexible in partitioning the space and thus the quantization error is possibly smaller.

Composite quantization, product quantization, and Cartesian $k$-means (optimized product quantization) can be explained from the view of sparse coding, as pointed in : the dictionary ($\{\mathbf{C}_{p}\}$) in composite quantization (product quantization and Cartesian $k$-means) satisfies the constant (orthogonality) constraint, and the sparse codes ($\{\mathbf{b}_{n}\}$) are and $1$ vectors where there is only one $1$ for each subvector corresponding to a source dictionary.

Comments: As discussed in product quantization , the idea of using the summation of several dictionary items as an approximation of a data item has already been studied in the signal processing research area, known as multi-stage vector quantization, residual quantization, or more generally structured vector quantization , and recently re-developed for similarity search under the Euclidean distance (additive quantization , , and tree quantization modifying additive quantization by introducing a tree-structure sparsity) and inner product .

2.3 Variants

The work in presents an approach to compute the source dictionaries given the $M$ hash functions $\{h_{m}(\mathbf{x})=b_{m}(g_{m}(\mathbf{x}))\}$, where $g_{m}()$ is a real-valued embedding function and $b_{m}()$ is a binarization function, for a better distance measure, quantization-like distance, instead of Hamming or weighted Hamming distance. It computes $M$ dictionaries, each corresponding to a hash bit and computed as

where $b=0$ and $b=1$. The distance computation cost is $O(M)$ through looking up a distance table, which can be accelerated by dividing the hash functions into groups (e.g., each group contains $8$ functions, and thus the cost is reduced to $O(\frac{M}{8})$), building a table (e.g., consisting of $256$ entries) per group instead of per hash function, and forming a larger distance lookup table. In contrast, optimized code ranking directly estimates the distance table rather than computing it from the estimated dictionary.

Composite quantization points to relation between Cartesian quantization and sparse coding. This indicates the application of sparse coding to similarity search. Compact sparse coding , the extension of robust sparse coding , adopts sparse codes to represent the database items: the atom indices corresponding to nonzero codes, which is equivalent to letting the hash bits associated with nonzero codes be $1$ and for zero codes, are used to build the inverted index, and the nonzero coefficients are used to reconstruct the database items and calculate the distances between the database items and the query. Anti-sparse coding aims to learn a hash code so that non-zero elements in the hash code are as many as possible.

3 Reconstruction

We review a few reconstruction-based hashing approaches. Essentially, quantization can be viewed as a reconstruction approach for a data item. Semantic hashing , generates the hash codes using the deep generative model, a restricted Boltzmann machine (RBM), for reconstructing the data item. As a result, the binary codes are used for finding similar data. A variant method proposed in reconstructs the input vector from the binary codes, which is effectively solved using the auxiliary coordinates algorithm. A simplified algorithm finds a binary hash code that can be used to effectively reconstruct the vector through a linear transformation.

Other Topics

Most hashing learning algorithms assume that the similarity information in the input space, especially the semantic similarity information, and the database items have already been given. There are some approaches to learn hash functions without such assumptions: active hashing that actively selects the labeled pairs which are most informative for hash function learning, online hashing , smart hashing , online sketching hashing , and online adaptive hashing , which learn the hash functions when the similar/dissimilar pairs come sequentially.

The manifold structure in the database is exploited for hashing, which is helpful for semantic similarity search, such as locally linear hashing , spline regression hashing , and inductive manifold hashing . Multi-table hashing, aimed at improving locality sensitive hashing, is also studied, such as complementary hashing and its multi-view extension , reciprocal hash tables and its query-adaptive extension , and so on.

There are some works extending the Hamming distance. In contrast to multi-dimensional spectral hashing in which the weights for the weighted Hamming distance are the same for arbitrary queries, the query-dependent distance approaches learn a distance measure whose weights or parameters depend on a specific query. Query adaptive hashing , a learning-to-hash version extended from query adaptive locality sensitive hashing , aims to select the hash bits (thus hash functions forming the hash bits) according to the query vector. Query-adaptive class-specific bit weighting , presents a weighted Hamming distance measure by learning the class-specific bit weights from the class information of the query. Bits reconfiguration is to learn a good distance measure over the hash codes precomputed from a pool of hash functions.

The following reviews three research topics: joint feature and hash learning with deep learning, fast search in the Hamming space replacing the exhaustive search, and the important application of the Cartesian quantization to inverted index.

The great success in deep neural network for representation learning has inspired a lot of deep compact coding algorithms . Typically, these approaches except simultaneously learn the representation using a deep neural network and the hashing function under some loss functions, rather than separately learn the features and then learn the hash functions.

The methodology is similar to other learning to hash algorithms that do not adopt deep learning, and the hash function is more general and could be a deep neural network. We provide here a separate discussion because this area is relatively new. However, we will not discuss semantic hashing which is usually not thought as a feature learning approach but just a hash function learning approach. In general, almost all non-deep-learning hashing algorithms if the similarity order (e.g., semantic similarity) is given, can be extended to deep learning based hashing algorithms. In the following, we discuss the deep learning based algorithms and also categorize them according to their similarity preserving manners.

Pairwise similarity preserving. The similarity-similarity difference minimization criterion is adopted in . It uses a two-step scheme: the hash codes are computed by minimizing the similarity-similarity difference without considering the visual information, and then the image representation and hash function are jointly learnt through deep learning.

Multiwise similarity preserving. The triplet loss is used in , which adopt the loss function defined in Equation (24) ($1$ is dropped in )

Quantization. Following the scalar quantization approach, deep hashing defines a loss to penalize the difference between the binary hash codes (see Equation (35)) and the real values from which a linear projection is used to generate the binary codes, and introduces the bit balance and bit uncorrelation conditions.

2 Fast Search in the Hamming Space

The computation of the Hamming distance is shown much faster than the computation of the distance in the input space. It is still expensive, however, to handle a large scale data set using linear scan. Thus, some indexing algorithms already shown effective and efficient for general vectors are borrowed for the search in the Hamming space. For example, min-hash, a kind of LSH, is exploited to search over high-dimensional binary data . In the following, we discuss other representative algorithms.

Multi-index hashing and its extension aim to partition the binary codes into $M$ disjoint substrings and build $M$ hash tables each corresponding to a substring, indexing all the binary codes $M$ times. Given a query, the method outputs the NN candidates which are near to the query at least in one hash table. FLANN extends the FLANN algorithm that was initially designed for ANN search over real-value vectors to search over binary vectors. The key idea is to build multiple hierarchical cluster trees to organize the binary vectors and to search for the nearest neighbors simultaneously over the multiple trees by traversing each tree in a best-first manner.

PQTable extends multi-index hashing from the Hamming space to the product-quantization coding space, for fast exact search. Unlike multi-index hashing flipping the bits in the binary codes to find candidate tables, PQTable adopts the multi-sequence algorithm for efficiently finding candidate tables. The neighborhood graph-based search algorithm for real-value vectors is extended to the Hamming space .

3 Inverted Multi-Index

Hash table lookup with binary hash codes is a form of inverted index. Retrieving multiple hash buckets for multiple hash tables is computationally cheaper compared with the subsequent reranking step using the true distance computed in the input space. It is also cheap to visit more buckets in a single table if the standard Hamming distance is used, as the nearby hash codes of the hash code of the query which can be obtained by flipping the bits of the hash code of the query. If there are a lot of empty buckets which increases the retrieval cost, the double-hash scheme or the fast search algorithm in the Hamming space, e.g., can be used to fast retrieve the hash buckets.

Thanks to the multi-sequence algorithm, the Cartesian quantization algorithms are also applied to the inverted index , , (called inverted multi-index), in which each composed quantization center corresponds to an inverted list. Instead of comparing the query with all the composed quantization centers, which is computationally expensive, the multi-sequence algorithm is able to efficiently produce a sequence of ($T$) inverted lists ordered by the increasing distances between the query and the composed quantization centers, whose cost is $O(T\log T)$. The study (Figure 5 in ) shows that the time cost of the multi-sequence algorithm when retrieving $10K$ candidates over the two datasets: SIFT$1M$ and GIST$1M$ is the smallest compared with other non-hashing inverted index algorithms.

Though the cost of the multi-sequence algorithm is greater than that with binary hash codes, both are relatively small and negligible compared with the subsequent reranking step that is often conducted in real applications. Thus the quantization-based inverted index (hash table) is more widely used compared with the conventional hash tables with binary hash codes.

Evaluation Protocols

There are three main concerns for an approximate nearest neighbor search algorithm: space cost, search efficiency, and search quality. The space cost for hashing algorithms depends on the code length for hash code ranking, and the code length and the table number for hash table lookup. The search performance is usually measured under the same space cost, i.e., the code length (and the table number) is chosen the same for different algorithms.

The search efficiency is measured as the time taken to return the search result for a query, which is usually computed as the average time over a number of queries. The time cost often does not include the cost of the reranking step (using the original feature representations) as it is assumed that such a cost given the same number of candidates does not depend on the hashing algorithms and can be viewed as a constant. When comparing the performance in the case the Hamming distance in hash code ranking is used in the coding space, it is not necessary to report the search time costs because they are the same. It is necessary to report the search time cost when a non-Hamming distance or the hash table lookup scheme is used.

The search quality is measured using recall@$R$ (i.e., a recall-$R$ curve). For each query, we retrieve its $R$ nearest items and compute the ratio of the true nearest items in the retrieved $R$ items to $T$ , i.e., the fraction of $T$ ground-truth nearest neighbors are found in the retrieved $R$ items. The average recall score over all the queries is used as the measure. The ground-truth nearest neighbors are computed over the original features using linear scan. Note that the recall@$R$ is equivalent to the accuracy computed after reordering the $R$ retrieved nearest items using the original features and returning the top $T$ items. In the case where the linear scan cost in the hash coding space is not the same (e.g., binary code hashing, and quantization-based hashing), the curve in terms of search recall and search time cost is usually reported.

The semantic similarity search, a variant of nearest neighbor search, sometimes uses the precision, the recall, the precision-recall curve, and mean average precision (mAP). The precision is computed at the retrieved position $R$, i.e., $R$ items are retrieved, as the ratio of the number of retrieved true positive items to $R$. The recall is computed, also at position $R$, as the ratio of the number of retrieved true positive items to the number of all true positive items in the database. The pairs of recall and precision in the precision-recall curve are computed by varying the retrieved position $R$. The mAP score is computed as follows: the average precision for a query, the area under the precision-recall curve is computed as $\sum_{t=1}^{N}P(t)\Delta(t)$, where $P(t)$ is the precision at cut-off $t$ in the ranked list and $\Delta(t)$ is the change in recall from items $t-1$ to $t$; the mean of average precisions over all the queries is computed as the final score.

2 Evaluation Datasets

The widely-used evaluation datasets have different scales from small, large, to very large. Various features have been used, such as SIFT features extracted from Photo-tourism and Caltech $101$ , GIST features from LabelMe and Peekaboom , as well as some features used in object retrieval: Fisher vectors and VLAD vectors . The following presents a brief introduction to several representative datasets, which is summarized in Table II.

MNIST includes $60K$ $784$-dimensional raw pixel features describing grayscale images of handwritten digits as a reference set, and $10K$ features as the queries.

SIFT$10K$ consists of $10K$ $128$-dimensional SIFT vectors as the reference set, $25K$ vectors as the learning set, and $100$ vectors as the query set. SIFT$1M$ is composed of $1M$ $128$-dimensional SIFT vectors as the reference set, $100K$ vectors as the learning set, and $10K$ as the query set. The learning sets in SIFT$10K$ and SIFT$1M$ are extracted from Flicker images and the reference sets and the query sets are from the INRIA holidays images .

GIST$1M$ consists of $1M$ $960$-dimensional GIST vectors as the reference set, $50K$ vectors as the learning set, $1K$ vectors as the query set. The learning set is extracted from the first $100K$ images from the tiny images . The reference set is from the Holiday images combined with Flickr$1M$ . The query set is from the Holiday image queries. Tiny$1M$ http://research.microsoft.com/~jingdw/SimilarImageSearch/NNData/NNdatasets.html consists of $1M$ $384$-dimensional GIST vectors as the reference set and $100K$ vectors as the query set. The two sets are extracted from the $1100K$ tiny images.

SIFT$1B$ includes $1B$ $128$-dimensional BYTE-valued SIFT vectors as the reference set, $100M$ vectors as the learning set and $10K$ vectors as the query set. The three sets are extracted from around $1M$ images. This dataset, and SIFT$10K$, SIFT$1M$ and GIST$1M$ are publicly availablehttp://corpus-texmex.irisa.fr/.

GloVe$1.2M$ http://nlp.stanford.edu/projects/glove/ contains $1,193,514$ $200$-dimensional word feature vectors extracted from Tweets. We randomly sample $10K$ vectors as the query set and use the remaining as the training set.

3 Training Sets and Hyper-Parameters Selection

There are three main choices of the training set over which the hash functions are learnt for learning-to-hash algorithms. The first choice is a separate set used for learning hash functions, which is not contained in the reference set. The second choice is to sample a small subset from the reference set. The third choice is to use all the reference set to train hash functions. The query set and the reference set are then used to evaluate the learnt hash functions.

In the case where the query is transformed to a hash code, e.g., when adopting the Hamming distance for most binary hash algorithms, learning over the whole reference set might lead to over-fitting and the performance might be worse than learning with a subset of the reference set or a separate set. In the case where the raw query is used without any processing, e.g., when adopting the asymmetric distance in Cartesian quantization, learning over the whole reference set is better as it results in better approximation of the reference set.

There are some hyper-parameters in the objective functions, e.g, the objective functions in minimal loss hashing and composite quantization . It is unfair and not suggested to select the hyper-parameters corresponding to the best performance over the query set. It is suggested instead to select the hyper-parameters by validation, e.g., sampling a subset from the reference set as the validation set which is reasonable because the validation criterion is not the objective function value but the search performance.

Performance Analysis

We summarize empirical observations and the analysis of the nearest neighbor search performance using the compact coding approach, most of which have already been mentioned or discussed in the existing works. We discuss about both hash table lookup and hash code ranking, with more focus on hash code ranking because the major usage of the learning to hash algorithms lies in hash code ranking for retrieving top candidates from a set of candidates obtained from the inverted index or other hash table lookup algorithms. The analysis is mainly focusing on the major application of hashing: nearest neighbor search with the Euclidean distance. The conclusion for semantic similarity search is similar in principle and the performance also depends on the ability of representing the semantic meaning of the input features. We also present empirical results of the quantization algorithms and the representative binary coding algorithms for hash code ranking.

We give a performance summary of the query scheme using hash table lookup for the two main hash algorithms: the binary hash codes and the quantization-based hash codes.

In terms of space cost, hash table lookup with binary hash codes has a little but negligible advantage over that with quantization-based hash codes because the main space cost comes from the indices of the reference items and the extra cost from the centers corresponding to the buckets using quantization is relatively small. Multi-assignment and multiple hash tables increase space cost as they require to store multiple copies of reference vector indices. As an alternative choice, single-assignment with a single table can be used but more buckets are retrieved for high recall.

When retrieving the same number of candidates, hash table lookup using binary hash codes is better in terms of the query time cost, but inferior to the quantization approach in terms of the recall, which has probably been firstly discussed in . In terms of recall vs. time cost the quantization approach is overall superior as the cost from the multi-sequence algorithm is relatively small and negligible compared with the subsequent reranking step, which is observed from our experience, and can be derived from and . In general, the performance for other algorithms based on the weighted Hamming distance and the learnt distance is in between. The observation holds for a single table with single assignment and multiple assignment, or multiple tables.

1.2 Query Performance with Hash Code Ranking

The following provides a short summary of the overall performance for three main categories: pairwise similarity preserving, multiwise similarity preserving, and quantization in terms of search cost and search accuracy under the same space cost, guaranteed by coding the items using the same number of bits, ignoring the small space cost of the dictionary in Cartesian quantization and the distance lookup tables.

Search accuracy: Multiwise similarity preserving is better than pairwise similarity preserving as it considers more information for hash function learning. There is no observation/conclusion on which algorithm, pairwise or multiwise similarity preserving algorithm, performs consistently the best. Nevertheless, there is a large amount of pairwise and multiwise similarity preserving algorithms because different algorithms may be suitable to different data distributions and optimization also affects the performance.

It has been shown in Section 7.1 that the cost function of hypercubic quantization is an approximation of the distance-distance difference. But it outperforms pairwise and multiwise similarity preserving algorithms. This is because it is infeasible to consider all pairs (triples) of items for the distance-distance difference in pairwise (multiwise) similarity preserving algorithms, and thus only a small subset of the pairs (triples), by sampling a subset of items or pairs (triples), is considered for almost all the pairwise (multiwise) similarity preserving hashing algorithms, while the cost function for quantization is an approximation for all pairs of items. This point is also discussed in .

Compared with binary code hashing including hypercubic quantization, another reason for the superiority of Cartesian quantization, as discussed in , is that there are only a small number ($L+1$) of distinct Hamming distances in the coding space for binary code hashing with the code length being $L$, while the number of distinct distances for Cartesian quantization is much larger. It is shown that the performance from learning a distance measure using a way like the quantization approach or directly learning a distance lookup table A similar idea is concurrently proposed in to learn a better similarity for a bag-of-words representation and quantized kernels. from precomputed hash codes is comparable to the performance of the Cartesian quantization approach if the codes from the quantization approach are given as the input.

Search cost: The evaluation of the Hamming distance using the CPU instruction $\operatorname{\_\_popcnt}$ is faster than the distance-table lookup. For example, it is around twice faster for the same code length $L$ than distance table lookup if a sub-table corresponds to a byte and there are totally $\frac{L}{8}$ sub-tables. It is worth pointing (also observed in ) that the Cartesian quantization approaches relying on the distance table lookup still achieve better search accuracy even with a code of the half length, which indicates that the overall performance of the quantization approaches in terms of space cost, query time cost, and search accuracy is superior.

In summary, if the online performance in terms of space cost, query time cost, and search accuracy is cared about, the quantization algorithms are suggested for hash code ranking, hash table lookup, as well as the scheme of combining inverted index (hash table lookup) and hash code ranking. The comparison of the query performances of pairwise and multiwise similarity preserving algorithms, as well as quantization is summarized in Table III.

Figure 3 presents $2$D toy examples. Figure 3 (a) shows that the quantization algorithm is able to discriminate the non-uniformly distributed clusters with different between-cluster distances while the binary code hashing algorithm is lacking such a capability due to the Hamming distance. Figure 3 (b) shows that the binary hash coding algorithms require more ($6$) hash bits to differentiate the $16$ uniformly-distributed clusters while the quantization algorithms only require $4$ ($=\log 16$) bits.

1.3 Empirical Results

We present the empirical results of the several representative hashing and quantization algorithms over SIFT$1M$ . We show the results for searching the nearest neighbor ($T=1$) with $128$ bits and the conclusion holds for searching more nearest neighbors ($T>1$) and with other numbers of bits. More results, such as the search time cost, and results using inverted multi-index with different quantization algorithms can be found in . We also conduct experiments over word feature vectors GloVe$1.2M$. We present the results using recall$@R$ for searching the nearest neighbor ($T=1$) with $128$ bits.

We also report the results over deep learning features extracted from the ILSVRC $2012$ dataset. The ILSVRC $2012$ dataset is a subset of ImageNet and contains over $1.2$ million images. We use the provided training set, $1,281,167$ images, as the retrieval database and use the provided validation set, $50,000$ images, as the test set. Similar to , the $4096$-dimensional feature extracted from the convolution neural networks (CNN) in is used to represent each image. We evaluate the search performance under the Euclidean distance in terms of recall@$R$, where $R$ is the number of the returned top candidates, and under the semantic similarity in terms of MAP vs. $\#$bits.

Figure 4 shows the recall@$R$ curves and the MAP results. We have several observations. (1) The performance of the quantization method is better than the hashing method in most cases for both Euclidean distance-based and semantic search. (2) LSH, a data-independent algorithm is generally worse than other learning to hash approaches. (3) For Euclidean distance-based search the performance of CQ is the best among quantization methods, which is consistent with the analysis and the $2D$ illustration shown in Figure 2.

2 Training Time Cost

We present the analysis of the training time cost for the case of using the linear hash function. The pairwise similarity preserving category considers the similarities of all pairs of items, and thus in general the training process takes quadratic time with respect to the number $N$ of the training samples ($O(N^{2}M+N^{2}d)$). To reduce the computational cost, sampling schemes are adopted: sample a small number (e.g., $O(N)$) of pairs, whose time complexity becomes linear with respect to $N$, resulting in ($O(NM+Nd)$), or sample a subset of the training items (e.g., containing $\bar{N}$ items), whose time complexity becomes smaller ($O(\bar{N}^{2}M+\bar{N}^{2}d)$). The multiwise similarity preserving category considers the similarities of all triples of items, and in general the training cost is greater and the sampling scheme is also used for acceleration. The analysis for kernel hash functions and other complex functions is similar, and the time complexity for both training hash functions and encoding database items is higher.

Iterative quantization consists of a PCA preprocessing step whose time complexity is $O(Nd^{2})$, and the hash code and hash function optimization step, whose time complexity is $O(NM^{2}+M^{3})$ ($M$ is the number of hash bits). The whole complexity is $O(Nd^{2}+NM^{2}+M^{3})$. Product quantization includes the $k$-means process for each partition, and the complexity is $TNKP$, where $K$ is usually $256$, $P=\frac{M}{8}$, and $T$ is the number of iterations for the $k$-means algorithm. The complexity of Cartesian $k$-means is $O(Nd^{2}+d^{3})$. The time complexity of composite quantization is $O(NKPd+NP^{2}+P^{2}K^{2}d)$. In summary, the time complexity of iterative quantization is the lowest and that of composite quantization is the highest. This indicates that it takes larger offline computation cost to get a higher (online) search performance.

Emerging Topics

The main goal of the hashing algorithm is to accelerate the online search as the distance can be efficiently computed through fast Hamming distance computation or fast distance table lookup. The offline hash function learning and hash code computation are shown to be still expensive, and have become attractive in research. The computation cost of the distance table used for looking up is thought ignorable and in reality could be higher when handling high-dimensional databases. There is also increasing interest in topics such as multi-modality and cross-modality hashing and semantic quantization.

Scalable Hash Function Learning. The algorithms depending on the pairwise similarity, such as binary reconstructive embedding, usually sample a small subset of pairs to reduce the cost of learning hash functions. It has been shown that the search accuracy is increased with a high sampling rate, but the training cost is greatly increased. The algorithms even without relying on the pairwise similarity, e.g., quantization, were also shown to be slow and even infeasible when handling very large data, e.g., $1B$ data items, and usually have to learn hash functions over a small subset, e.g., $1M$ data items. This poses a challenging request to learn the hash function over larger datasets.

Hash Code Computation Speedup. Existing hashing algorithms rarely take into consideration the cost of encoding a data item. Such a cost during the query stage becomes significant in the case that only a small number of database items or a small database are compared to the query. The search combined with the inverted index and compact codes is such a case. When kernel hash functions are used, encoding the database items to binary codes is also much more expensive than that with linear hash functions. The composite quantization-like approach also takes much time to compute the hash codes.

A recent work, circulant binary embedding , accelerates the encoding process for the linear hash functions, and tree-quantization sparsifies the dictionary items into a tree structure, to speeding up the assignment process. However, more research is needed to speed up the hash code computation for other hashing algorithms, such as composite quantization.

Distance Table Computation Speedup. Product quantization and its variants need to precompute the distance table between the query and the elements of the dictionaries. Most existing algorithms claim that the cost of distance table computation is negligible. However in practice, the cost becomes bigger when using the codes computed from quantization to rank the candidates retrieved from the inverted index. This is a research direction that will attract research interest in the near future, such as a recent study, sparse composite quantization .

2 Promising Extensions

Semantic Quantization. Existing quantization algorithms focus on the search under the Euclidean distances. Like binary code hashing algorithms where many studies on semantic similarity have been conducted, learning quantization-based hash codes with semantic similarity is attracting interest. There are already a few studies. For example, we have proposed an supervised quantization approach and some comparisons are provided in Figure 4.

Multiple and Cross Modality Hashing. One important characteristic of big data is the variety of data types and data sources. This is particularly true for multimedia data, where various media types (e.g., video, image, audio and hypertext) can be described by many different low- and high-level features, and relevant multimedia objects may come from different data sources contributed by different users and organizations. This raises a research direction, performing joint-modality hashing learning by exploiting the relation among multiple modalities, for supporting some special applications, such as cross-modal search. This topic is attracting a lot of research efforts nowadays, such as collaborative hashing , collaborative quantization , and cross-media hashing , , , , .

Conclusion

In this paper, we categorize the learning-to-hash algorithms into four main groups: pairwise similarity preserving, multiwise similarity preserving, implicit similarity preserving, and quantization, present a comprehensive survey with a discussion about their relations. We point out the empirical observation that quantization is superior in terms of search accuracy, search efficiency and space cost. In addition, we introduce a few emerging topics and the promising extensions.

Acknowledgements

This work was partially supported by the National Nature Science Foundation of China No. 61632007.

References