Fast Exact Search in Hamming Space With Multi-Index Hashing.

Area of Science:

• Computer Science
• Data Science
• Machine Learning

Background:

• Growing interest in compact binary codes for efficient image data and feature descriptor representation.
• Limitations of using binary codes longer than 32 bits as direct hash table indices were previously thought to be ineffective.

Purpose of the Study:

• To develop a rigorous method for building multiple hash tables on binary code substrings.
• To enable exact k-nearest neighbor search in Hamming space for large-scale datasets.

Main Methods:

• Constructing multiple hash tables utilizing binary code substrings.
• Implementing a storage-efficient and straightforward approach for indexing and searching.

Main Results:

• Theoretical analysis indicates sub-linear run-time performance for uniformly distributed codes.
• Empirical results demonstrate significant speedups compared to linear scan on datasets up to one billion codes (64, 128, or 256 bits).

Conclusions:

• The proposed method effectively enables exact k-nearest neighbor search in Hamming space.
• The approach offers substantial performance improvements for large-scale binary code indexing and retrieval.