PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Hash for Indexing Big Data - A Survey

Jun Wang, Wei Liu, Sanjiv Kumar, Shih-Fu Chang

arXiv:1509.05472v1cs.LG

TL;DR

Large-scale nearest-neighbor search needs alternatives to exhaustive comparison because of prohibitive computational costs. This survey organizes learning-to-hash methods that use data and supervision to produce compact codes, reviews representative and deep-learning approaches, and discusses their benefits, limitations, and open directions.

  • Problem

    Exhaustive nearest-neighbor comparison is infeasible for massive datasets, while randomized hashing can be insufficient for real-world semantic similarity despite guarantees in certain metric spaces.

  • Method

    The paper surveys unsupervised, semi-supervised, supervised, and deep-learning hashing methods that learn compact binary codes from data distributions and supervision.

  • Results

    The survey reports that nonlinear and supervised techniques generally achieve better performance than linear and unsupervised methods, but at higher computational cost.

  • Takeaways & Limitations

    Learning-based hashing provides a framework for preserving semantic or neighborhood relationships in compact code spaces while supporting efficient retrieval.

  • Takeaways & Limitations

    Most learning-based hashing techniques lack theoretical guarantees on the quality of returned neighbors.

Abstract

from arXiv · show

The explosive growth in big data has attracted much attention in designing efficient indexing and search methods recently. In many critical applications such as large-scale search and pattern matching, finding the nearest neighbors to a query is a fundamental research problem. However, the straightforward solution using exhaustive comparison is infeasible due to the prohibitive computational complexity and memory requirement. In response, Approximate Nearest Neighbor (ANN) search based on hashing techniques has become popular due to its promising performance in both efficiency and accuracy. Prior randomized hashing methods, e.g., Locality-Sensitive Hashing (LSH), explore data-independent hash functions with random projections or permutations. Although having elegant theoretic guarantees on the search quality in certain metric spaces, performance of randomized hashing has been shown insufficient in many real-world applications. As a remedy, new approaches incorporating data-driven learning methods in development of advanced hash functions have emerged. Such learning to hash methods exploit information such as data distributions or class labels when optimizing the hash codes or functions. Importantly, the learned hash codes are able to preserve the proximity of neighboring data in the original feature spaces in the hash code spaces. The goal of this paper is to provide readers with systematic understanding of insights, pros and cons of the emerging techniques. We provide a comprehensive survey of the learning to hash framework and representative techniques of various types, including unsupervised, semi-supervised, and supervised. In addition, we also summarize recent hashing approaches utilizing the deep learning models. Finally, we discuss the future direction and trends of research in this area.

I. Introduction

Large-scale nearest-neighbor search is difficult because exhaustive comparison is costly in time and memory, especially for high-dimensional data. Hashing addresses this challenge by mapping data to compact binary codes, while learning-based methods adapt hash functions to data distributions or supervision.

  • Motivation: Exhaustive comparison is infeasible for large databases because it has linear time complexity and high-dimensional data worsens scalability.Documents and images may contain thousands or tens of thousands of dimensions.
  • Hashing framework: Hashing repeatedly partitions data and maps each item into a binary code in Hamming space.The survey describes K binary hash functions mapping N D-dimensional vectors to K-bit codes.
  • Hashing framework: Binary codes reduce storage and support efficient nearest-neighbor search through Hamming-distance computation and indexing structures.The survey gives an example compressing 80 million tiny images from around 600G bytes to 600M bytes using 64-bit codes.
  • Prior methods: Randomized LSH offers theoretical guarantees in certain metrics but may require long codes and multiple hash tables, increasing storage and query costs.Its guarantees apply to metrics such as ℓp for p∈[0,2] and Jaccard, which may not capture complex semantic similarity.
  • Learning to hash: Learning to hash develops data-dependent, task-specific hash functions using data distributions and information such as labels or pairwise relationships.The survey covers unsupervised, semi-supervised, and supervised approaches, along with deep-learning-based hashing.

