# Fast Supervised Hashing with Decision Trees for High-Dimensional Data

arXiv: https://arxiv.org/abs/1404.1561 · HTML: https://mlsanity.com/paper/1404.1561/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Apr 2014.

## Built on by (most cited first, 2 of 2)

- [EcoFormer: Energy-Saving Attention with Linear Complexity](https://mlsanity.com/paper/2209.09004/) (2022)
- [Hashing Learning with Hyper-Class Representation](https://mlsanity.com/paper/2206.02334/) (2022)

## Abstract (arXiv)

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.