PaperlayerView exact revision on arXiv

Source-linked AI summary

Hashing for Similarity Search: A Survey

Jingdong Wang, Heng Tao Shen, Jingkuan Song, Jianqiu Ji

arXiv:1408.2927v1cs.DScs.CVcs.DB

TL;DR

Similarity search becomes difficult when databases are large or high-dimensional, motivating approximate methods. This survey reviews hashing through locality sensitive hashing and learning to hash, covering hash functions, distances, and search schemes; it also identifies scalability limits in hash-function learning.

  • Problem

    Exact nearest neighbor search can be computationally infeasible for large databases or costly distances, and high-dimensional problems motivate approximate search.

  • Method

    The survey organizes hashing algorithms into locality sensitive hashing and learning to hash, reviewing their hash functions, distance measures, and code-space search schemes.

  • Results

    The survey explains how the two hashing categories are designed to conduct similarity search and identifies future research trends.

  • Takeaways & Limitations

    Hashing supports approximate similarity search through data-independent or data-dependent hash functions and compact-code search.

  • Takeaways & Limitations

    Learning hash functions remains slow or infeasible on very large datasets and is often trained on smaller subsets instead.

Abstract

from arXiv · show

Similarity search (nearest neighbor search) is a problem of pursuing the data items whose distances to a query item are the smallest from a large database. Various methods have been developed to address this problem, and recently a lot of efforts have been devoted to approximate search. In this paper, we present a survey on one of the main solutions, hashing, which has been widely studied since the pioneering work locality sensitive hashing. We divide the hashing algorithms two main categories: locality sensitive hashing, which designs hash functions without exploring the data distribution and learning to hash, which learns hash functions according the data distribution, and review them from various aspects, including hash function design and distance measure and search scheme in the hash coding space.

1 INTRODUCTION

Similarity search seeks the nearest database item to a query, but exact search becomes infeasible for large databases or costly distance computations. The survey presents hashing as an approximate-search solution using either locality-sensitive hash tables or short-code distance approximation.

  • Similarity search finds the database item nearest to a query under a specified distance measure.
  • Hashing transforms data items into low-dimensional representations or short binary codes for approximate nearest neighbor search.
  • Hash-table methods retrieve items sharing query buckets, exploiting the higher collision probability of similar items.
  • Short-code methods rank items using distances computed from compact codes, aiming to preserve similarity while reducing computation.

2 OVERVIEW

Nearest neighbor search selects items closest to a query, while approximate and randomized variants trade exactness or determinism for scalable retrieval. Hashing supports this through bucket lookup or efficient short-code distances, often followed by candidate reranking.

  • Nearest neighbor search returns the item minimizing dist(q, x), while K-NN search returns the K closest items.
  • Approximate nearest neighbor search seeks an item within a multiplicative distance factor or within a relaxed R-near-neighbor radius.
  • Randomized search reports approximate or exact near neighbors with probability 1 − δ rather than deterministically.
  • Hashing maps reference and query items to compact codes so approximate search can use codes and possibly a small subset of raw items.
  • The two basic code-search strategies are hash-table lookup and fast distance approximation.
  • Hash-table lookup maximizes collisions among near items, retrieves query-bucket contents, and can use multiple tables to improve recall.
  • Fast distance approximation exhaustively compares query and reference codes, then can rerank candidates using original-feature distances.
  • Non-exhaustive search retrieves candidates through inverted indexes or organizes codes in tree or graph structures to avoid scanning everything.

3 LOCALITY SENSITIVE HASHING: DEFINITION AND INSTANCES

