Hashing for Similarity Search: A Survey

By Jingdong Wang, Heng Tao Shen, Jingkuan Song, Jianqiu Ji. 2014

577 citations recorded by the source corpus.

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.

Subfields: 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 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.”
Clustering huge protein sequence sets in linear time (2017, methodology): “Linear-time clustering algorithms, using for instance hashing techniques, have been proposed [28, 29].”
Deep Hashing Network for Unsupervised Domain Adaptation (2017, neutral): “Against this backdrop, hashing has emerged as one of the most popular and effective techniques due to its fast query speed and low memory cost [48].”
Large-Scale Weakly-Supervised Pre-Training for Video Action Recognition (2019, methodology): “Following this, we use locality sensitive hashing [66] to measure the amount of overlap (percentage of feature match w.r.t. source video length) between each source and target video.”
A Survey on Learning to Hash (2016, background): “The detailed review on LSH can be found in [147].”
Binary Generative Adversarial Networks for Image Retrieval (2017, methodology): “With the rapidly increasing amount of images, similarity search in large image collections has been actively pursued in a number of domains, including computer vision, information retrieval and pattern recognition [39, 43].”
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.”
Deep Bayesian Hashing with Center Prior for Multi-modal Neuroimage Retrieval (2020, unknown): “For comprehensive surveys, we refer readers to [30] and [31].”
Correlation Hashing Network for Efficient Cross-Modal Retrieval (2016, methodology): “…topic in machine learning, computer vision, and multimedia retrieval [Bronstein et al., 2010; Kumar and Udupa, 2011; Zhen and Yeung, 2012a; Zhen and Yeung, 2012b; Song et al., 2013; Wang et al., 2014b; Yu et al., 2014; Hu et al., 2014; Zhang and Li, 2014; Liu et al., 2014; Long et al., 2016].”
HashNet: Deep Learning to Hash by Continuation (2017, methodology): “Please refer to [35] for a comprehensive survey.”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “For high-dimensional data, several hashing based methods have been proposed, including randomized [19, 1, 32] and learning-based techniques [34, 35, 15].”
ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms (2018, methodology): “using hashing. A lot of research has been conducted with respect to locality-sensitive hashing (LSH) [18], but there exist many other techniques that rely on hashing for ˙nding nearest neighbors; see [36] for a survey on the topic. We note that, in the realm of LSH-based techniques, algorithms guara”
A Growing Long-term Episodic & Semantic Memory (2016, methodology): “Various models have been proposed for this type of memory, such as Sparse Distributed Memory [19], Clean-up Memory [29], and approximate nearest neighbor search methods [34].”
Polysemous Codes (2016, background): “The literature on eﬃcient search with compact codes is vast and we refer the reader to two recent surveys [49,51] for extensive references on this subject.”
A Tutorial on Environment-Aware Communications via Channel Knowledge Map for 6G (2023, background): “One possible approach to generate such virtual locations is by using hashing algorithms, which are one-way functions that generate a fixed-length output from an input of arbitrary length [223].”
NASH: Toward End-to-End Neural Architecture for Generative Semantic Hashing (2018, methodology): “Semantic hashing is an effective approach for fast similarity search (Salakhutdinov and Hinton, 2009; Zhang ∗ Equal contribution. et al., 2010; Wang et al., 2014).”