Fast Supervised Hashing with Decision Trees for High-Dimensional Data

By Guosheng Lin, Chunhua Shen, Javen Qinfeng Shi, Anton van den Hengel, David Suter. 2014 IEEE Conference on Computer Vision and Pattern Recognition, 2014

428 citations recorded by the source corpus.

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 their 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 perfor- mance 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 func- tions 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.

Subfields: Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/11ccebed975bedf09b4893d7e3c31be897a1f527

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Hashing with binary autoencoders (2015, background): “Some recent work has tried to respect the binary nature of the codes or thresholds by using alternating optimization directly on an objective function, over one entry or one row of the weight matrix in the hash function [16, 21], or over a subset of the binary codes [19, 18].”
Sketch-based manga retrieval using manga109 dataset (2015, methodology): “The two main branches of ANN methods include productquantization-based methods [18, 26] and hashing-based methods [36, 68, 69, 73].”
SSD-6D: Making RGB-Based 3D Detection and 6D Pose Estimation Great Again (2017, methodology): “We take random images from MS COCO [20] as background and render our objects with random transformations into the scene using OpenGL commands.”
Two-Stream Deep Hashing With Class-Specific Centers for Supervised Image Search (2020, methodology): “Fast supervised hashing (FastHash) [49] adopts boosted decision trees to achieve nonlinearity in hashing and ﬁts the learned binary codes, an efﬁcient GraphCut-based block search method is also proposed to solve large-scale inference.”
Learning Visual Semantic Relationships for Efficient Visual Retrieval (2015, methodology): “We introduce these techniques in the following part.”
How should we evaluate supervised hashing? (2016, methodology): “Following this work, different techniques use both the similarity matrix and the feature space: semi-supervised hashing [6], supervised hashing with kernels (KSH) [7], Semantic Hashing [8], Minimal Loss Hashing [9], fast supervised hashing [10].”
Unsupervised Semantic-Preserving Adversarial Hashing for Image Search (2019, methodology): “Representative supervised hashing methods include minimal loss hashing (MLH) [50], kernel-based supervised hashing (KSH) [23], adaptive hashing (AH) [51], and fast supervised hashing (FashHash) [52].”
Binary Generative Adversarial Networks for Image Retrieval (2017, methodology): “Supervised hashing is designed to generate the binary codes based on predeﬁned labels [8, 27, 40].”
Hashing for Similarity Search: A Survey (2014, methodology): “An instance algorithm [76] uses an efficient GraphCut based block search method for inferring binary codes for large databases and trains boosted decision trees fit the binary codes.”
Deep Supervised Discrete Hashing (2017, methodology): “Supervised hashing methods include SPLH [15], KSH [12], FastH [10], LFH [22], and SDH [14].”
Feature Learning Based Deep Supervised Hashing with Pairwise Labels (2015, methodology): “Representative pairwise label based methods include sequential projection learning for hashing (SPLH) [Wang et al., 2010], minimal loss hashing (MLH) [Norouzi and Fleet, 2011], supervised hashing with kernels (KSH) [Liu et al., 2012], two-step hashing (TSH) [Lin et al., 2013], fast supervised hashin”
Supervised Discrete Hashing (2015, methodology): “The similar idea was also adopted in [17,18,39].”
Unsupervised Deep Hashing with Similarity-Adaptive and Discrete Optimization (2018, methodology): “To address the above problem, a few efforts have recently been devoted to developing effective discrete optimization methods for the hashing problem [8], [22], [29], [37].”
Pairwise Teacher-Student Network for Semi-Supervised Hashing (2019, methodology): “Pairwise losses is widely used for solving (deep) supervised hashing algorithm with pairwise similarity as supervision [18, 16, 17, 3, 15, 31].”
Learning in high-dimensional multimedia data: the state of the art (2015, background): “64 bits 128 bits BRE [44] High low SSH [92] low low ITQ [23] fair fair KSH [53] High fair FastHash [50] High There are also some further developments extended from the standard hashing algorithms: Multiple Feature Hashing (MFH) [81] learns a group of hash functions to generate binary codes for multi”
A Survey on Learning to Hash (2016, methodology): “The second one is a two-step scheme [76], [77] with its extension to alternative optimization [32]: optimize the binary codes without considering the hash function, followed by estimating the function parame-”