Locality-sensitive hashing (LSH) supports approximate nearest neighbor search by mapping similar items to the same code more often than dissimilar items. The survey covers LSH families, search schemes, theoretical performance, and instances for several distances and similarities.

  • Hash-function families: LSH research develops hash families for ℓp, angular, Hamming, and Jaccard distances or similarities.Examples include p-stable distribution LSH for ℓp distance, sign-random-projection for angular distance, and min-hash for Jaccard coefficient.
  • Definition: LSH maps similar input items to the same hash code with higher probability than dissimilar items.The framework was introduced for efficient approximate nearest neighbor search in high-dimensional space.
  • Search scheme: The LSH scheme indexes items in hash-table buckets and retrieves items sharing the query's bucket as near-item candidates.Unlike conventional hashing, LSH seeks collisions between nearby items rather than avoiding collisions.
  • Search scheme: Concatenating K independently chosen hash functions amplifies the gap between near-item collision probability P1 and far-item collision probability P2.Long codes improve precision, but the resulting bucket space can be too large for direct indexing, so only nonempty buckets are retained.
  • Instances: For Euclidean distance, Gaussian random projections yield a p-stable LSH with exponent ρ strictly below 1/c for some finite r.The survey also reports LSH instances for angular distance, χ2 distance, and pairwise-order similarity.

4 LOCALITY SENSITIVE HASHING: SEARCH, MODELING, AND ANALYSIS

This section reviews search schemes, modeling approaches, and analyses for locality-sensitive hashing, including multi-probe, adaptive, tree-based, and fast implementations. It also examines parameter optimization, relative contrast, and the limitation that data-independent hash functions can underperform in some applications.

  • Search schemes: Entropy-based search uses O(N^ρ) random points and a single hash table with K = N log(1/g) hash bits, with theoretical evidence guaranteeing search quality.The method searches buckets associated with sampled points in a ball around the query.
  • Search schemes: Multi-probe LSH orders perturbations by boundary-distance scores and achieves similar time efficiency while reducing hash tables by an order of magnitude.The method probes likely neighboring buckets rather than only the query’s bucket.
  • Search schemes: Fast LSH computes hash codes in O(d log d + KL) instead of O(dKL) and reduces approximate-angle query time to O(d log 1/ε + 1/ε^2).These algorithms use structured transformations including Hadamard transforms and sparse or diagonal random operations.
  • Search schemes: Bi-level LSH first partitions data with a random-projection tree, then applies a hierarchical LSH table enhanced with Morton-curve organization and E8 lattice partitioning.The first-level groups have bounded aspect ratios, while the hierarchy helps when multi-probe LSH retrieves too few candidates.
  • Modeling and analysis: Relative-contrast analysis relates nearest-neighbor difficulty to dimensionality, database size, metric norm, and normalized variance, and extends to the kth nearest neighbor.The analysis defines normalized variance using the distance distribution and gives an approximation involving the Gaussian cumulative density function.
  • Modeling and analysis: Because LSH hash functions are data-independent, practical performance can be worse than expected in certain applications, motivating data-learned hash functions.The survey contrasts strong theoretical properties with this practical limitation.

5 LEARNING TO HASH: HAMMING EMBEDDING AND EXTENSIONS

Learning to hash learns compact codes and their coding-space similarity measures from data distributions, balancing efficient search with preservation of input-space similarity.

  • Core framework: Learning to hash maps each input item to a compact code so nearest-neighbor search in coding space approximates search in input space.Its design combines a hash function, a coding-space similarity measure, and an optimization criterion.
  • Hash function: Hash functions may use linear projections, spherical functions, kernels, neural networks, or non-parametric mappings.Linear sign functions and nearest-vector assignment are representative constructions.
  • Hash function: The hash-function type affects code-computation efficiency and the flexibility of space partitioning.Parameter optimization depends on the selected distance measure and distance-preservation objective.
  • Distance measure: Coding-space distances include Hamming distance and Euclidean distance, alongside variants such as weighted Hamming distance and distance-table lookup.Hamming distance counts differing binary positions, while Euclidean distance is used with nearest-vector assignment.
  • Optimization criterion: Optimization criteria include order preservation, similarity alignment, coding consistency, and coding balance.Coding balance seeks uniformly distributed reference vectors in each hash bucket; related criteria include bit balance and bit independence.
  • Coding consistent hashing: Spectral hashing seeks Hamming-consistent codes with few bits while enforcing bit balance and bit uncorrelation.Its approximate solution assumes uniformly distributed data and uses PCA directions, low-eigenvalue Laplacian eigenfunctions, and zero thresholding.

5.2 Similarity Alignment Hashing

