GPGPU Implementation of Nearest Neighbor Search with Product Quantization

A nearest neighbor search with product quantization is a prominent method that achieves a high-precision search with less memory consumption than an exhaustive way. However, in order to accomplish a large size search with a large reference data, the search method have to be accelerated by using parallel systems such as multicore processors and GPGPU (General Purpose computing on GPU) systems. The distance calculation between a query and a reference data is an independent operation that is easily parallelized, but the reduction computation of distances after that is not completely parallel, so this leads to performace degradation. Therefore, in order to maximize a speedup, the adequate parameter selection is required in terms of parallelism. In this paper, the baseline of parallelization of the nearest neighbor search with product quantization is described, and the validity of our approach (Optimistic Search), which utilizes a small number of candidates of nearest neighbors, is discussed with experiments. We also show the effectiveness of pseudo matrix transposition for the sake of the efficient search. In addition, the method for autotuning is proposed and its effectiveness is empirically confirmed.