Complementary projection hashing

Recently, hashing techniques have been widely applied to solve the approximate nearest neighbors search prob-lem in many vision applications. Generally, these hash-ing approaches generate 2c buckets, where c is the length of the hash code. A good hashing method should satisfy the following two requirements: 1) mapping the nearby data points into the same bucket or nearby (measured by the Hamming distance) buckets. 2) all the data points are evenly distributed among all the buckets. In this paper, we propose a novel algorithm named Complementary Pro-jection Hashing (CPH) to find the optimal hashing func-tions which explicitly considers the above two requirements. Specifically, CPH aims at sequentially finding a series of hy-perplanes (hashing functions) which cross the sparse region of the data. At the same time, the data points are evenly dis-tributed in the hypercubes generated by these hyperplanes. The experiments comparing with the state-of-the-art hash-ing methods demonstrate the effectiveness of the proposed method. 1