Similarity alignment hashing directly aligns distances or similarities computed in the input and coding spaces. Reviewed methods implement this goal through reconstruction, kernels, probability alignment, or bilinear hashing.

  • Overview: Similarity alignment hashing minimizes discrepancies between input-space and coding-space similarities or distances.Distance-distribution alignment and quantization can also be interpreted within this category.
  • Distance alignment: Binary reconstructive embedding learns codes by minimizing the difference between input-space Euclidean distances and code-space Hamming distances.The objective uses a set of point pairs containing nearest neighbors and other pairs.
  • Kernel methods: Supervised hashing with kernels combines kernel-based hash functions with alignment between Hamming affinity and labeled or distance-based similarity.Pairs may be marked similar or dissimilar, and the method optimizes their affinity differences.
  • Distribution alignment: Spec hashing treats normalized pairwise similarities as probabilities and aligns probability distributions from the input and Hamming spaces.The Hamming-space distribution is defined using an exponential function of Hamming distance and a normalization variable.
  • Bilinear hashing: Bilinear hyperplane hashing transforms vectors into higher-dimensional representations and applies sign-based hashing to database vectors or hyperplane normals.Its random factors are independently sampled from standard Gaussian distributions, though they can also be learned from similarity information.

5.3 Order Preserving Hashing

Order-preserving hashing targets agreement between similarity rankings in the original and Hamming spaces. Methods use hinge-like penalties, category alignment, triplet supervision, and weighted embeddings.

  • Overview: Order-preserving hashing maximizes alignment between similarity orders in the original space and the Hamming space.The reviewed category focuses on ranking agreement rather than merely matching individual distances.
  • Pairwise ordering: Minimal loss hashing penalizes similar points that are too far apart and dissimilar points that are too close in Hamming space.A convex-concave upper bound is optimized with a perceptron-like learning procedure.
  • Pairwise ordering: Order preserving hashing divides database points into distance-based categories and maximizes alignment between categories defined in original and Hamming spaces.The sign operator is dropped and the resulting problem is solved with a quadratic penalty algorithm.
  • Triplet supervision: Triplet loss hashing preserves relative similarity by requiring each anchor-positive pair to be closer than its anchor-negative pair.Its loss is max(∥y − y+∥1 − ∥y − y−∥1 + 1, 0).
  • Weighted embeddings: Similarity sensitive coding learns a weighted Hamming embedding whose weak-learner weights encode task-specific similarity.Boosted SSC aggregates binary outputs from weak classifiers into the embedding.

5.4 Regularized Space Partitioning

Regularized space-partitioning methods seek effective partitions without explicitly evaluating coding-space distances. They impose balance, margin, kernel, spherical, or density-based structure during hash-function learning.

  • Overview: Regularized space partitioning pursues effective partitions without explicitly evaluating distance in the coding space.The broader hashing view interprets algorithms as methods for partitioning the data space.
  • Partition regularization: Complementary projection hashing constructs each hash function using distances to previously learned partition planes.It also imposes pairwise bit balance so four subspaces formed by two hyperplanes contain approximately N/4 points each.
  • Margin methods: Label-regularized maximum margin hashing uses side information to seek hash functions that separate dissimilar pairs and group similar pairs.The formulation combines maximum-margin constraints with a bit-balance constraint.
  • Spherical hashing: Spherical hashing uses multiple hyperspheres defined by pivots and thresholds, with code distances based on shared inside or outside assignments.Its pivots and thresholds are learned iteratively to satisfy pairwise bit balance.
  • Density-sensitive hashing: Density-sensitive hashing uses k-means clusters to generate candidate hyperplanes and selects those that split the data most equally.Candidate functions are scored by entropy, and the highest-scoring L functions form the compound hash function.

5.5 Hashing with Weighted Hamming Distance

