Low-Precision Quantization for Efficient Nearest Neighbor Search
Fast k-Nearest Neighbor search over real-valued vector spaces (KNN) is an important algorithmic task for information retrieval and recommendation systems. We present a method for using reduced precision to represent vectors through quantized integer values, enabling both a reduction in the memory overhead of indexing these vectors and faster distance computations at query time. While most traditional quantization techniques focus on minimizing the reconstruction error between a point and its uncompressed counterpart, we focus instead on preserving the behavior of the underlying distance metric. Furthermore, our quantization approach is applied at the implementation level and can be combined with existing KNN algorithms. Our experiments on both open source and proprietary datasets across multiple popular KNN frameworks validate that quantized distance metrics can reduce memory by 60% and improve query throughput by 30%, while incurring only a 2% reduction in recall.
Code (0)
등록된 구현이 없습니다.
Tasks
Information RetrievalQuantizationRecommendation SystemsRetrievalSimilar Papers 제목 키워드 기반
Interleaved Composite Quantization for High-Dimensional Similarity Search
Similarity search retrieves the nearest neighbors of a query vector from a dataset of high-dimensional vectors. As the size of the dataset grows, the cost of performing the distance computations needed to implement a que…
QuantizationVocal Bursts Intensity PredictionFast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs
We explore the use of GPU for accelerating large scale nearest neighbor search and we propose a fast vector-quantization-based exhaustive nearest neighbor search algorithm that can achieve high accuracy without any index…
GPUQuantizationTransformed Residual Quantization for Approximate Nearest Neighbor Search
The success of product quantization (PQ) for fast nearest neighbor search depends on the exponentially reduced complexities of both storage and computation with respect to the codebook size. Recent efforts have been focu…
QuantizationImproved Residual Vector Quantization for High-dimensional Approximate Nearest Neighbor Search
Quantization methods have been introduced to perform large scale approximate nearest search tasks. Residual Vector Quantization (RVQ) is one of the effective quantization methods. RVQ uses a multi-stage codebook learning…
ClusteringQuantizationVocal Bursts Intensity PredictionExploiting Modern Hardware for High-Dimensional Nearest Neighbor Search
Many multimedia information retrieval or machine learning problems require efficient high-dimensional nearest neighbor search techniques. For instance, multimedia objects (images, music or videos) can be represented by h…
BIG-bench Machine LearningInformation RetrievalQuantizationRetrieval+1