Optimized residual vector quantization for efficient approximate nearest neighbor search

详细信息    查看全文

• 作者：Liefu Ai ; Junqing Yu ; Zebin Wu ; Yunfeng He ; Tao Guan
• 关键词：Approximate nearest neighbor search ; Vector quantization ; Codebook optimization ; Filtration
• 刊名：Multimedia Systems
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：23
• 期：2
• 页码：169-181
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Multimedia Information Systems; Computer Communication Networks; Operating Systems; Data Storage Representation; Data Encryption; Computer Graphics;
• 出版者：Springer Berlin Heidelberg
• ISSN：1432-1882
• 卷排序：23

文摘

In this paper, an optimized residual vector quantization-based approach is presented for improving the quality of vector quantization and approximate nearest neighbor search. The main contributions are as follows. Based on residual vector quantization (RVQ), a joint optimization process called enhanced RVQ (ERVQ) is introduced. Each stage codebook is iteratively optimized by the others aiming at minimizing the overall quantization errors. Thus, an input vector is approximated by its quantization outputs more accurately. Consequently, the precision of approximate nearest neighbor search is improved. To efficiently find nearest centroids when quantizing vectors, a non-linear vector quantization method is proposed. The vectors are embedded into 2-dimensional space where the lower bounds of Euclidean distances between the vectors and centroids are calculated. The lower bound is used to filter non-nearest centroids for the purpose of reducing computational costs. ERVQ is noticeably optimized in terms of time efficiency on quantizing vectors when combining with this method. To evaluate the accuracy that vectors are approximated by their quantization outputs, an ERVQ-based exhaustive method for approximate nearest neighbor search is implemented. Experimental results on three datasets demonstrate that our approaches outperform the state-of-the-art methods over vector quantization and approximate nearest neighbor search.