Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TPAMI.2013.231 | Pattern Analysis and Machine Intelligence, IEEE Transactions |
Keywords | Field | DocType |
cryptography,feature extraction,image coding,image representation,search problems,Hamming space,compact binary codes,distributed codes,fast exact search,feature descriptors,hash table,image data representation,k-nearest neighbor,multiindex hashing,Binary codes,Hamming distance,large-scale image retrieval,multi index hashing,multi-index hashing,nearest neighbor search | Hamming code,Pattern recognition,Computer science,Hamming(7,4),Block code,Theoretical computer science,Hamming distance,Artificial intelligence,Linear code,Hash function,Hamming space,Hash table | Journal |
Volume | Issue | ISSN |
36 | 6 | 0162-8828 |
Citations | PageRank | References |
47 | 1.16 | 25 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohammad Norouzi | 1 | 1212 | 56.60 |
| A. Punjani | 2 | 49 | 1.86 |
| David J. Fleet | 3 | 5236 | 550.74 |