Efficient Large-scale Approximate Nearest Neighbor Search on the GPU

Abstract

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.

Cited by in corpus (11)

• Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs
• GGNN: Graph-based GPU Nearest Neighbor Search
• Vector and Line Quantization for Billion-scale Similarity Search on GPUs
• Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal
• LOVO: Efficient Complex Object Query in Large-Scale Video Datasets
• Accurate and Efficient Similarity Search for Large Scale Face Recognition
• Recurrent Binary Embedding for GPU-Enabled Exhaustive Retrieval from Billion-Scale Semantic Vectors
• Large-Scale Approximate k-NN Graph Construction on GPU
• Learn to Cluster Faces via Pairwise Classification
• PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash Tables
• Reconfigurable Inverted Index