# Fast Exact Search in Hamming Space with Multi-Index Hashing

arXiv: https://arxiv.org/abs/1307.2982 · HTML: https://mlsanity.com/paper/1307.2982/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2013.

## Built on by (most cited first, 6 of 6)

- [Improving Retrieval in Theme-specific Applications using a Corpus Topical Taxonomy](https://mlsanity.com/paper/2403.04160/) (2024)
- [Unsupervised Multi-Index Semantic Hashing](https://mlsanity.com/paper/2103.14460/) (2021)
- [Hierarchical Patch Compression for ColPali: Efficient Multi-Vector Document Retrieval with Dynamic Pruning and Quantization](https://mlsanity.com/paper/2506.21601/) (2025)
- [A Lower Bound of Hash Codes' Performance](https://mlsanity.com/paper/2210.05899/) (2022)
- [Footprints of Data in a Classifier: Understanding the Privacy Risks and Solution Strategies](https://mlsanity.com/paper/2407.02268/) (2024)
- [NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction](https://mlsanity.com/paper/2608.15438/) (2026)

## Abstract (arXiv)

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 straightforward 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.