NOKMeans: Non-Orthogonal K-means Hashing

Finding nearest neighbor points in a large scale high dimensional data set is of wide interest in computer vision. One popular and efficient approach is to encode each data point as a binary code in Hamming space using separating hyperplanes. One condition which is often implicitly assumed is that the separating hyperplanes should be mutually orthogonal. With the aim of increasing the representation capability of the hyperplanes when used for indexing, we relax the orthogonality assumption without forsaking the alternate view of using cluster centers to represent the indexing partitions. This is achieved by viewing the data points in a space determined by their distances to the hyperplanes. We show that the proposed method is superior to existing state-of-the-art techniques on several large computer vision datasets.