PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Learning to Hash

Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, Heng Tao Shen

arXiv:1606.00185v2cs.CV

TL;DR

Nearest neighbor search requires efficient retrieval of close database items, but exact search is costly at scale. The paper surveys learning-to-hash methods by their similarity-preservation strategy, relates the categories, and reviews evaluation and emerging topics. It reports that quantization is superior in search accuracy, efficiency, and space cost.

  • Problem

    Nearest neighbor search becomes prohibitively costly when databases are very large or distance computations are expensive, creating a need for efficient approximate search.

  • Method

    The paper presents a comprehensive survey that categorizes learning-to-hash algorithms by pairwise, multiwise, implicit similarity preservation, quantization, and end-to-end hash learning.

  • Results

    Quantization is empirically superior to other approaches in search accuracy, search efficiency, and space cost.

  • Takeaways & Limitations

    The categorization clarifies connections and differences among existing algorithms, while quantization emerges as the strongest overall approach across the reported search criteria.

  • Takeaways & Limitations

    Similarity-preserving objectives alone may lead to trivial solutions, so additional constraints are necessary.

Abstract

from arXiv · show

Nearest neighbor search is a problem of finding the data points from the database such that the distances from them to the query point are the smallest. Learning to hash is one of the major solutions to this problem and has been widely studied recently. In this paper, we present a comprehensive survey of the learning to hash algorithms, categorize them according to the manners of preserving the similarities into: pairwise similarity preserving, multiwise similarity preserving, implicit similarity preserving, as well as quantization, and discuss their relations. We separate quantization from pairwise similarity preserving as the objective function is very different though quantization, as we show, can be derived from preserving the pairwise similarities. In addition, we present the evaluation protocols, and the general performance analysis, and point out that the quantization algorithms perform superiorly in terms of search accuracy, search time cost, and space cost. Finally, we introduce a few emerging topics.

1 INTRODUCTION

Nearest neighbor search becomes costly for large databases or expensive distance computations, motivating approximate methods such as learning to hash. This survey organizes learning-to-hash algorithms by how they preserve similarity and reports strong empirical performance for quantization.

  • Motivation: Exact nearest neighbor search is prohibitively costly for very large databases or expensive distance computations, motivating approximate nearest neighbor search.Approximate search is described as more efficient and useful for many practical problems.
  • Learning to Hash: Learning to hash learns dataset-dependent hash functions that approximate nearest-neighbor results in a compact coding space while reducing search and storage costs.The approach maps data to short codes and seeks similarity between coding-space and original-space search results.
  • Learning to Hash: Similarity preservation is the main methodology, using semantic or original-space distance similarities to guide the coding-space representation.The survey focuses primarily on similarities derived from distances such as Euclidean distance.
  • Survey Scope: The survey categorizes methods into pairwise, multiwise, implicit similarity preserving, quantization, and end-to-end hash learning strategies.It also discusses relations among these categories and evaluation datasets and schemes.
  • Main Observation: Quantization empirically outperforms other approaches in search accuracy, search efficiency, and space cost.The survey emphasizes quantization-based solutions and analyzes this performance observation.

2 BACKGROUND

Nearest neighbor search seeks the closest database items under a distance measure, but exact search becomes difficult in large, high-dimensional databases. Hashing accelerates approximate search by mapping items to compact codes, using lookup, ranking, or a combination of both.

  • 2.1 Nearest Neighbor Search: Exact nearest neighbor search returns the database item minimizing distance to a query, while K-nearest neighbor search returns the K closest items.The database is represented as X = {x1, x2, · · ·, xN}, with NN(q) = arg minx∈X dist(q, x).
  • 2.1 Nearest Neighbor Search: Distances depend on the search problem and may include ℓs norms, Euclidean distance, ℓ1 distance, or cosine similarity.Euclidean distance is identified as a widely studied case.
  • 2.1 Nearest Neighbor Search: In large-scale high-dimensional settings, exact methods can cost more than linear scan, motivating error-constrained and time-constrained approximate search.Time-constrained search limits query time while seeking high accuracy and low query cost.
  • 2.2 Search with Hashing: Hashing maps reference and query items to compact codes so approximate search can use code distances and possibly a small subset of raw items.Hash-code distances are cheaper to compute than distances in the original input space.
  • 2.2 Search with Hashing: A hash function maps an input x to a code y, which may be integer or binary, and multiple hash functions can form a compound vector code.The compound code is represented as y = [y1 y2 · · · yM]⊤.
  • 2.2 Search with Hashing: Hash table lookup retrieves items from buckets indexed by codes, while hash code ranking compares the query with reference items using fast code-distance evaluation.Lookup can visit nearby buckets or use multiple tables; ranking may be exhaustive over the reference set or applied after candidate retrieval.
  • 2.2 Search with Hashing: Non-exhaustive search first retrieves candidates with a hash table or inverted index, then ranks them by hash-code distance and may rerank them using original features.The combined strategy reduces the search scope while retaining a subsequent ranking stage.

