18269

Efficient Large-scale Approximate Nearest Neighbor Search on OpenCL FPGA

Jialiang Zhang, Soroosh Khoram, Jing Li
UW-Madison
The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4924-4932, 2018

@inproceedings{zhang2018efficient,

   title={Efficient Large-Scale Approximate Nearest Neighbor Search on OpenCL FPGA},

   author={Zhang, Jialiang and Khoram, Soroosh and Li, Jing},

   booktitle={Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition},

   pages={4924–4932},

   year={2018}

}

Download Download (PDF)   View View   Source Source   

402

views

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.
Rating: 2.0/5. From 2 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2018 hgpu.org

All rights belong to the respective authors

Contact us: