Complementary hashing for approximate nearest neighbor search
- 1 November 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15505499,p. 1631-1638
Abstract
Recently, hashing based Approximate Nearest Neighbor (ANN) techniques have been attracting lots of attention in computer vision. The data-dependent hashing methods, e.g., Spectral Hashing, expects better performance than the data-blind counterparts, e.g., Locality Sensitive Hashing (LSH). However, most data-dependent hashing methods only employ a single hash table. When higher recall is desired, they have to retrieve exponentially growing number of hash buckets around the bucket containing the query, which may drag down the precision rapidly. In this paper, we propose a so-called complementary hashing approach, which is able to balance the precision and recall in a more effective way. The key idea is to employ multiple complementary hash tables, which are learned sequentially in a boosting manner, so that, given a query, its true nearest neighbors missed from the active bucket of one hash table are more likely to be found in the active bucket of the next hash table. Compared with LSH that also can exploit multiple hash tables, our approach is more effective to find true NNs, thanks to the complementarity property of the hash tables from our approach. Experimental results on large scale ANN search show that the proposed method significantly improves the performance and outperforms the state-of-the-art.Keywords
This publication has 17 references indexed in Scilit:
- Locality sensitive hashing: A comparison of hash function types and querying mechanismsPattern Recognition Letters, 2010
- Self-taught hashing for fast similarity search2010
- Weakly-supervised hashing in kernel space2010
- Semi-supervised hashing for scalable image retrieval2010
- Small codes and large image databases for recognition2008
- Entropy based nearest neighbor search in high dimensions2006
- Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions2006
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Similarity estimation techniques from rounding algorithms2002
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975