Efficient Large-Scale Approximate Nearest Neighbor Search on the GPU
By Patrick Wieschollek, Oliver Wang, Alexander Sorkine-Hornung, Hendrik P. A. Lensch. 2016
66 citations recorded by the source corpus.
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.
Subfields: Computer Vision and Pattern Recognition, Media Technology, Information Retrieval & Search
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Vision and Pattern Recognition
- Herv'e J'egou
- Luc Van Gool
- Andrew Zisserman
- Cordelia Schmid
- Matthijs Douze
- Dacheng Tao
- Trevor Darrell
- Yi Yang
In Media Technology
- Herv'e J'egou
- Matthijs Douze
- Jeff Johnson
- Florent Perronnin
- Victor S. Lempitsky
- Artem Babenko
- Jingdong Wang
- Kaiming He
In Information Retrieval & Search
- Herv'e J'egou
- Matthijs Douze
- Jeff Johnson
- Dmitry A. Yashunin
- Yury Malkov
- Ondřej Chum
- Florent Perronnin
- Victor S. Lempitsky
Citations in the corpus
- Billion-Scale Similarity Search with GPUs (2017, methodology): “Details on distance computations and articulation with k-selection are the key to understanding why this method can outperform more recent GPUcompliant approximate nearest neighbor strategies [47].”
- Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, background): “(LSH) [8], [9] and product quantization (PQ) [10], [11], [12], [13], [14], [15], [16], [17].”