Efficient Large-Scale Approximate Nearest Neighbor Search on OpenCL FPGA
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.
Code (0)
등록된 구현이 없습니다.
Tasks
CPUGPUQuantizationSimilar Papers 제목 키워드 기반
LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System
Nearest neighbor search (NNS) has a wide range of applications in information retrieval, computer vision, machine learning, databases, and other areas. Existing state-of-the-art algorithm for nearest neighbor search, Hie…
Information RetrievalPlaying the Game of 2048RetrievalApproximate k-NN Graph Construction: a Generic Online Approach
Nearest neighbor search and k-nearest neighbor graph construction are two fundamental issues arise from many disciplines such as multimedia information retrieval, data-mining and machine learning. They become more and mo…
graph constructionInformation RetrievalRetrievalSubspace Approximation for Approximate Nearest Neighbor Search in NLP
Most natural language processing tasks can be formulated as the approximated nearest neighbor search problem, such as word analogy, document similarity, machine translation. Take the question-answering task as an example…
Machine TranslationQuestion AnsweringRetrievalTensor-Train Point Cloud Compression and Efficient Approximate Nearest-Neighbor Search
Nearest-neighbor search in large vector databases is crucial for various machine learning applications. This paper introduces a novel method using tensor-train (TT) low-rank tensor decomposition to efficiently represent …
Density EstimationOut of Distribution (OOD) DetectionTensor DecompositionEfficient Large-scale Approximate Nearest Neighbor Search on the GPU
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 r…
CPUGPUQuantizationRe-Ranking