A Survey on Learning to Hash

By Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, Heng Tao Shen. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016

1,084 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/2d024cda9043514b9335bd1fcdc288b74983220e

How researchers see this paper

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

In Computer Vision and Pattern Recognition

Citations in the corpus

Fine-Grained Image Analysis With Deep Learning: A Survey (2021, methodology): “Image hashing [201], [202] is a popular and effective technique for approximate nearest neighbor search, and has the potential to help with large-scale”
SIFT Meets CNN: A Decade Survey of Instance Retrieval (2016, methodology): “We refer readers to [67] for a survey of ANN approaches.”
Reconstruction Network for Video Captioning (2018, background): “It can be applied in various practical applications, such as image and video retrieval [33, 44, 22], answering questions from images [21], and assisting people who suffer from vision disorders [43].”
Robust Unsupervised Cross-modal Hashing for Multimedia Retrieval (2020, background): “Recently, hashing [2, 14, 23, 44, 47] has attracted increased attention for its great gains of both storage and computation in massive multimedia data [32].”
Unsupervised Deep Hashing with Similarity-Adaptive and Discrete Optimization (2018, background): “learning to hash), which aims to generate compact binary codes by learning from data [48].”
Controllable Video Captioning With POS Sequence Guidance Based on Gated Fusion Network (2019, background): “This task can be applied for high-level video understanding in a variety of practical applications, such as visual retrieval [26, 37, 48, 24], visual question answer-”
Learning Discriminative Binary Codes for Large-scale Cross-modal Retrieval (2017, background): “According to the discussions in [14], [25], [29], [30], and [40], these approaches can be divided into two main categories: unsupervised and supervised hashing methods.”
Learning Cross-Modal Common Representations by Private–Shared Subspaces Separation (2020, background): “Readers can refer to the related survey paper [42] to obtain a more comprehensive review of these cross-modal hashing methods.”
Efficient Passage Retrieval with Hashing for Open-domain Question Answering (2021, methodology): “Learning to hash (Wang et al., 2016, 2018) is a method for learning hash functions in a data-dependent manner.”
Dense Text Retrieval Based on Pretrained Language Models: A Survey (2022, neutral): “• Hashing-based approaches [248], [254], [255] assign vec-”
Variational Deep Semantic Hashing for Text Documents (2017, background): “Due to computational and storage eﬃciencies of compact binary codes, hashing methodshave been widely usedforsimilarity search, which is an essential component in a variety of large-scale information retrieval systems [33, 35].”
The Faiss Library (2024, positive): “Since the original work introducing product quantization search [16], quantization-based ANN has emerged as a powerful alternative to binary codes [17].”
Person Re-identification: Past, Present and Future (2016, background): “On the other hand, when it comes to retrieval, efﬁcient indexing structures [22] and hashing techniques [23] can be beneﬁcial for re-ID in a large gallery.”
A Decade Survey of Content Based Image Retrieval Using Deep Learning (2020, background): “The deep learning based generation of descriptors or hash codes is the recent trends large-scale content based image retrieval, due to its computational efficiency and retrieval quality [28].”
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[92, 95, 99].”
Progressive Generative Hashing for Image Retrieval (2018, methodology): “…learnt the projection based hash functions by leveraging the information contained in the data [Weiss et al. , 2008; Gong and Lazebnik, 2011; Wang et al. , 2017; Liu et al. , 2014b; Wang et al. , 2018; Kong and Li, 2012; Yu et al. , 2014; Liu et al. , 2014a; Shen et al. , 2015; Wang et al. , 2014].”