B. Pipeline of Hashing-based ANN Search

Hashing-based ANN search comprises hash-function design, database encoding and indexing, and online querying. Hash tables enable inverse lookup by retrieving items whose codes lie within a chosen Hamming radius.

  • Pipeline overview: The ANN hashing pipeline has three steps: designing hash functions, generating and indexing hash codes, and querying with hash codes.These stages separate learned code construction from database organization and online retrieval.
  • Designing Hash Functions: Hash functions may be randomized or learned from data and supervision, with common forms parameterized by projection vectors and intercepts.The prespecified function can be nonlinear, and training estimates the parameters using data and sometimes supervised information.
  • Indexing Using Hash Tables: A database is indexed by storing only occupied buckets in an inverse-lookup hash table keyed by K-bit codes.With K binary functions, the table has at most 2^K possible entries, while the codes require only NK/8 bytes.
  • Online Querying with Hashing: During querying, the query is encoded with the same hash functions as the database items before neighbors are sought in Hamming space.Hamming distance can be computed efficiently with XOR and popcount operations.
  • Online Querying with Hashing: Inverse lookup returns items from buckets within Hamming radius r, requiring O(K^r) bucket searches and constant time independent of database size N.Small radii such as r=1 or 2 are commonly used to avoid exponential growth in searched code combinations.

C. Randomized Hashing Methods

Randomized hashing uses data-independent projections or permutations to preserve similarity through hash collisions, but often requires long codes and multiple tables for accurate ANN search. Random projection hashing targets angular locality, while MinHash preserves Jaccard similarity for sets and sparse vectors.

  • Random projection based hashing: LSH selects hash functions so nearby points have a high probability of sharing a hash bit or bucket.Random projection hashing preserves locality from the original space in Hamming space.
  • Randomized hashing overview: Randomized hashing has been applied across similarity measures including cosine and Jaccard similarity.The survey reviews random projection and random permutation approaches as two randomized hashing categories.
  • Random projection based hashing: Long hash codes reduce false collisions but can lower recall, while multiple hash tables increase recall at higher storage and query costs.For l K-bit tables, the precision–recall tradeoff requires additional indexing resources.
  • Random permutation based hashing: MinHash approximates Jaccard similarity by using minimum indices after random permutations of set elements.Its collision probability equals the Jaccard similarity between two sets.
  • Random permutation based hashing: MinHash extends to vectors and performs well for high-dimensional sparse representations such as document bag-of-words and image feature histograms.A large-scale webpage duplicate-detection evaluation reported that MinHash outperformed competing methods.

III. Categories of Learning Based Hashing Methods

Learning to hash focuses on designing improved data-dependent hash functions, with most methods targeting compact, discriminative codes usable in a single hash table. Some work also learns complementary multiple tables to improve precision and recall.

  • Learning to hash focus: Learning to hash emphasizes improved data-dependent hash functions as a central step in hashing-based ANN search.The survey primarily categorizes techniques by learning paradigm and hash-function characteristics.
  • Single-table methods: Most emerging methods seek compact discriminative codes so small Hamming-ball searches or Hamming-space scans can be fast and accurate.This focus supports indexing with a single hash table.
  • Multiple-table methods: Sequentially learned complementary hash tables can improve both precision and recall through a boosting-style procedure.Multitable indexing can also accelerate exhaustive Hamming-space scans when codes are short and databases are large.

A. Data-Dependent vs. Data-Independent

