Random Exemplar Hashing

Abstract. We present a new method that addresses the problem of approximate nearest neighbor search via partitioning the feature space. The proposed random exemplar hashing algorithm can be used to generate binary codes of data to facilitate nearest neighbor search within large datasets. Inspired by the idea of using an ensemble of classifiers for discriminative learning, we devise an unsupervised learning algorithm to explore the feature space with respect to randomly selected exemplars. Experimental results on three large datasets show that our method outperforms the state-of-the-art, especially on the cases of longer binary codes.