Efficient indexing of binary LSH for high dimensional nearest neighbor

In this paper, we propose a surprising simple method to solve the ANN problem with high accuracy results and requiring only a limited number of random I/O. For the distance-preserving properties of LSH functions, the idea of collision counting is used to guarantee the accuracy of the returned neighbours. We convert the dynamic collision counting problem into the nearest neighbor search (NN) in Hamming space. To support the NN search in the hamming space, we establish the multi-index hashing structure to rearrange the binary hash keys and their corresponding objectives. Accessing the candidates consumes a limited number of random I/O and shorter response time. Experimental results show that our method can achieve higher accuracy of ANN results compared with the state-of-the-art methods including LSB, C2LSH and SK-LSH.