Fast Supervised Hashing with Decision Trees for High-Dimensional Data

Abstract

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.

Appearing in Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2014, Ohio, USA

References in corpus (1)

• Learning Hash Functions Using Column Generation

Cited by in corpus (57)

• Sketch-based Manga Retrieval using Manga109 Dataset
• Supervised Learning of Semantics-Preserving Hash via Deep Convolutional Neural Networks
• SSDH: Semi-supervised Deep Hashing for Large Scale Image Retrieval
• Deep Supervised Discrete Hashing
• Hashing on Nonlinear Manifolds
• Feature Learning based Deep Supervised Hashing with Pairwise Labels
• Deep Discrete Supervised Hashing
• Supervised Hashing Using Graph Cuts and Boosted Decision Trees
• Online Hashing
• Unsupervised Deep Cross-modality Spectral Hashing
• Hashing with binary autoencoders
• Simultaneous Feature Aggregating and Hashing for Compact Binary Code Learning
• Optimizing affinity-based binary hashing using auxiliary coordinates
• Semantic Cluster Unary Loss for Efficient Deep Hashing
• Learning in High-Dimensional Multimedia Data: The State of the Art
• End-to-end Network for Twitter Geolocation Prediction and Hashing
• Discrete Hashing with Deep Neural Network
• Asymmetric Deep Supervised Hashing
• Making Online Sketching Hashing Even Faster
• Efficient Training of Very Deep Neural Networks for Supervised Hashing
• Optimizing Ranking Measures for Compact Binary Code Learning
• Probability Weighted Compact Feature for Domain Adaptive Retrieval
• Unsupervised Semantic Deep Hashing
• SADIH: Semantic-Aware DIscrete Hashing
• Random Forests Can Hash
• Push for Quantization: Deep Fisher Hashing
• Dual Asymmetric Deep Hashing Learning
• Simultaneous Compression and Quantization: A Joint Approach for Efficient Unsupervised Hashing
• Deep Momentum Uncertainty Hashing
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Fast Large-Scale Discrete Optimization Based on Principal Coordinate Descent
• Neurons Merging Layer: Towards Progressive Redundancy Reduction for Deep Supervised Hashing
• Deep Supervised Hashing leveraging Quadratic Spherical Mutual Information for Content-based Image Retrieval
• Deep Class-Wise Hashing: Semantics-Preserving Hashing via Class-wise Loss
• Hashing as Tie-Aware Learning to Rank
• Optimal Projection Guided Transfer Hashing for Image Retrieval
• Fast Supervised Discrete Hashing
• End-to-end Binary Representation Learning via Direct Binary Embedding
• Fast Metric Learning For Deep Neural Networks
• Deep Supervised Hashing with Triplet Labels
• Constructing Binary Descriptors with a Stochastic Hill Climbing Search
• Deep Reinforcement Learning with Label Embedding Reward for Supervised Image Hashing
• Supervised Discrete Hashing with Relaxation
• Scalable Gaussian Processes for Supervised Hashing
• Learning Binary Codes and Binary Weights for Efficient Classification
• Structured Learning of Binary Codes with Column Generation
• Online Supervised Hashing for Ever-Growing Datasets
• Multi-Merge Budget Maintenance for Stochastic Gradient Descent SVM Training
• Hashing with Binary Matrix Pursuit
• Video Segment Copy Detection Using Memory Constrained Hierarchical Batch-Normalized LSTM Autoencoder
• Global Hashing System for Fast Image Search
• Regularizing Deep Hashing Networks Using GAN Generated Fake Images
• Speeding Up Budgeted Stochastic Gradient Descent SVM Training with Precomputed Golden Section Search
• ForestHash: Semantic Hashing With Shallow Random Forests and Tiny Convolutional Networks
• Learning Hash Function through Codewords
• A Scalable Optimization Mechanism for Pairwise based Discrete Hashing
• Binary Hashing with Semidefinite Relaxation and Augmented Lagrangian