Hashing methods divide into data-independent approaches, such as LSH, and data-dependent approaches that use data properties or supervision. Learning-based methods span unsupervised, semi-supervised, and supervised settings and vary in function form, optimization, and bit weighting.

  • Data dependence: Data-independent hashing designs functions without analyzing a given dataset, whereas data-dependent methods use data and possibly supervision.LSH and related random-projection methods are presented as prominent data-independent examples.
  • Learning paradigms: Unsupervised hashing exploits distributions or manifold structure to learn compact codes with improved accuracy.Representative methods include spectral, graph, manifold, iterative-quantization, kernelized, isotropic, and angular-quantization hashing.
  • Learning paradigms: Semi-supervised hashing can combine labeled metric learning with unsupervised hash-function design.The survey classifies metric learning combined with LSH as semi-supervised when labels learn the metric but not the hash function.
  • Supervision levels: Supervised information ranges from pointwise labels and pairwise relations to triplet comparisons and ranking orders.Pairwise methods may underuse ranking information, while triplet methods encode proximity comparisons among three points.
  • Hash-function characteristics: Linear hash functions are computationally efficient, while nonlinear methods address their limited discriminative power.PCA hashing uses large-variance projections; spectral hashing further partitions projections with a sinusoidal function.
  • Learning procedures: Learning procedures may optimize all hash functions jointly or learn them sequentially while accounting for earlier functions' bias.The survey calls these single-shot and multiple-shot learning paradigms.
  • Weighted hashing: Weighted Hamming embeddings assign unequal importance to bits because large-variance projections often provide stronger discrimination.BSSC jointly learns hash functions and bit weights to reduce nonneighbor collisions while improving neighbor collisions.

IV. Methodology Review and Analysis

The survey reviews representative unsupervised, semi-supervised, and supervised hashing methods, emphasizing their formulations, technical merits, and practical trade-offs. These approaches design data-specific hash functions, with anchor graphs addressing scalability and nonlinear structure without assuming uniform data distribution.

  • Method categories: The reviewed framework spans unsupervised, semi-supervised, and supervised methods, including spectral, anchor graph, angular quantization, metric-learning, and ranking-based hashing.Table II summarizes the surveyed techniques and their technical merits.
  • Spectral hashing: Spectral hashing preserves neighborhood relationships while enforcing balanced and uncorrelated binary codes through relaxed graph-partitioning optimization.The exact balanced graph-partitioning problem is NP-hard, motivating spectral relaxation under a uniform-distribution assumption.
  • Anchor graph hashing: Anchor graph hashing approximates pairwise similarities with point-to-anchor relationships, reducing the eigenproblem from N×N scale to an M×M system with M much smaller than N.The method follows the spectral-hashing objective without assuming uniform data distribution.
  • Anchor graph hashing: On nonlinear two-moon data, anchor graph hashing separates the manifold with the first bit and maintains balanced partitioning, outperforming exact graph hashing on the reported comparison.Exact graph hashing loses balanced partitioning for the second bit, while spectral hashing cannot handle this nonlinear structure effectively.
  • Angular quantization: Angular quantization assigns each non-negative feature vector to its nearest binary-hypercube vertex, then learns a rotation or lower-dimensional projection for compact codes.The optimal codes and projection or rotation matrix are learned by alternating optimization.

D. Binary Reconstructive Embedding

Binary Reconstructive Embedding learns data-dependent, bit-correlated hash functions by matching distances in the original metric space to reconstructed Hamming distances. Its optimization uses coordinate descent and requires appropriate normalization because the two distance scales differ.

  • Hash functions: The hash functions use training samples, a kernel function, and a learned weight matrix to produce data-dependent, bit-correlated codes.This replaces data-independent random projections or principal components with learned functions.
  • Objective: Binary Reconstructive Embedding minimizes the discrepancy between Euclidean metric distances and reconstructed distances in Hamming space.The reconstruction objective is defined over training sample pairs.
  • Optimization: Coordinate descent iteratively updates the hash functions to reach a local optimum because the sign function makes direct optimization difficult.The method can be extended to supervised hashing by assigning zero distances to same-label pairs and large distances to different-label pairs.
  • Limitation: Input normalization is needed because reconstructed Hamming distance is bounded in [0,1], whereas the metric distance has no upper bound.Unit-hypersphere normalization makes the metric distance comparable but removes data-point scale information.

