litlas
ログインアカウント作成

Billion-Scale Similarity Search with GPUs

著者: Jeff Johnson, Matthijs Douze, Hervé Jégou - IEEE Transactions on Big Data 2019 被引用: 846

Similarity search finds application in database systems handling complex data such as images or videos, which are typically represented by high-dimensional features and require specific indexing structures. This paper tackles the problem of better utilizing GPUs for this task. While GPUs excel at data parallel tasks such as distance computation, prior approaches in this domain are bottlenecked by algorithms that expose less parallelism, such as k -min selection, or make poor use of the memory hierarchy. We propose a novel design for k -selection. We apply it in different similarity search scenarios, by optimizing brute-force, approximate and compressed-domain search based on product quantization. In all these setups, we outperform the state of the art by large margins. Our implementation operates at up to 55 percent of theoretical peak performance, enabling a nearest neighbor implementation that is 8.5 × faster than prior GPU state of the art. It enables the construction of a high accuracy k -NN graph on 95 million images from the Yfcc100M dataset in 35 minutes, and of a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs. We have open-sourced our approach for the sake of comparison and reproducibility.

Product Quantization forNearest Neighbor SearchProduct Quantization for Nearest Neighbor SearchSearching in one billionvectors: Re-rank with…Searching in one billion vectors: Re-rank with source codingThe Inverted Multi-IndexThe Inverted Multi-IndexCartesian K-MeansCartesian K-MeansK-Means Hashing: AnAffinity-Preserving…K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact CodesLocally OptimizedProduct Quantization fo…Locally Optimized Product Quantization for Approximate Nearest Neighbor SearchOptimized ProductQuantizationOptimized Product QuantizationCache locality is notenough: High-Performanc…Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast ScanEfficient Indexing ofBillion-Scale Datasets…Efficient Indexing of Billion-Scale Datasets of Deep DescriptorsPolysemous CodesPolysemous CodesDeep Residual Learningfor Image RecognitionDeep Residual Learning for Image RecognitionEfficient Large-ScaleApproximate Nearest…Efficient Large-Scale Approximate Nearest Neighbor Search on the GPU[Invited Paper] A Surveyof Product Quantization[Invited Paper] A Survey of Product QuantizationPQTable: NonexhaustiveFast Search for…PQTable: Nonexhaustive Fast Search for Product-Quantized Codes Using Hash TablesPQTable: Non-exhaustiveFast Search for…PQTable: Non-exhaustive Fast Search for Product-quantized Codes using Hash TablesLearning Tree-based DeepModel for Recommender…Learning Tree-based Deep Model for Recommender SystemsWord Translation WithoutParallel DataWord Translation Without Parallel DataHierarchical NeuralStory GenerationHierarchical Neural Story GenerationSO-Net: Self-OrganizingNetwork for Point Cloud…SO-Net: Self-Organizing Network for Point Cloud AnalysisA Probabilistic Approachto Cross-Region…A Probabilistic Approach to Cross-Region Matching-Based Image RetrievalFast Approximate NearestNeighbor Search With Th…Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out GraphGPU acceleratedt-distributed stochasti…GPU accelerated t-distributed stochastic neighbor embeddingAccelerating 3D DeepLearning with PyTorch3DAccelerating 3D Deep Learning with PyTorch3DDeep Learningapplications for…Deep Learning applications for COVID-19Billion-Scale SimilaritySearch with GPUsBillion-Scale Similarity Search with GPUs過去の参考文献中心の論文この論文を引用する論文古い新しい

ノードをクリックするとフォーカスを固定、空白をクリックすると本論文に戻ります。ホバーで一時的にプレビューできます。各ノードのページはタイトルから開けます。