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.
@cite_42: We describe a technique for building hash indices for a large dictionary of strings. This technique permits robust retrieval of strings from the dictionary even when the query pattern has a significant number of errors. This technique is closely related to the classical Turan problem for hypergraphs. We propose a general method of multi-index construction by generalizing certain Turan hypergraphs. We also develop an accompanying theory for analyzing such hashing schemes. The resulting algorithms have been implemented and can be applied to a wide variety of recognition and retrieval problems. >
@cite_8: We present two algorithms for the approximate nearest neighbor problem in high-dimensional spaces. For data sets of size n living in R d , the algorithms require space that is only polynomial in n and d, while achieving query times that are sub-linear in n and polynomial in d. We also show applications to other high-dimensional geometric problems, such as the approximate minimum spanning tree. The article is based on the material from the authors' STOC'98 and FOCS'01 papers. It unifies, generalizes and simplifies the results from those papers.
The second problem is to find all codes in a dataset @math that are within a fixed Hamming distance of a query, sometimes called the Approximate Query problem @cite_42 , or Point Location in Equal Balls (PLEB) @cite_8 . A binary code is an @math -neighbor of a query code, denoted @math , if it differs from @math in @math bits or less. We define the @math -neighbor search problem as: find all @math -neighbors of a query @math from @math .