3 LEARNING TO HASH

Learning to hash learns compact codes so approximate nearest-neighbor results remain close to those in the original space while searches remain efficient. Its design spans hash functions, similarity measures, similarity-preserving objectives, and optimization strategies, with quantization treated separately despite its pairwise interpretation.

  • 3 LEARNING TO HASH: Learning to hash maps inputs to compact codes while aiming to preserve nearest-neighbor results and efficient coding-space search.The approach must jointly consider the hash function, coding-space similarity, input-space similarity, loss function, and optimization technique.
  • 3.1 Hash Function: Hash functions may use linear projections, kernels, spherical functions, neural networks, or nonparametric mappings.Linear functions are efficient to evaluate, whereas more flexible kernel and nearest-vector-assignment functions can improve search accuracy.
  • 3.1 Hash Function: Nearest-vector assignment maps an item to the index of its closest center, with distances computed using the corresponding centers rather than directly from the codes.The centers may be computed by methods such as K-means.
  • 3.2 Similarity: Input-space similarities can derive from pairwise distances, such as Euclidean distance, or from semantic class membership.A typical distance-based similarity is Gaussian, while semantic similarity is often binary for same-class pairs.
  • 3.2 Similarity: Coding-space similarity commonly uses Hamming distance or related measures, while quantization commonly evaluates Euclidean distances between query or data vectors and centers.Asymmetric quantization distance is preferred because accuracy is higher with nearly the same time cost, using a distance lookup table for efficiency.
  • 3.3 Similarity Preserving: Learning objectives preserve similarity order through pairwise, multiwise, implicit, or quantization-based strategies.Quantization is separated because its formulation differs substantially, although it can be explained as pairwise similarity preservation.
  • 3.4 Optimization: Optimization is difficult because sign functions create mixed-binary-integer problems and large datasets make computation expensive.Common responses include continuous relaxation, two-step optimization, discretization, and sampling data points or constraints.
  • 3.5 Categorization: Similarity preservation is used for categorization because it is the essential hashing goal, although hash functions and optimization also affect search performance.The survey’s categorization organizes methods by the similarity-preserving manner used in their objective functions.

4 PAIRWISE SIMILARITY PRESERVING

Pairwise similarity-preserving hashing aligns pairwise distances or similarities between the input and Hamming spaces through several objective-function families. The section also covers spectral hashing, its assumptions and limitations, and constraints or relaxations used to obtain useful binary codes.

  • Objective functions: Pairwise methods align distances or similarities for item pairs between the input and Hamming coding spaces.The reviewed families include similarity-similarity, distance-distance, normalized similarity, and product-based objectives.
  • Objective functions: Product-based objectives encode monotonic relationships, requiring coding-space distance or similarity to change consistently with input-space similarity or distance.SDPM, SSPM, DDPM, and DSPM respectively minimize or maximize products to preserve these pairwise relations.
  • Constraints and optimization: Similarity-preserving objectives alone can yield trivial solutions, so code-balance, bit-balance, or bit-uncorrelation constraints are introduced.For example, assigning every item the same code is prevented by balancing bits and decorrelating different bits.
  • Spectral hashing: Spectral hashing uses PCA directions and low-eigenvalue Laplacian eigenfunctions to construct hash bits under a separate multidimensional uniform-distribution assumption.Its hash function thresholds sinusoidal eigenfunctions with a sign operator.
  • Spectral hashing: Spectral hashing performs well for short codes but poorly for long codes because uniformity assumptions may fail and multiple eigenfunctions can be selected along one PCA direction.The latter can violate the uncorrelation requirement.
  • Constraints and optimization: Pairwise methods use continuous relaxation, two-step optimization, discretization, or direct binary optimization to handle the sign function.Representative methods also use linear or kernel hash functions and alternative constraints during optimization.