E. Metric Learning based Hashing

Metric-learning hashing learns a Mahalanobis metric from pairwise labels and incorporates it into randomized hash functions so similar and dissimilar pairs receive different collision behavior. The section also contrasts this with semi-supervised hashing, which combines labeled accuracy with entropy over unlabeled data.

  • Metric-learning hashing: Metric-learning hashing learns a parameterized Mahalanobis metric from pairwise label information before applying randomized projection-based hash functions.The learned metric is factorized so distances become Euclidean distances between transformed data points.
  • Metric-learning hashing: The resulting hash codes preserve the learned similarity measure in Hamming space, making similar pairs more likely to share hash bits.Figure 8 contrasts standard random-projection LSH with metric-learning-based LSH.
  • Practical trade-offs: Supervised hashing can outperform unsupervised approaches, but costly, noisy, and sparse annotations can promote overfitting in large-scale settings.The performance of hashing methods also depends strongly on learning parameters and dataset characteristics.
  • Semi-supervised hashing: Semi-supervised hashing uses a small set of pairwise labels and abundant unlabeled data, optimizing labeled empirical accuracy while maximizing entropy across the dataset.Similar and dissimilar pairs are represented by separate constraint sets and a labeled-information matrix.
  • Semi-supervised hashing: Optimizing only labeled accuracy can perfectly fit pairwise labels yet produce imbalanced, uninformative partitions on unlabeled data.An information-theoretic regularizer addresses this issue by encouraging high-entropy hash bits.

G. Column Generation Hashing

Column generation hashing uses ranking comparisons rather than only pairwise labels to learn weighted hash functions that preserve relative similarity in weighted Hamming space. A large-margin objective is optimized iteratively by generating hash functions and updating their weights.

  • Ranking supervision: Ranking supervision represents that a positive sample is more similar to a query than a negative sample, often matching information available in retrieval and recommendation applications.The comparison is expressed as a query-centered triplet.
  • Column generation hashing: Column generation hashing preserves these relative comparisons in a weighted Hamming space using weighted hash functions.The method is presented as a representative large-margin approach for ranking-preserving hashing.
  • Optimization: Its large-margin formulation uses random projections for hash codes together with regularization and ranking constraints.The formulation can use an ℓ1 norm and alternative loss functions or regularizers.
  • Optimization: Column generation solves the optimization iteratively by generating the best hash function and updating the associated bit-weight vector at each iteration.The approach alternates between expanding the hash-function set and revising weights.

H. Ranking Supervised Hashing

Ranking Supervised Hashing preserves query-specific ranking orders in Hamming space by matching ground-truth and hash-derived ranking triplet matrices. Its constrained objective also reduces redundancy between hash bits.

  • For each query, semantic relevance or feature similarity produces a ranking list that is converted into a ranking triplet matrix.
  • The method estimates a relaxed ranking triplet matrix from binary hash codes and minimizes its inconsistency with the ground-truth matrix.
  • A triplet entry indicates which of two database samples should rank closer to the query in Hamming space.
  • With linear hash functions, the formulation is a constrained quadratic problem whose orthogonality constraint minimizes redundancy between hash bits.

I. Circulant Binary Embedding

Circulant Binary Embedding uses circulant projections to reduce the cost of generating binary hashes, while the survey situates it alongside several deep hashing approaches. Deep methods jointly or sequentially learn representations and hash codes, but hashing speed remains underreported.

  • I. Circulant Binary Embedding: Circulant Binary Embedding computes binary codes as the sign of a circulant projection, which can be implemented through circular convolution and the fast Fourier transform.
  • I. Circulant Binary Embedding: The circulant projection reduces time complexity from d2 to dlog d, and its vector may be random or learned with supervision.
  • V. Deep Learning for Hashing: Deep hashing methods learn compact binary representations using neural networks, including generative models, hierarchical transformations, and supervised objectives.
  • V. Deep Learning for Hashing: CNN Hashing integrates image feature learning with hash-value learning, while Deep Semantic Ranking Hashing preserves multilevel similarities from image triplets.
  • V. Deep Learning for Hashing: Deep Neural Network Hashing jointly learns image representations and hash values and was shown to surpass CNN Hashing and several shallow supervised methods in image-search accuracy.
  • V. Deep Learning for Hashing: Most deep hashing methods did not report hash-generation time, raising concerns about practical speed compared with shallow methods such as ITQ and KSH.

