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. >
Our work is inspired in part by the multi-index hashing results of Greene, Parnas, and Yao @cite_42 . Building on the classical Turan problem for hypergraphs, they construct a set of over-lapping binary substrings such that any two codes that differ by at most @math bits are guaranteed to be identical in at least one of the constructed substrings. Accordingly, they propose an exact method for finding all @math -neighbors of a query using multiple hash tables, one for each substring. At query time, candidate @math -neighbors are found by using query substrings as indices into their corresponding hash tables. As explained below, while run-time efficient, the main drawback of their approach is the prohibitive storage required for the requisite number of hash tables. By comparison, the method we propose requires much less storage, and is only marginally slower in search performance.