Fast search in Hamming space with multi-index hashing

By Mohammad Norouzi, Ali Punjani, David J. Fleet. 2012

291 citations recorded by the source corpus.

Subfields: Aerospace Engineering, 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 Aerospace Engineering

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, background): “In addition, binary codes incur important overheads for non-exhaustive search methods [35].”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “A great advantage of working with binary codes is their small storage cost and the fact that exact neighbor search can be done in sublinear time (Norouzi et al., 2012b).”
Hamming Distance Metric Learning (2012, methodology): “Computing AH distance is slightly less efficient than Hamming distance, and efficient retrieval algorithms, such as [25], are not directly applicable.”
Linear cross-modal hashing for efficient multimedia search (2013, background): “Although they have some asymptotic theoretical properties, LSH-like hashing methods often require long binary codes and multiple hash tables to achieve reasonable retrieval accuracy [20].”
Fast Exact Search in Hamming Space With Multi-Index Hashing (2013, unknown): “Approximate methods are interesting, and the approach below could be made faster by allowing misses.”
Fast Nearest Neighbor Search in the Hamming Space (2016, methodology): “Compared to FLANN and MIH, our approach enjoys two-fold advantages.”
HashNet: Deep Learning to Hash by Continuation (2017, methodology): “Many learning to hash methods have been proposed to enable efficient ANN search of high-dimensional data by ranking the Hamming distance across compact binary hash codes [19, 12, 27, 9, 23, 34, 25, 11, 38, 39].”
ImageNet Auto-Annotation with Segmentation Propagation (2014, methodology): “While this is already fast enough for the large-scale experiments in this paper, it could be accelerated even further with fast nearest neighbour techniques dedicated to hamming codes [46].”
Hashing for Similarity Search: A Survey (2014, methodology): “The idea [104] is that binary codes in the reference database are indexed M times into M different hash tables, based on M disjoint binary substrings.”
Deep Cauchy Hashing for Hamming Space Retrieval (2018, methodology): “We follow standard evaluation methods for Hamming space retrieval [9], which consists of two consecutive steps: (1) Pruning, to return data points within Hamming radius 2 for each query using hash table lookups; (2) Scanning, to re-rank the returned data points in ascending order of their distances ”
Deep Hashing Network for Efficient Similarity Retrieval (2016, methodology): “…have been proposed to enable efficient ANN search using Hamming distance (Kulis and Darrell 2009; Gong and Lazebnik 2011; Norouzi and Blei 2011; Fleet, Punjani, and Norouzi 2012; Liu et al. 2012; Wang, Kumar, and Chang 2012; Liu et al. 2013; Gong et al. 2013; Yu et al. 2014; Xia et al. 2014;…”
Discrete Collaborative Filtering (2016, methodology): “We adopted Multi-Index Hashing (MIH) table [22], which builds one table for each code subsegment.”
Segmentation Propagation in ImageNet (2012, unknown): “While this is already fast enough for the large-scale experiments in this paper, it could be accelerated even further with fast nearest neighbour techniques dedicated to hamming codes [31].”
Cartesian K-Means (2013, background): “The cluster regions are simply the four quadrants of the 2D space.”
Polysemous Codes (2016, methodology): “Additionally, Norouzi and Fleet have proposed an algorithm to speed-up the search in this Hamming space [41].”