This section reviews hashing methods that use weighted Hamming distances to better measure similarity in code space. The methods either learn bit weights, select bits per query, or optimize weighted affinities.

  • Weighted Hamming distance: Multi-dimensional spectral hashing optimizes hash codes and diagonal weights so weighted Hamming affinity matches the original affinity.Its selected eigenfunctions define the hash bits, and lookup tables can accelerate computation.
  • Weighted Hamming distance: Weighted Hamming schemes evaluate distances between hash codes using unequal bit contributions.Weighted hashing explicitly incorporates weights into the Hamming distance formulation.
  • Weighted Hamming distance: Weighted hashing solves a formulation that separates similar and dissimilar pairs while learning a weighted Hamming distance.The method binarizes at medians and learns linear hash functions for individual bits.
  • Query-adaptive weighting and selection: Query-informed methods learn class-specific weights or select hash functions according to each query.Query adaptive hashing performs offline function learning followed by online query-dependent selection.

5.6 Other Hash Learning Algorithms

This section surveys hash-learning methods beyond the preceding weighted-distance schemes, including generative, local, manifold, sparse, and two-stage approaches. These methods learn embeddings, hash functions, or representations that preserve structure or reconstruct data.

  • Generative and global methods: Semantic hashing learns reconstructive binary codes with a deep generative model without using similarity information.The codes support similarity search because they can reconstruct the input data.
  • Generative and global methods: Spline regression hashing learns a global kernel hash function consistent with local hash functions associated with neighboring points.Its global function uses h(x) = vT φ(x).
  • Manifold and exact-search methods: Inductive manifold mashing clusters data, embeds cluster centers in a low-dimensional space, and derives a hash function from them.The procedure combines clustering, manifold embedding, and hash-function construction.
  • Manifold and exact-search methods: An exact nearest-neighbor method computes a lower bound before deciding whether an exact Euclidean distance is necessary.The lower bound is compared with the current minimum distance to prune exact evaluations.
  • Sparse and reconstructive coding: Anti-sparse coding maximizes the number of nonzero code elements and binarizes the resulting projection by its signs.Its codes permit explicit reconstruction of the original vector up to a scaling factor.
  • Two-stage embedding and extension: Several methods use two stages: learn binary embeddings first, then learn hash functions that map inputs to those codes.Examples include boosted decision trees, linear SVMs, elastic-net hash functions, and locally linear out-of-sample extensions.

5.7 Beyond Hamming Distances in the Coding Space

This section examines search methods that replace ordinary Hamming distance with alternative measures in the coding space. The approaches include integer-like distances, asymmetric lookup-based distances, query-sensitive similarities, and learned bit reconfiguration.

  • Overview: The section focuses on designing effective distance measures for binary codes and hash functions, summarized in Table 5.The broader coding-space measures include Hamming variants and Euclidean distance.
  • Beyond ordinary Hamming distance: Manhattan hashing converts multi-bit projection codes into integers so differences better reflect Euclidean ordering along each projection direction.It addresses neighborhood distortion caused when multiple bits represent one projection direction.
  • Asymmetric distance: Asymmetric distance methods compare query embeddings with code-conditioned representatives or lower bounds, then sum per-hash distances.Precomputed lookup tables and block grouping reduce summations and lookup operations.
  • Query-sensitive ranking: Query-sensitive hash-code ranking estimates projection-wise similarity for R-neighbor search under a Gaussian assumption and aggregates logarithmic similarities.Lookup tables are used to accelerate the computation.
  • Learned code-space distances: Bits reconfiguration learns a projection over precomputed hash codes that separates dissimilar pairs, brings similar pairs together, and balances bit distributions.A supervised locality-preserving refinement based on graph Laplacians is also applied.

6 LEARNING TO HASH: QUANTIZATION

