Scale balance for prototype-based binary quantization. (October 2020)

• Record Type: Journal Article
• Authors: Li, Zhiyang; Qu, Wenyu; Cao, Yuan; Qi, Heng; Stojmenovic, Milos; Hu, Jia
• Is Part Of: Pattern recognition. Volume 106(2020:Oct.)
• Publication Date: 2020-10
• Subjects: Approximate nearest neighbor search -- High-dimensional vectors -- Prototype-based binary quantization; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2020.107409
• Languages: English
• ISSNs: 0031-3203

Abstract

Abstract: Nowadays, prototype-based binary quantization (PBQ) is a promising solution for the approximate nearest neighbor search problem, which simultaneously preserves the affinity structures of prototypes in both Euclidean space as well as those of their codes in binary space. To learn longer binary codes, space decomposition based on product quantization is usually adopted. In practice, we find that the scale between Euclidean distance and Hamming distance usually varies across these decomposed subspaces, which degenerates the performance of PBQ based methods. We make an attempt to balance the scale of these subspaces via a joint optimization problem in the classic PBQ model, and present both an iterative and alternate algorithm for optimization. We conducted experiments on 6 public databases, and demonstrated that our scale balancing based methods SKMH and SABQ outperform state-of-the-art hashing methods including popular prototype-based binary quantization methods, with up to 81.62% relative performance gains when learning 256-bit binary codes.