Multi-Index Hashing for Fast Hamming Space Search

15 concepts13 papers1 proposal

High-dimensional data—such as images, video, text, and source code—is frequently compressed into compact binary codes to enable rapid similarity searches. In this compressed representation, similarity is measured by the Hamming distance: the number of bit positions in which two codes differ.

When dealing with massive datasets containing millions or billions of items, we often want to find all entries within a small Hamming distance radius $r$ of a query code. Historically, practitioners faced a frustrating dilemma:

  1. Linear Scan: Check the query against every single item in the database. This requires $O(N)$ time, which becomes prohibitively slow as the dataset scales.
  2. Single Hash Table: Treat the full binary code as a hash key. To find all neighbors within a radius $r$, you must generate and probe every single binary key that differs from the query by up to $r$ bits. The number of lookups scales combinatorially as $\sum_{i=0}^r \binom{B}{i}$, where $B$ is the total bit length. For a standard 64-bit code and a modest radius of $r=4$, this requires over 600,000 lookups per query. For longer codes, the search space explodes exponentially, and the hash table becomes incredibly sparse and memory-inefficient.

Multi-Index Hashing (MIH) resolves this dilemma. It provides a way to perform exact nearest neighbor search in near-constant time, bypassing the exponential lookup explosion without resorting to slow linear scans.

The Core Intuition: The Pigeonhole Principle

The magic of Multi-Index Hashing relies on a simple mathematical truth: the Pigeonhole Principle.

Imagine you have a 64-bit binary code, and you are looking for neighbor codes that differ by at most $r = 3$ bits. Now, let's slice that 64-bit code into $m = 4$ disjoint, contiguous substrings of 16 bits each.

If a database code has a total Hamming distance of 3 or less from your query code, those 3 bit errors must be distributed across the 4 substrings. By the Pigeonhole Principle, it is impossible to put 3 errors into 4 distinct boxes without leaving at least one box completely empty. Therefore, at least one of the 4 substrings must match the query substring exactly.

More generally, if we partition a $B$-bit code into $m$ disjoint substrings, any neighbor within a total Hamming distance $r$ must have at least one substring with a local Hamming distance of at most: $$r' = \lfloor r/m \rfloor$$

In their foundational work, Mohammad Norouzi et al. leveraged this insight to design Multi-Index Hashing (Fast search in Hamming space with multi-index hashing, Fast Exact Search in Hamming Space With Multi-Index Hashing.). By choosing $m$ such that $r' = 0$ (i.e., $m = r + 1$), they guaranteed that a true neighbor would match the query exactly in at least one substring slot.

How Multi-Index Hashing Works

The algorithm operates in two phases: indexing and querying.

1. Index Construction

Instead of building one massive hash table for the entire $B$-bit code, the authors construct $m$ separate, smaller hash tables—one for each substring slot.

For every item in the database:

  • The $B$-bit code is sliced into $m$ disjoint substrings.
  • The item's identifier is inserted into the $i$-th hash table using the $i$-th substring as the hash key.

Because each substring is short (e.g., $B/m$ bits), the individual hash tables remain compact, dense, and scale linearly with the number of items in the database.

Database Code: [ 10110011 | 01101100 | 11110000 | 00001111 ]
                    |          |          |          |
              Table 1 Key  Table 2 Key  Table 3 Key  Table 4 Key

2. Query Processing

When a query code arrives, it is similarly sliced into $m$ substrings.

  • For each substring slot $i$, the algorithm probes the $i$-th hash table. It looks up all entries located within a very small local radius $r' = \lfloor r/m \rfloor$.
  • If $m = r + 1$, then $r' = 0$, meaning the algorithm only needs to perform a single, constant-time lookup for the exact substring key in each table.
  • The algorithm takes the union of the candidates retrieved from all $m$ tables. This forms a highly filtered candidate set.
  • Finally, the algorithm performs a true full-length Hamming distance check on this small candidate set to discard false positives (items that matched in one substring but had too many errors elsewhere).

Because the candidate set is orders of magnitude smaller than the entire database, this final verification step is incredibly fast. The approach guarantees exact results while achieving speedups of over 1000x compared to a linear scan.

Evolution and Broad Applications

The core concept of partitioning long codes into sub-indices to avoid exponential search spaces has since expanded far beyond uniform binary codes.

From Binary to Product Quantization

Product Quantization (PQ) is a popular alternative to binary hashing that compresses high-dimensional vectors into sequences of subspace cluster indices. The multi-table paradigm adapts naturally to this space. Toshihiko Yamasaki et al. (PQTable: Fast Exact Asymmetric Distance Neighbor Search for Product Quantization Using Hash Tables) and Yusuke Matsui et al. (PQTable: Nonexhaustive Fast Search for Product-Quantized Codes Using Hash Tables) demonstrated that quantized codes can be used directly as keys in a multi-table structure. By breaking down long PQ codes into smaller table lookups, they achieved up to $10^5$x speedups over linear scans without introducing any additional approximation error beyond the initial quantization.

Deep Hashing Integration

With the rise of deep learning, researchers began training neural networks to output binary hash codes directly from raw data. To make these deep representations searchable at scale, Hanjiang Lai et al. (Improved Search in Hamming Space Using Deep Multi-Index Hashing) integrated MIH into deep architectures, utilizing balanced constraints to ensure that the learned codes distribute evenly across the sub-hash tables. For large-scale code repositories, Wenchao Gu et al. (SECRET: Towards Scalable and Efficient Code Retrieval via Segmented Deep Hashing) showed that segmenting deep hash codes into smaller chunks for multi-table lookups reduces retrieval latency by over 95% compared to traditional full-length scans.

Variable-Length and Multi-Scale Partitioning

While classic MIH splits codes into equal-length segments, the framework has been optimized to handle non-uniform data distributions. Eng-Jon Ong et al. (Improved Hamming Distance Search Using Variable Length Hashing) discovered that partitioning binary codes into substrings of varying lengths allows for precise control over the retrieval probability curve, maximizing search efficiency on billion-scale datasets.

The underlying philosophy of multi-index partitioning appears across several other specialized domains:

Ultimately, whether applied to network packets, genomic sequences, or deep image embeddings, the core mechanism remains identical: breaking a long, complex key into smaller, manageable sub-problems allows us to trade exponential search spaces for fast, parallelizable, constant-time lookups.

Key Foundational Work

Fast search in Hamming space with multi-index hashing (2012) — contributed 2 concept elements to this direction.
Sequential hashing: A flexible approach for unveiling significant patterns in high speed networks (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multi_index_hashing_bb94f1db,
  title = {multi-index hashing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-index-hashing/rdr_bb94f1db81cd4f6fa75e6ac7b3d21bbd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_index_hashing_bb94f1db_v1,
  title = {multi-index hashing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-index-hashing/rdr_bb94f1db81cd4f6fa75e6ac7b3d21bbd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake