We are very excited to join forces with MLCommons and OctoML.ai! Contact Grigori Fursin for more details!

Efficient Large-scale Approximate Nearest Neighbor Search on the GPU

lib:ea9f0afa622be78b (v1.0.0)

Authors: Patrick Wieschollek,Oliver Wang,Alexander Sorkine-Hornung,Hendrik P. A. Lensch
Where published: CVPR 2016 6
ArXiv: 1702.05911
Document:  PDF  DOI 
Abstract URL: http://arxiv.org/abs/1702.05911v1


We present a new approach for efficient approximate nearest neighbor (ANN) search in high dimensional spaces, extending the idea of Product Quantization. We propose a two-level product and vector quantization tree that reduces the number of vector comparisons required during tree traversal. Our approach also includes a novel highly parallelizable re-ranking method for candidate vectors by efficiently reusing already computed intermediate values. Due to its small memory footprint during traversal, the method lends itself to an efficient, parallel GPU implementation. This Product Quantization Tree (PQT) approach significantly outperforms recent state of the art methods for high dimensional nearest neighbor queries on standard reference datasets. Ours is the first work that demonstrates GPU performance superior to CPU performance on high dimensional, large scale ANN problems in time-critical real-world applications, like loop-closing in videos.

Relevant initiatives  

Related knowledge about this paper Reproduced results (crowd-benchmarking and competitions) Artifact and reproducibility checklists Common formats for research projects and shared artifacts Reproducibility initiatives

Comments  

Please log in to add your comments!
If you notice any inapropriate content that should not be here, please report us as soon as possible and we will try to remove it within 48 hours!