To retrieve images or documents instantly from massive databases, modern search systems map high-dimensional data into compact binary hash codes. In supervised hashing, the goal is to ensure that semantically similar items map to nearby binary codes in the Hamming space.
Traditionally, this is achieved by optimizing a loss function based on pairwise or triplet relationships: if item $i$ and item $j$ share a semantic label, their hash codes should have a small Hamming distance. However, this formulation introduces a fundamental scalability bottleneck. For a dataset of $N$ samples, computing or storing the pairwise similarity matrix requires $O(N^2)$ time and memory complexity. When scaling to million-scale datasets, this quadratic explosion becomes computationally prohibitive.
To bypass this bottleneck, a powerful paradigm has emerged: linear-time supervised hashing. By restructuring how semantic information guides the network, these methods achieve linear complexity ($O(N)$), allowing supervised models to scale efficiently to millions of items.
Point-wise Supervision: Hashing as Classification
The most direct way to break the quadratic bottleneck is to eliminate pairwise comparisons entirely. Instead of evaluating how two instances relate to each other, point-wise supervised hashing treats hash code generation as a localized classification or regression task.
Kevin Lin et al. demonstrated this shift in Deep learning of binary hash codes for fast image retrieval, showing that binary representations can be learned simultaneously with image features by framing the objective around point-wise classification. By utilizing individual image labels rather than pairs, the training complexity drops from quadratic to linear relative to the dataset size.
This allows deep hashing models to be trained via standard mini-batch stochastic gradient descent (SGD), exactly like traditional image classifiers. As Dang-Khoa Le Tan et al. noted in Supervised Hashing with End-to-End Binary Deep Neural Network, mini-batch training bypasses the need to load a massive global similarity matrix into memory, making training on millions of images feasible on standard hardware.
Pairwise Hashing (Quadratic: O(N²))
[Image 1] <---> [Image 2]
^ ^
| |
v v
[Image 4] <---> [Image 3]
Point-wise Hashing (Linear: O(N))
[Image 1] ---> [Fixed Semantic Target / Class Prototype]
[Image 2] ---> [Fixed Semantic Target / Class Prototype]
[Image 3] ---> [Fixed Semantic Target / Class Prototype]
But why does this preserve similarity if the network never explicitly compares pairs? The intuition lies in the shared target space. In Natural Supervised Hashing, the authors proposed using semantic label vectors directly as targets for binary code generation. Similarly, Huei‐Fang Yang et al. introduced Supervised Semantics-preserving Deep Hashing (SSDH) in Supervised Learning of Semantics-Preserving Hash via Deep Convolutional Neural Networks, which maps individual images to a classification layer that implicitly clusters similar items together.
If two images share the same semantic labels, a well-optimized point-wise classification loss—such as the structured loss utilized by Han Sun et al. in A Novel Semantics-Preserving Hashing for Fine-Grained Image Retrieval—forces their latent representations into the same region of the embedding space. Consequently, their thresholded binary outputs naturally align, preserving pairwise similarity implicitly without ever computing it explicitly.
Class Centers and Proxies
When dealing with complex datasets or multi-label scenarios, mapping directly to a simple classification layer can cause boundary overlap issues. To solve this, researchers introduced class-level abstractions that sit between individual instances and global similarity matrices.
Instead of comparing an instance to every other instance, models can compare an instance to a set of class centers or proxies. Ming Zhang et al. leveraged this in Improved Deep Classwise Hashing With Centers Similarity Learning for Image Retrieval by simultaneously learning binary hash codes and discriminative class centers. By optimizing codes relative to these centers, the computational complexity scales with the number of classes rather than the number of data points.
For massive datasets with hundreds of thousands of categories, even class-pairwise operations can become heavy. To address this, Yu Liang et al. proposed Unleashing the Full Potential of Product Quantization for Large-Scale Image Retrieval, which uses class-level supervision with fixed quantization targets to eliminate large similarity matrix calculations entirely. In multi-label remote sensing applications, Xin Sui et al. developed Deep semantic-dependence proxy hashing with global and spatial informative embedding for multi-label remote sensing image retrieval, using class-representative proxies to reduce training complexity from quadratic to linear relative to the number of classes.
This paradigm shift is mathematically clean: if a dataset has $N$ instances and $C$ classes (where $C \ll N$), transitioning from instance-level matrices to class-level matrices reduces memory complexity from $O(N^2)$ to $O(C^2)$ or $O(NC)$. As explained by Long-Kai Huang et al. in Class-Wise Supervised Hashing with Label Embedding and Active Bits, learning "code-prototypes" for each class allows the model to utilize the entire labeled dataset for training without encountering the memory bottlenecks associated with large-scale pairwise comparisons.
Matrix Decomposition and Asymmetric Optimization
Another powerful strategy to achieve linear-time complexity involves decomposing or sampling the similarity matrix rather than discarding it entirely.
One prominent approach is column sampling or anchor-based approximation. Instead of computing the full $N \times N$ matrix, the model samples a small subset of columns representing "anchors" or landmark points. Wang-Cheng Kang et al. utilized this in Column Sampling Based Discrete Supervised Hashing (COSDISH), demonstrating that column sampling allows supervised hashing to scale linearly with the number of data points while maintaining a low memory footprint.
Similarly, Qing-Yuan Jiang et al. showed in Deep Discrete Supervised Hashing that anchor-based sampling can effectively approximate global similarity relationships without sacrificing retrieval performance. In a similar vein, the fully Bayesian framework proposed by Zihao Hu et al. in Bayesian Supervised Hashing employs a stochastic learning variant that samples columns of the similarity matrix to achieve linear-time complexity while capturing essential semantic relationships.
Alternatively, the quadratic bottleneck can be bypassed by changing the architectural symmetry of the network. In Asymmetric Deep Supervised Hashing, Qing-Yuan Jiang et al. decoupled the query hash function from the database code generation:
$$\text{Symmetric Hashing Loss} \propto \sum_{i,j} \mathcal{L}(H(x_i), H(x_j)) \quad [O(N^2)]$$ $$\text{Asymmetric Hashing Loss} \propto \sum_{i,j} \mathcal{L}(H(x_i), B_j) \quad [O(N)]$$
By learning a deep neural network ($H$) only for query points while directly optimizing the database hash codes ($B$), they reduced the computational complexity from quadratic to linear. This asymmetry allows the model to train on the full extent of a large-scale database, avoiding the performance degradation that occurs when models are forced to train on small data subsets due to memory constraints.
Decomposing Similarity Objectives
The principle of linear-time scaling also applies to multimodal and discrete optimization frameworks. For instance, in cross-modal retrieval (e.g., matching text to images), Dongqing Zhang et al. demonstrated in Large-Scale Supervised Multimodal Hashing with Semantic Correlation Maximization that supervised hashing achieves linear-time complexity when similarity objectives are decomposed into local operations. This allows models to utilize entire large-scale datasets for training without performance loss.
Furthermore, optimizing a flexible target matrix alongside binary codes can lead to significant training speed improvements. As shown by Jie Gui et al. in Supervised Hashing with Relaxation, this flexibility makes discrete optimization orders of magnitude faster than traditional kernel-based methods.
In cross-modal settings, Peng-Fei Zhang et al. designed a framework with linear computational complexity in Semantics-Reconstructing Hashing for Cross-Modal Retrieval by reconstructing semantic representations directly from labels, completely avoiding the construction of full pairwise similarity matrices.
Beyond Deep Learning: Alternative Non-Linear Functions
While deep neural networks are highly effective, linear-time supervised hashing principles also extend to other efficient non-linear models, such as decision trees and kernel methods, which offer unique computational advantages.
For instance, Guosheng Lin et al. introduced FastHash in Supervised Hashing Using Graph Cuts and Boosted Decision Trees, which decouples binary code inference from hash function learning. By utilizing gradient-boosted decision tree ensembles instead of deep networks or kernel-based models, they achieved non-linear hashing with significantly lower training and inference costs, enabling scaling to millions of high-dimensional samples.
In another direction, Yage Wang et al. combined DenseNet with Supervised Kernel Hashing (KSH) in Image Hash retrieval with DenseNet, balancing computational speed and storage efficiency by minimizing projection errors.
Furthermore, as highlighted by Thiago Ramos et al. in BlockBoost: Scalable and Efficient Blocking through Boosting, these alternative learned hashing frameworks can process millions of entries in minutes on consumer-grade hardware, bypassing the severe memory bottlenecks and prohibitive training times that often plague massive deep learning architectures.
Summary
By replacing instance-to-instance comparisons with point-wise classification targets, class-level proxies, or sampled anchor columns, linear-time supervised hashing transforms a global, combinatorially explosive optimization problem into a series of localized, independent operations. This structural shift allows retrieval systems to fully harness the semantic power of massive datasets without being crushed by the weight of quadratic complexity.
Key Foundational Work
Deep learning of binary hash codes for fast image retrieval (2015) — contributed 2 concept elements to this direction.
Large-Scale Supervised Multimodal Hashing with Semantic Correlation Maximization (2014) — contributed 1 concept elements to this direction.
Supervised Hashing Using Graph Cuts and Boosted Decision Trees. (2015) — contributed 1 concept elements to this direction.