This section surveys quantization-based learning-to-hash methods, which partition projected data or subspaces and encode the resulting assignments. The methods include transform, hypercubic, iterative, isotropic, angular, and product quantization.

  • Overview: Quantization-based hashing assigns projected data to discrete regions, with the section emphasizing partitioning projection values into multiple parts.Representative algorithms are summarized in Table 6.
  • Transform coding: Transform coding applies PCA, allocates bits across principal directions, and quantizes selected directions into clusters with binary center codes.Distances aggregate center-to-center or query-projection-to-database-center distances across selected directions.
  • Quantization schemes: Hyper­cubic quantization maps each data item to a vertex whose coordinates belong to {−1, 1}.The resulting representation is a binary-valued vector in an M-dimensional hypercube.
  • Quantization schemes: Iterative quantization reduces dimensionality with PCA and alternates between assigning binary codes and optimizing an orthogonal rotation.The rotation is solved as an orthogonal Procrustes problem.
  • Quantization schemes: Isotropic hashing rotates PCA-reduced data so variances across directions are equal, making hash bits contribute more equally to distance evaluation.Under an isotropic Gaussian distribution, its solution is equivalent to iterative quantization.
  • Quantization schemes: Angular quantization addresses cosine-similarity search by approximating each vector with its nearest binary-hypercube vertex and evaluating similarity in Hamming space.The nearest vertex can be found in O(d log d) time.
  • Product quantization: Product quantization divides the feature space into P subspaces, quantizes each into K clusters, and represents items with P code components.Query distances are evaluated through distance-table lookups and summed across subspaces.

7 LEARNING TO HASH: OTHER TOPICS

The survey covers additional hashing topics spanning multi-table learning, active and online learning, specialized hash constructions, sparse coding, and search schemes for binary codes.

  • Multi-table hashing: Complementary hashing sequentially learns multiple hash tables so nearest neighbors are likely to share a bucket in at least one table.The first compound hash function uses a similarity-based objective, while subsequent tables optimize the objective with different matrices.
  • Multi-table hashing: Reciprocal hash tables search a graph of candidate hash functions, updating graph weights with a boosting-style algorithm to select subsequent tables.Each graph vertex represents a binary-output hash function, weighted by how often similar pairs map to the same value.
  • Active and online learning: Active hashing learns a compound hash function and actively selects informative labeled pairs using certainty scores based on distances to hash-function hyperplanes.The procedure uses labeled, unlabeled, and candidate sets, with a selection objective involving normalized certainty scores, a similarity matrix, and a trade-off parameter.
  • Active and online learning: Online and smart hashing address sequentially arriving similar or dissimilar pairs, while smart hashing relearns only a small subset of hash functions for faster response.Online hashing updates all hash functions, whereas smart hashing limits relearning to a subset.
  • Specialized hash constructions: Concomitant hashing forms unordered two-bit codes from points with the smallest and largest absolute cosine similarity, with collision probability increasing with absolute inner product.The resulting code supports min-inner-product and max-inner-product interpretations through Hamming distance.
  • Specialized hash constructions: Other methods hash matrix features through bilinear projections, use sparse codes and inverted indices, or search binary vectors with substring tables and hierarchical cluster trees.Substring-based search unions candidates found near the query in at least one subcode, while tree-based search traverses multiple trees and linearly searches reached leaves.

8 DISCUSSIONS AND FUTURE TRENDS

The discussion identifies scalability and computation costs as open issues for hashing, including learning over very large datasets, encoding queries, distance-table construction, and multimodal data.

  • 8.1 Scalable Hash Function Learning: Pairwise-similarity methods trade training cost against accuracy through pair sampling, while many methods remain slow or infeasible at billion-item scale.Hash functions are often learned from about 1M items even when the database contains 1B items.
  • 8.2 Hash Code Computation Speedup: Hash code encoding can dominate query cost when few database items are compared, motivating faster projections such as circulant binary embedding.Fast Fourier transformation reduces the stated projection cost from O(d2) to d log d.
  • 8.3 Distance Table Computation Speedup: Product quantization methods require query-to-dictionary distance tables, whose computation can become substantial when codes rerank candidates from an inverted index.The survey identifies distance-table computation as a direction for further research.
  • 8.4 Joint-modality Hashing: Multimedia variety across data types, feature levels, and sources motivates joint-modality hashing that exploits relationships among modalities.The motivation includes video, image, audio, and hypertext data contributed by different users and organizations.

9 CONCLUSION

The paper surveys hashing for similarity search by organizing algorithms into locality sensitive hashing and learning to hash, and by examining how they support search.

  • Conclusion: The survey reviews locality sensitive hashing and learning to hash, showing how these categories are designed to conduct similarity search.It also points out future trends in hashing for similarity search.
Loading 1408.2927v1…