Learning to Hash for Indexing Big Data—A Survey

By Jun Wang, Wei David Liu, Sanjiv Kumar, Shih-Fu Chang. 2015

546 citations recorded by the source corpus.

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, semisupervised, 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.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Information Retrieval & Search

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

FastText.zip: Compressing text classification models (2016, methodology): “We refer the reader to two recent surveys by Wang et al. (2014) and Wang et al. (2015) for an overview of the binary hashing literature.”
Learning Discrete Representations via Information Maximizing Self-Augmented Training (2017, background): “…to remain unchanged under data augmentation (Red arrows), while maximizing the information-theoretic dependency between data and their representations (Blue arrow). while hash learning is popular for an approximate nearest neighbor search for large scale information retrieval (Wang et al., 2016).”
Transfer Hashing with Privileged Information (2016, methodology): “Hashing methods have been applied for efficient similarity search in many application areas, especially for information retrieval [Wang et al., 2016].”
Unsupervised Semantic-Preserving Adversarial Hashing for Image Search (2019, background): “Therefore more attention is being paid to hash-based methods [20], [21], [23], [31]–[36], which have relative low storage cost and a fast query speed.”
The Case for Learned Index Structures (2017, background): “Learning Hash Functions for ANN Indexes: There has been a lot of research on learning hash functions [49, 59, 67, 68].”
Pairwise Relationship Guided Deep Hashing for Cross-Modal Retrieval (2017, background): “For a comprehensive survey, we refer the readers to (Wang et al. 2016).”
Accelerating Large-Scale Inference with Anisotropic Vector Quantization (2019, methodology): “We refer readers to (Wang et al., 2014; 2016) for a comprehensive survey.”
An Overview of Cross-Media Retrieval: Concepts, Methodologies, Benchmarks, and Challenges (2017, background): “However, most of them only involve a single media type such as image [65].”
Discrete Collaborative Filtering (2016, background): “For comprehensive reviews of CF and hashing, please refer to [5] and [29], respectively.”
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, background): “Many studies in other fields show that an insightful taxonomy can serve as a guideline for promising research in this domain[99, 102, 105].”
Sketch-based manga retrieval using manga109 dataset (2015, methodology): “The two main branches of ANN methods include productquantization-based methods [18, 26] and hashing-based methods [36, 68, 69, 73].”
Top Rank Supervised Binary Coding for Visual Search (2015, background): “During the past few years, binary coding (also known as hashing [26] in the literature) techniques have been widely used in a variety of computer vision and machine learning applications, including object recognition [23, 24, 21], scene classification [22], image retrieval [9, 14, 8, 33, 34, 20], li”
Digital Twin: Values, Challenges and Enablers From a Modeling Perspective (2019, unknown): “[397] J.”
The Faiss Library (2024, unknown): “Faiss includes a benchmarking framework (bench_fw) that optimizes index types and parameters to explore accuracy , memory usage and search time operating points.”
A Survey on Learning to Hash (2016, background): “It should be noted that as pointed in [145], [147], other factors, such as the hash function, or the optimization algorithm, is also important for the search performance.”
Variational Deep Semantic Hashing for Text Documents (2017, background): “It has many important information retrieval applications such as document clustering, content-based retrieval, and collaborative ﬁltering [33]. rapid growth of Internet has resulted in massive textual data in the recent decades.”
Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement (v1.0) (2016, background): “Please refer to [42, 41] for a comprehensive survey.”
Central Similarity Quantization for Efficient Image and Video Retrieval (2019, background): “By transforming high-dimensional data to compact binary hash codes in the Hamming space via a proper hash function [37], hashing offers remarkable efﬁciency for data storage and retrieval.”