Tree-based compact hashing for approximate nearest neighbor search

Hashing methods map high-dimensional data onto compact binary codes for efficient retrieval. These methods focus on preserving the data similarity in Hamming distance between the mapped hash codes. In this paper we propose a novel hashing method motivated by maximizing the probability of data with the same hash code being true neighbors, under the constraint of code compactness. This method is data-dependent and generates quite compact hash codes. The key idea is to use a collection of tree-structured hyperplanes to satisfy the compactness constraint, as well as to maximize the lower bound of the objective function. We compare our method with some widely used hashing methods on real datasets of different sizes. The experimental results illustrate the superior performance of our method. The performance of this method is further effectively improved by a multi-table extension.