Fast Exact Search in Hamming Space With Multi-Index Hashing

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

171 citations recorded by the source corpus.

There is growing interest in representing image data and feature descriptors using compact binary codes for fast near neighbor search. Although binary codes are motivated by their use as direct indices (addresses) into a hash table, codes longer than 32 bits are not being used as such, as it was thought to be ineffective. We introduce a rigorous way to build multiple hash tables on binary code substrings that enables exact k-nearest neighbor search in Hamming space. The approach is storage efficient and straight-forward to implement. Theoretical analysis shows that the algorithm exhibits sub-linear run-time behavior for uniformly distributed codes. Empirical results show dramatic speedups over a linear scan baseline for datasets of up to one billion codes of 64, 128, or 256 bits.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Algorithms & Complexity

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Algorithms & Complexity

Citations in the corpus

TGIF: A New Dataset and Benchmark on Animated GIF Description (2016, methodology): “We compute 64bit DCT image hash using pHash [45] and apply multiple index hashing [24] to perform k nearest neighbor search ( k = 100 ) in the Hamming space.”
Learning descriptors for object recognition and 3D pose estimation (2015, methodology): “So far the only recognition approaches that have been demonstrated to work on large scale problems are based on Nearest Neighbor (NN) classification [23, 16, 8], because extremely efficient methods for NN search exist with an average complexity of O(1) [24, 21].”
Near neighbor searching with K nearest references (2015, background): “Such techniques turn out to be useful in specific areas like computer vision [40].”
Scalable Semi-Supervised Learning by Efficient Anchor Graph Regularization (2016, methodology): “Additionally, hashing strategies [7], [32], [29] can also be applied to facilitate large-scale classification.”
Multiscale Quantization for Fast Similarity Search (2017, methodology): “Compared to IVFADC [20], which uses plain PQ with coarse quantizers, our end-to-end trained MSQ reduces quantization error by 15-20% on SIFT1M, and 20-25% on DEEP10M, which is a substantial reduction.”
Binary Stochastic Representations for Large Multi-class Classification (2017, methodology): “For instance, the proposed method in [11] achieves a complexity in O ( c √ k log 2 k ).”