Data driven multi-index hashing

Abstract

Binary representation for large scale nearest neighbor search received more and more concern recently. Although binary codes can be directly used as indices of the hash tables, correlations between the bits may lead to non-uniform codes distribution and reduce the performance of the hash table. In this paper, we propose a data driven multi-index hashing method for exact nearest neighbor search in Hamming space. By exploring the statistics properties of the dataset, we can separate the correlated bits into different segments during the process of building multiple hash tables, and thus make binary codes distributed as uniformly as possible in each hash table. Experiments conducted on a huge amount of binary codes extracted from the UK Bench dataset show that our method can achieve significant acceleration in searching speed for large scale dataset.