Supervised hashing aims to map the original features to compact binary codes that are able to preserve label based similarity in the Hamming space. Non-linear hash functions have demonstrated the advantage over linear ones due to their powerful generalization capability. In the literature, kernel functions are typically used to achieve non-linearity in hashing, which achieve encouraging retrieval performance at the price of slow evaluation and training time. Here we propose to use boosted decision trees for achieving non-linearity in hashing, which are fast to train and evaluate, hence more suitable for hashing with high dimensional data. In our approach, we first propose sub-modular formulations for the hashing binary code inference problem and an efficient GraphCut based block search method for solving large-scale inference. Then we learn hash functions by training boosted decision trees to fit the binary codes. Experiments demonstrate that our proposed method significantly outperforms most state-of-the-art methods in retrieval precision and training time. Especially for high-dimensional data, our method is orders of magnitude faster than many methods in terms of training time.

本文利用增强决策树来实现哈希中的非线性，提出了基于次模形式的哈希二进制码推断问题和用于解决大规模哈希推断的高效GraphCut块搜索方法。实验证明，该方法在检索准确性和训练时间方面显著优于大多数最先进的方法，尤其是对于高维数据，该方法的训练时间比许多方法快数个数量级。

利用决策树进行高维数据的快速监督哈希