Unsupervised Online Hashing with Multi-Bit Quantization

Zhenyu Weng, Yuesheng Zhu; Proceedings of the Asian Conference on Computer Vision (ACCV), 2022, pp. 3911-3926

Online hashing methods aim to update hash functions with newly arriving data streams, which can process large-scale data online. To this end, most existing methods update projection functions online and adopt a single-bit quantization strategy that quantizes each projected component with one bit. However, single-bit quantization results in large information loss in the quantization process and thus cannot preserve the similarity information of original data well. In this paper, we propose a novel unsupervised online hashing method with multi-bit quantization towards solving this problem, which consists of online data sketching and online quantizer learning. By maintaining a small-size data sketch to preserve the streaming data information, an orthogonal transformation is learned from the data sketch to make the components of the streaming data independent. Then, an optimal quantizer is learned to adaptively quantize each component with multiple bits by modeling the data distribution. Therefore, our method can quantize each component with multiple bits rather than one bit to better preserve the data similarity online. The experiments show that our method can achieve better search accuracy than the relevant online methods for approximate nearest neighbor search.