Source-linked AI summary
Fast Exact Search in Hamming Space with Multi-Index Hashing
Mohammad Norouzi, Ali Punjani, David J. Fleet
TL;DR
Long binary codes were not being used directly as hash indices because Hamming-ball bucket counts can make search inefficient. The paper introduces multi-index hashing on code substrings for exact Hamming-space kNN, with sub-linear theoretical behavior and large empirical speedups over linear scan.
Problem
Direct hash-table search becomes inefficient for long binary codes because the number of buckets within a Hamming radius grows near-exponentially.
Method
The method indexes disjoint binary-code substrings in multiple hash tables, retrieves guaranteed candidates, and verifies them using the full code.
Results
More than two orders of magnitude faster than linear scan on datasets of up to 1B 64-bit and 128-bit codes, with sub-linear behavior demonstrated theoretically and empirically.
Takeaways & Limitations
Multi-index hashing provides a practical exact-search data structure for large-scale binary-code datasets, combining storage efficiency with fast retrieval.
Takeaways & Limitations
The runtime analysis assumes uniformly distributed codes, although real database codes are not uniformly distributed and that distribution is not ideal for the method.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Binary codes offer compact storage and fast comparisons, but direct hash-table search becomes inefficient as code length and Hamming radius grow. The paper addresses this open problem with an exact, storage-efficient data structure for kNN and r-neighbor search in Hamming space.
- Motivation: Binary codes support compact storage, fast comparisons, and direct hash-table indexing for near-neighbor search.Direct indexing can dramatically accelerate search relative to exhaustive linear scanning.
- Problem: The number of hash buckets within a Hamming radius grows near-exponentially, often making direct hashing slower than linear scan.This limitation is especially problematic for codes longer than 32 bits, which are commonly needed for retrieval quality.
- Contribution: The paper introduces an exact kNN data structure with sub-linear search, storage efficiency, and straightforward implementation.The approach targets both kNN and fixed-radius neighbor search in Hamming space.
- Contribution: Multi-index hashing is reported to be hundreds of times faster than linear scan on databases containing up to 1B binary codes.The method is evaluated on binary codes derived from large-scale visual descriptors.
- Problem: 64-bit codes have about 1B buckets within a 7-bit Hamming radius, while 128-bit hash tables are prohibitive for radii above 6.These figures illustrate why conventional single-table hashing does not scale to large codes and practical search radii.
2 MULTI-INDEX HASHING
Multi-index hashing partitions each binary code into disjoint substrings and searches multiple substring hash tables. Carefully chosen substring radii guarantee exact retrieval while balancing bucket lookups, candidate verification, and storage.
- Algorithm: Database codes are indexed in m hash tables using m disjoint substrings, and candidates are verified with the full binary code.The union of substring candidates contains all true r-neighbors, after which full-code Hamming distances remove false candidates.
- Substring Search Radii: If two codes differ by at most r bits, at least one of their m substrings differs by at most ⌊r/m⌋ bits.This pigeonhole-based guarantee enables exact retrieval through shorter substring searches.
- Substring Search Radii: For r = mr′ + a, the algorithm searches a+1 substring tables at radius r′ and the remaining tables at radius r′−1.This refinement preserves the guarantee that all r-neighbors are found while reducing unnecessary bucket searches.
- Complexity Trade-off: The method trades fewer bucket lookups against more candidate checks, with m = q potentially producing a candidate set nearly as large as the database.Substring length therefore affects both query work and storage-related design choices.
- Novelty: Unlike earlier multi-table methods that relied heavily on exact substring matches, relaxing substring matching improves storage requirements.The paper identifies this relaxation as a key source of effectiveness.
3 PERFORMANCE ANALYSIS
The analysis models lookup and candidate-test costs to select substring lengths and characterize runtime and storage. Choosing s near log2 n yields sub-linear expected search time for small search-radius ratios, with storage O(nq + n log2 n).
- The cost model asks how substring length affects search cost and how runtime and storage scale with database size, code length, and search radius.
- Decreasing substring length increases the number of substrings but requires exponentially fewer lookups.
- For uniformly distributed codes, expected candidates equal the number of lookups times n/2^s, under the model’s bucket-occupancy assumption.
- s = log2 n is a near-optimal substring-length heuristic, and makes the expected number of items per substring bucket equal to 1.The cost curves remain minimal near this value across database sizes and search radii.
- O(q n^H(r/q)/log2 n) is the expected query-time complexity for uniform codes; it is sub-linear in n for small r/q.For r/q ≤ .11, the stated complexity becomes O(q √n/log2 n).
- O(nq + n log2 n) is the storage cost when m ≈ q/log2 n, while run-time increases slightly to reduce storage relative to prior multi-table hashing.The proposed storage includes the full codes and identifiers for substring hash tables.
4 k-NEAREST NEIGHBOR SEARCH
The kNN procedure progressively expands a per-substring search radius and validates candidates with full-code Hamming distances. This query-dependent strategy guarantees recovery of the required neighbors while adapting to local code distributions.
- A fixed Hamming radius may retrieve different numbers of neighbors across queries because binary codes are not uniformly distributed.
- Each candidate is checked using the full Hamming distance before being added to the distance-indexed neighbor sets.
- Finding more than k candidates within distance (r′ + 1)m − 1 guarantees that the k nearest neighbors have been found.
- The algorithm progressively increases the per-substring radius and cycles through substring hash tables until enough neighbors are found.
5 EXPERIMENTS
Experiments on large SIFT and Gist-derived binary-code datasets show that multi-index hashing provides exact search substantially faster than linear scan, with sub-linear query-time scaling and distribution-dependent performance. The implementation uses linear memory growth and remains effective across code lengths, neighbor counts, and hashing methods.
- 5 EXPERIMENTS: Memory requirements grow linearly with database size, requiring approximately 27 GB for 1B 64-bit codes and approximately twice that for 128-bit codes.The experiments use a single computer, while a distributed implementation could place substring hash tables on separate computers.
- 5.3 Multi-Index Hashing vs. Linear Scan: Multi-index hashing solves exact 1000-NN search on 1B 64-bit codes in about 50 ms, over 300× faster than linear scan.Performance on 1-NN and 10-NN is even more impressive.
- 5.3 Multi-Index Hashing vs. Linear Scan: Increasing the requested number of neighbors increases the Hamming search radius and lowers multi-index-hashing speedup, while linear-scan time remains unchanged.Queries requiring relatively large search radii tend to dominate average query cost.
- 5.3 Multi-Index Hashing vs. Linear Scan: Multi-index hashing is much faster than linear scan across a wide range of dataset sizes and k, with speedup factors improving as database size increases.The experiments cover 64-, 128-, and 256-bit codes on the AMD machine.
- 5.3 Multi-Index Hashing vs. Linear Scan: Sub-linear query time persists for empirical, non-uniform code distributions, as shown by multi-index-hashing curves tracking square-root curves on log-log plots.The paper uses the similar slope of the curves as evidence for sub-linear behavior.
- 5.5 Substring Optimization: Optimizing substrings provides overall run-time reductions on the order of 20% against consecutive substrings in some cases, with greater impact at longer code lengths.Figure 10 reports optimized-substring run-time behavior as a function of dataset size.
6 IMPLEMENTATION DETAILS
The implementation builds direct-address hash tables over disjoint code substrings, uses sparse storage and candidate deduplication, and selects the number of substrings empirically near q / log2 n. Its memory cost is linear in the database size and code length, while huge pages improve large-footprint access.
- Hash Tables: Multi-index hashing uses direct-address tables on disjoint s-bit substrings, mapping each substring to a bucket without collision detection.The implementation typically uses short substrings with s ≤32.
- Hash Tables: Sparse direct-address tables group 32 buckets, store occupancy vectors, and use one pointer per group to avoid allocating a full pointer array.This reduces the cost of empty 32-bit address tables compared with ordinary direct addressing.
- Memory Requirements: The total memory cost is m2^(s−5)24 + m min(n, 2^s)4 + 4mn + nms/8 bytes, and is O(nq) when s = log2 n.For 1B codes, the implementation requires 28 GB for 64-bit codes, 57 GB for 128-bit codes, and 113 GB for 256-bit codes.
- Query Processing: Candidate duplicates are removed with an n-bit marker string, while full-code Hamming distances use XOR operations followed by population counts.Duplicate marking has negligible practical run-time in the implementation.
- Parameter Selection: The number of substring hash tables is selected by hold-out validation near the heuristic q / log2 n.Cross-validation chooses the number yielding minimum estimated run-time among nearby values.
- Memory Access: Huge pages reduce page counts and TLB misses for large memory footprints, improving memory-access speed and reducing run-time volatility.The experiments use libhugetlbfs to allocate 2 MB pages instead of 4 KB pages.
7 CONCLUSION
The proposed multi-index hashing algorithm achieves sub-linear behavior theoretically and empirically, but important questions remain about realistic assumptions, substring design, and approximate search.
- 7 CONCLUSION: The substring-length choice and bit assignment remain open design issues for improving multi-index hashing.The authors identify log2 n as a promising substring length, call the current bit-assignment method suboptimal, and suggest different lengths across tables.
- 7 CONCLUSION: The algorithm exhibits sub-linear run-time behavior theoretically for uniformly distributed codes and empirically on real datasets.The theoretical guarantee assumes small search radius, while the experiments use non-uniform binary codes.
- 7 CONCLUSION: More realistic assumptions that preserve theoretical analysis remain an open problem because experimental codes are not uniformly distributed.The paper explicitly identifies bridging its theoretical analysis and empirical findings as unresolved.
- 7 CONCLUSION: Approximate variants could be more efficient, but comparisons would need to account for storage, run time, recall, and precision.The paper discusses stopping before all exact neighbors are found or before all substring tables are searched.
- 7 CONCLUSION: Asymmetric Hamming-distance methods are a related direction because they avoid quantizing the query into a binary string.The paper notes that directly comparing real-valued queries with database binary codes can avoid quantization noise.