Towards Optimal Discrete Online Hashing with Balanced Similarity

Mingbao Lin, Rongrong Ji, Hong Liu, Xiaoshuai Sun, Yongjian Wu, Yunsheng Wu

Abstract When facing large-scale image datasets, online hashing serves as a promising solution for online retrieval and prediction tasks. It encodes the online streaming data into compact binary codes, and simultaneously updates the hash functions to renew codes of the existing dataset. To this end, the existing methods update hash functions solely based on the new data batch, without investigating the correlation between such new data and the existing dataset. In addition, existing works update the hash functions using a relaxation process in its corresponding approximated continuous space. And it remains as an open problem to directly apply discrete optimizations in online hashing. In this paper, we propose a novel supervised online hashing method, termed Balanced Similarity for Online Discrete Hashing (BSODH), to solve the above problems in a unified framework. BSODH employs a well-designed hashing algorithm to preserve the similarity between the streaming data and the existing dataset via an asymmetric graph regularization. We further identify the "data-imbalance" problem brought by the constructed asymmetric graph, which restricts the application of discrete optimization in our problem. Therefore, a novel balanced similarity is further proposed, which uses two equilibrium factors to balance the similar and dissimilar weights and eventually enables the usage of discrete optimizations. Extensive experiments conducted on three widely-used benchmarks demonstrate the advantages of the proposed method over the state-of-the-art methods.

Introduction

In large-scale image retrieval, hashing is a critical technique that transforms high-dimensional images into compact binary codes. This transformation enables efficient search and significantly reduces storage requirements. Online Hashing (OH) adapts this process for streaming data, updating hash functions as new information arrives. However, current OH methods suffer from two primary limitations: an "updating imbalance" where models ignore the relationship between new batches and the existing database, and "optimization inefficiency" caused by continuous relaxation during training, which leads to high quantization errors.

Methodology: Balanced Similarity for Online Discrete Hashing (BSODH)

To address these challenges, we propose BSODH, which integrates three core innovations:

Asymmetric Graph Regularization

Unlike traditional methods that treat new data batches in isolation, BSODH constructs an asymmetric graph to preserve the similarity between incoming streaming data and the existing dataset. This ensures that the global structure of the database is maintained even as it grows.

Overview of the BSODH framework illustrating the asymmetric graph regularization and similarity preservation between new data and the existing dataset.

Balanced Similarity Matrix

The asymmetric graph often introduces a "data-imbalance" problem, where dissimilar pairs vastly outnumber similar ones. This imbalance can lead to "consistent codes," where the model assigns identical hash bits to different items, rendering the retrieval system ineffective. We introduce a balanced similarity matrix using two equilibrium factors, $\eta_s$ and $\eta_d$, to weight similar pairs more heavily. This prevents the optimization from being dominated by dissimilar pairs and ensures discriminative code learning.

Discrete Optimization

BSODH moves away from continuous relaxation by employing a customized discrete optimization algorithm. Using a row-by-row iterative update rule inspired by Discrete Cyclic Coordinate descent, the model solves for binary bits directly. This approach minimizes quantization error and converges extremely quickly—often in just one or two iterations—making it highly suitable for online applications.

Experimental Evaluation

We evaluated BSODH on three benchmark datasets: CIFAR-10, Places205, and MNIST.

Key Results

BSODH consistently outperforms state-of-the-art methods such as MIHash and OSH across various metrics.

Precision performance comparison across CIFAR-10, Places205, and MNIST datasets, showing BSODH (red diamonds) consistently outperforming other methods.

On CIFAR-10, BSODH achieved a mean Average Precision (mAP) of 0.711 at 128 bits, compared to 0.664 for MIHash. The most significant gains were observed in Precision within Hamming Radius (Precision@H2), where BSODH showed a 29.97% improvement over the next best method on CIFAR-10.

Conclusion

BSODH provides a robust framework for online hashing by addressing data imbalance and optimization inefficiencies. By directly optimizing discrete codes and balancing similarity weights, it achieves superior retrieval accuracy and fast convergence. Future work will explore integrating this discrete optimization approach with deep neural networks and adapting the framework for class-incremental learning scenarios.

Summary updated

Abstract

When facing large-scale image datasets, online hashing serves as a promising solution for online retrieval and prediction tasks. It encodes the online streaming data into compact binary codes, and simultaneously updates the hash functions to renew codes of the existing dataset. To this end, the existing methods update hash functions solely based on the new data batch, without investigating the correlation between such new data and the existing dataset. In addition, existing works update the hash functions using a relaxation process in its corresponding approximated continuous space. And it remains as an open problem to directly apply discrete optimizations in online hashing. In this paper, we propose a novel supervised online hashing method, termed Balanced Similarity for Online Discrete Hashing (BSODH), to solve the above problems in a unified framework. BSODH employs a well-designed hashing algorithm to preserve the similarity between the streaming data and the existing dataset via an asymmetric graph regularization. We further identify the "data-imbalance" problem brought by the constructed asymmetric graph, which restricts the application of discrete optimization in our problem. Therefore, a novel balanced similarity is further proposed, which uses two equilibrium factors to balance the similar and dissimilar weights and eventually enables the usage of discrete optimizations. Extensive experiments conducted on three widely-used benchmarks demonstrate the advantages of the proposed method over the state-of-the-art methods.
BibTeX
@inproceedings{lin2019towards,
  author = {Mingbao Lin and Rongrong Ji and Hong Liu and Xiaoshuai Sun and Yongjian Wu and Yunsheng Wu},
  title = {{Towards Optimal Discrete Online Hashing with Balanced Similarity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33018722},
}
Figure