4.2 Similarity-Similarity Product Maximization

Similarity-similarity product maximization learns codes whose pairwise coding similarities agree with input-space similarities, while balancing code variance and imposing orthogonality constraints. Its unsupervised extension updates projection vectors sequentially using previously assigned codes.

  • Objective: Similarity-similarity product maximization rewards larger coding-space similarity when input-space similarity is larger.The input similarity can encode same-class or nearby pairs, with dissimilar pairs assigned negative similarity.
  • Optimization: A linear sign hash function is optimized with variance maximization for bit balance and W^⊤W = I as a relaxation of bit uncorrelation.The sign operator is dropped when estimating the projection matrix.
  • Unsupervised extension: The unsupervised extension computes projection vectors sequentially, using PCA for the first vector and revising similarities according to errors from earlier iterations.Nearby points separated previously receive positive revised similarity, while far points colliding previously receive negative revised similarity.
  • Optimization: The objective has a trivial all-identical-code solution unless additional constraints or regularization are imposed.Under binary codes, similarity-product maximization can be related to similarity-distance product minimization.
  • Related formulations: Distance-distance product maximization and similarity-distance product minimization are also formulated with variance regularization and linear projections.Optimization drops the sign operator and constrains the projected data covariance through W^⊤XLX^⊤W.

4.4 Distance-Distance Difference Minimization

Distance-distance difference minimization minimizes discrepancies between input-space and coding-space Euclidean distances, with kernel and graph-based variants. Related formulations reveal a trade-off between matching distances and preventing collapsed or overly similar codes.

  • Objective: Distance-distance difference minimization uses Euclidean distance in both input and coding spaces and minimizes their squared differences.Binary reconstructive embedding is identified as belonging to this group.
  • Kernel methods: Kernel hash functions represent the coding map through sampled data, a kernel function, and learnable weights.A coordinate-descent method can update one weight exactly while fixing the others, with time complexity O(N log N + |E|).
  • Related formulations: Distance-distance difference minimization differs from distance-distance product maximization by an additional term that minimizes coding-space distances.This term acts as a regularizer complementary to maximizing coding-space distances.
  • Related formulations: Similarity-similarity difference minimization aligns input and coding similarities, including through kernel, normalized Gaussian-kernel, graph, and discrete optimization variants.Representative approaches include supervised hashing with kernels, kernel reconstructive hashing, scalable graph hashing, and binary hashing.
  • Degenerate solutions: Similarity-similarity product maximization has a trivial solution in which all data points receive identical hash codes, motivating complementary regularization terms.The regularizer minimizes coding-space similarities so codes become more different.

5 MULTIWISE SIMILARITY PRESERVING

Multiwise similarity-preserving hashing matches ordering relationships among more than two items rather than only pairwise similarities. The surveyed methods use neighborhoods, triplets, lists, or search-list partitions to preserve ranking behavior in the coding space.

  • Overview: Multiwise methods formulate losses by maximizing agreement of similarity orders among more than two items in the input and coding spaces.They target ordering relationships rather than only pairwise similarity values.
  • Neighborhood methods: KNN hashing directly maximizes kNN search accuracy using a factorized neighborhood representation of training-data relationships.This approach optimizes the search result rather than preserving an order indirectly.
  • Triplet methods: Triplet loss hashing compares an anchor with a more-similar positive and a less-similar negative item using a hinge-like triplet loss.The loss is max(1 −∥y −y−∥1 + ∥y −y+∥1, 0).
  • Ranking methods: Top-rank supervised binary coding penalizes incorrectly ranked samples at the top of a Hamming-distance list more than samples near the bottom.This weighting focuses supervision on the most prominent ranking errors.
  • Listwise and order-preserving methods: Listwise supervision hashing uses triplets and a triplet tensor to maximize agreement among triplewise similarities.Order-preserving hashing instead aligns complete search-list orders through categories defined by input- and coding-space distances.
  • Method distinctions: Triplet loss hashing and listwise supervision hashing share central ideas but differ in loss formulation and optimization techniques, whereas order-preserving hashing compares search-list relations.These distinctions determine whether supervision targets triplewise or listwise structure.

