Optimized high order product quantization for approximate nearest neighbors search

作者:Linhao Li, Qinghua Hu

摘要

Product quantization is now considered as an effective approach to solve the approximate nearest neighbor (ANN) search. A collection of derivative algorithms have been developed. However, the current techniques ignore the intrinsic high order structures of data, which usually contain helpful information for improving the computational precision. In this paper, aiming at the complex structure of high order data, we design an optimized technique, called optimized high order product quantization (O-HOPQ) for ANN search. In O-HOPQ, we incorporate the high order structures of the data into the process of designing a more effective subspace decomposition way. As a result, spatial adjacent elements in the high order data space are grouped into the same sub-space. Then, O-HOPQ generates its spatial structured code-book, by optimizing the quantization distortion. Starting from the structured codebook, the global optimum quantizers can be obtained effectively and efficiently. Experimental results show that appropriate utilization of the potential information that exists in the complex structure of high order data will result in significant improvements to the performance of the product quantizers. Besides, the high order structure based approaches are effective to the scenario where the data have intrinsic complex structures.

论文关键词:product quantization, high order structured data, tensor theory, approximate nearest neighbor search

论文评审过程:

论文官网地址:https://doi.org/10.1007/s11704-018-7049-5