A novel feature selection method for nearest neighbor search in binary embedding codes

We address the issue of search nearest neighbors in binary embedding codes by asymmetric distance computation. Although asymmetric distance computation can obtain a more accurate result than symmetric distance computation, its speed is much slower. Applying multi-index hashing can accelerate asymmetric distance computation. However, it takes more memory to store the index tables. Thus, how to select appropriate binary features for indexing under a certain memory constraint is a key issue to improve asymmetric distance computation. In this paper, we propose a novel feature selection method. When only partial index tables can be loaded into memory, the binary features with the lowest quantization error can be selected as a representative for indexing. Experimental results show that the proposed method improves the accuracy up to 8.35% and outperforms the linear scan approach and other feature selection methods.