6 IMPLICIT SIMILARITY PRESERVING

Implicit similarity-preserving methods learn hash functions by partitioning the input space without explicitly penalizing disagreement between input-space and coding-space similarities. Representative approaches use maximum-margin, bit-balance, or hyperspherical partitioning criteria.

  • These methods pursue effective space partitioning without explicitly evaluating input-space and coding-space distance or similarity relations.
  • Random maximum margin hashing randomly assigns positive and negative labels, then learns hash-function hyperplanes using a standard SVM formulation.
  • Complementary projection hashing maximizes items’ distances from the partition plane while imposing bit balance and bit uncorrelation conditions.
  • Spherical hashing partitions space with hyperspheres and learns pivots and thresholds to satisfy pairwise bit-balance constraints.

7 QUANTIZATION

Quantization approximates data with compact codes or composed dictionary vectors, and its distortion provides an upper bound on pairwise distance differences. Cartesian constructions reduce query computation, while composite quantization offers more flexible partitions and potentially smaller errors.

  • The quantization distortion error is an upper bound, with scale, on differences between input-feature and approximate-representation pairwise distances.
  • Hypercubic quantization maps data to binary or rotated hypercube vertices, whereas Cartesian quantization represents data using vectors selected from composed dictionaries.
  • Iterative quantization applies PCA dimension reduction, learns an optimal rotation, and then performs scalar quantization through alternative optimization.
  • Isotropic hashing rotates PCA-preprocessed data so the variances along the selected directions are equal, making hash bits contribute equally to distance evaluation.
  • Cartesian quantization combines P small source dictionaries into a larger dictionary, computes query-to-item distances in O(P), and reduces query cost from Nd to NP after precomputation.
  • Product quantization partitions the feature space into P disjoint subspaces and encodes each item using a P-tuple of independently selected cluster centers.
  • Composite quantization generalizes product quantization and Cartesian k-means, with more flexible partitions and smaller quantization errors that can improve search accuracy at similar efficiency.

8 OTHER TOPICS

The survey discusses online, manifold, query-adaptive, deep, and indexing extensions of learning to hash. It emphasizes replacing exhaustive Hamming-space scans with indexing and applying Cartesian quantization to inverted indexes.

  • Online hashing methods learn hash functions as similar and dissimilar pairs arrive sequentially, while active hashing selects informative labeled pairs.
  • Manifold-based methods exploit database structure for semantic similarity search, and multi-table hashing extends locality-sensitive hashing with multiple or adaptive tables.
  • Deep compact-coding methods jointly learn representations and hashing functions under loss functions rather than learning features and hashes separately.
  • Deep hashing variants preserve pairwise or multiwise similarities, or impose quantization, bit-balance, and bit-uncorrelation losses.
  • Indexing methods reduce the cost of searching large binary datasets, including multi-index hashing, FLANN extensions, and PQTable for product-quantization codes.
  • Cartesian quantization supports inverted indexes whose multi-sequence algorithm orders candidate lists efficiently, and the resulting overhead is often negligible relative to reranking.

9 EVALUATION PROTOCOLS

