Abstract
We present a new method for Product Quantization (PQ)
based approximated nearest neighbor search (ANN) in high dimensional spaces. Specifically, we first propose a quantization
scheme for the codebook of coarse quantizer, product quantizer,
and rotation matrix, to reduce the cost of accessing these codebooks. Our approach also combines a highly parallel k-selection
method, which can be fused with the distance calculation to reduce the memory overhead. We implement the proposed method
on Intel HARPv2 platform using OpenCL-FPGA. The proposed
method significantly outperforms state-of-the-art methods on
CPU and GPU for high dimensional nearest neighbor queries
on billion-scale datasets in terms of query time and accuracy
regardless of the batch size. To our best knowledge, this is the
first work to demonstrate FPGA performance superior to CPU
and GPU on high-dimensional, large-scale ANN datasets