VI. Advanced Methods and Related Applications

Advanced hashing extends approximate search beyond conventional point-to-point queries to hyperplanes and other structured objects. Hyperplane methods preserve angle-sensitive collisions with different accuracy–cost trade-offs, while related applications motivate scalable specialized search.

  • A. Hyperplane Hashing: Point-to-hyperplane hashing addresses nearest-neighbor search where the query is a hyperplane rather than a point, a setting distinct from conventional point-to-point search.
  • A. Hyperplane Hashing: Hyperplane hashing is important for scalable SVM active learning, which selects unlabeled samples near the current hyperplane decision boundary.
  • A. Hyperplane Hashing: The target hyperplane neighbors are points with small point-to-hyperplane angles, while wide-angle points should be avoided.
  • A. Hyperplane Hashing: AH-Hash collision probability decreases monotonically with point-to-hyperplane angle, providing angle-sensitive hashing.
  • A. Hyperplane Hashing: EH-Hash also has angle-sensitive collisions but is more expensive to compute than AH-Hash because it operates in an embedded d2-dimensional space.
  • A. Hyperplane Hashing: BH-Hash has twice AH-Hash’s collision probability, exceeds EH-Hash’s, and is computed in Θ(2d) time versus Θ(2d2) for EH-Hash.

B. Subspace Hashing

Subspace hashing targets approximate nearest-subspace search by mapping subspaces into a vector space and applying conventional hashing. Later work provides faster point-to-subspace hashing with linear-time hash computation and sublinear search.

  • Subspace hashing supports applications involving image patches, image sets, video clips, and other subspace representations.
  • A general approximate nearest subspace framework maps queries and database elements to points in a new vector space before applying conventional vector hashing.
  • The mapping-plus-LSH approach reduces subspace hashing to a regular vector hashing task.
  • For point-to-subspace queries, a later method hashes D-dimensional vectors or D×r-dimensional subspaces in O(D) time and achieves sublinear search time in database size.
  • Faster hashing for subspace-to-subspace queries with varying dimensions remains an identified direction for theoretical and practical work.

C. MultiModality Hashing

Multi-modality hashing extends learned hash functions beyond single representations to jointly index heterogeneous data while preserving semantic relationships across modalities.

  • Most hash-learning methods target a single modality, but newer approaches address multimodal and heterogeneous data common in social networks.These settings require hash functions designed for more complex data representations.
  • Composing hashing combines multiple information sources, using feature concatenation or iterative weighting to derive hash functions.Its objective can jointly index images and text while preserving semantic relations.
  • Boosted co-regularization combines intra-modality and inter-modality losses, sequentially reducing bias from previously learned hash functions.The objective is optimized through a boosting procedure.
  • Dual-view hashing learns a shared Hamming embedding from two views while maintaining the predictability of the binary codes.
  • Multimedia indexing is a natural application, with supervised and semi-supervised hashing widely studied for image search, retrieval, and mobile product search.Related applications include image patch matching, classification, face recognition, pose estimation, and object-related tasks.
  • Open issues include missing theoretical guarantees for most learning-based hashing methods and uncertainty about using compact codes directly for general learning tasks without accuracy loss.The survey calls for theoretically sound practical methods, including resource-constrained settings such as mobile devices.
Loading 1509.05472v1…