Evaluation compares approximate nearest-neighbor methods by space cost, query efficiency, and search quality using recall, precision, and mAP across datasets and training protocols. The survey also notes that training-set choice and validation affect measured performance.

  • Approximate nearest-neighbor evaluation focuses on space cost, search efficiency, and search quality, with comparisons usually controlled by equal code length and table number.
  • Search efficiency is average query time, often excluding reranking because equal candidate counts make its cost a constant across algorithms.
  • Search quality uses recall@R against ground-truth neighbors computed by linear scan over original features.
  • Semantic search additionally uses precision, recall, precision-recall curves, and mean average precision computed over ranked retrieval results.
  • The survey covers datasets ranging from MNIST and SIFT10K to billion-scale SIFT1B, using feature types including pixels, SIFT, GIST, Fisher vectors, VLAD, and word vectors.
  • Hash functions may be trained on separate data, a reference-set subset, or the full reference set, with full-set training potentially overfitting Hamming-code queries.
  • Hyperparameters should be selected by validation rather than choosing the best performance on the query set.

10 PERFORMANCE ANALYSIS

The survey compares query performance across binary hashing, similarity-preserving methods, and quantization, finding quantization generally superior in accuracy and overall online performance despite some lookup-time advantages for binary codes.

  • Query Performance with Hash Table Lookup: Binary-code hash-table lookup has only a negligible space advantage over quantization because reference-item indices dominate storage.Multiple tables and multi-assignment increase space cost by storing multiple copies of reference indices.
  • Query Performance with Hash Table Lookup: When retrieving the same number of candidates, binary hash lookup is faster but has lower recall than quantization.The quantization approach is overall superior in recall versus query-time cost.
  • Query Performance with Hash Code Ranking: Multiwise similarity preserving is more accurate than pairwise similarity preserving, but neither category consistently dominates across algorithms and data distributions.Performance also depends on optimization and suitability to the data distribution.
  • Query Performance with Hash Code Ranking: Quantization’s cost function approximates distance differences over all item pairs, whereas pairwise and multiwise methods typically sample only subsets.This analysis is presented as one explanation for quantization’s superior performance.
  • Query Performance with Hash Code Ranking: Quantization achieves better search accuracy even with half-length codes, yielding superior overall space, query-time, and accuracy performance.Cartesian quantization relies on distance-table lookup, while binary codes use faster Hamming-distance computation.
  • Query Performance: 6 hash bits distinguish 16 uniformly distributed clusters for binary hashing, whereas quantization requires only 4 (= log 16) bits.The toy example illustrates quantization’s more efficient representation of cluster structure.
  • Empirical Results: Quantization methods outperform hashing methods in most cases for both Euclidean-distance and semantic search.On ImageNet, the comparison uses recall@R for Euclidean search and mAP for semantic search.
  • Training Time Cost: Composite quantization has the highest training complexity among the listed quantization methods, while iterative quantization has the lowest.The analysis links higher offline computation cost with higher online search performance.

11 EMERGING TOPICS

The survey identifies scalability and computation speed as emerging challenges for learning to hash, alongside extensions to semantic, multiple, and cross-modality settings.

  • Scalable Hash Function Learning: Learning hash functions over very large datasets remains challenging because pairwise and quantization methods often sample only small subsets.The cited examples include datasets with up to 1B items but training subsets around 1M items.
  • Hash Code Computation Speedup: Hash-code encoding can become significant during query processing, especially when few database items are compared or complex kernel functions are used.Existing algorithms often underconsider this encoding cost.
  • Distance Table Computation Speedup: Distance-table computation in product quantization can be non-negligible when quantized codes rank candidates retrieved from an inverted index.This motivates speeding up distance-table computation.
  • Semantic Quantization: Semantic quantization extends quantization-based hashing beyond Euclidean search toward semantic similarity.The survey notes supervised quantization and comparisons in Figure 4.
  • Multiple and Cross Modality Hashing: Joint-modality hashing exploits relations among multiple data modalities to support cross-modal applications.Relevant modalities include video, image, audio, and hypertext.

12 CONCLUSION

The survey organizes learning-to-hash algorithms into four main groups and concludes that quantization is empirically superior across key online-search costs.

  • Conclusion: The survey categorizes algorithms as pairwise similarity preserving, multiwise similarity preserving, implicit similarity preserving, and quantization.It also discusses the relations among these categories and introduces emerging topics and extensions.
  • Conclusion: Quantization is empirically superior in search accuracy, search efficiency, and space cost.This is the paper’s principal performance observation.
Loading 1606.00185v2…