Improved 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 scheme to lower the quantization error stage by stage. However, there are two major limitations for RVQ when applied to on high-dimensional approximate nearest neighbor search: 1. The performance gain diminishes quickly with added stages. 2. Encoding a vector with RVQ is actually NP-hard. In this paper, we propose an improved residual vector quantization (IRVQ) method, our IRVQ learns codebook with a hybrid method of subspace clustering and warm-started k-means on each stage to prevent performance gain from dropping, and uses a multi-path encoding scheme to encode a vector with lower distortion. Experimental results on the benchmark datasets show that our method gives substantially improves RVQ and delivers better performance compared to the state-of-the-art.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringQuantizationVocal Bursts Intensity PredictionSimilar Papers 제목 키워드 기반
RQ-MoE: Residual Quantization via Mixture of Experts for Efficient Input-Dependent Vector Compression
Vector quantization is a fundamental tool for compressing high-dimensional embeddings, yet existing multi-codebook methods rely on static codebooks that limit expressiveness under heterogeneous data geometry. While recen…
Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks
Vector quantization is a fundamental technique for compression and large-scale nearest neighbor search. For high-accuracy operating points, multi-codebook quantization associates data vectors with one element from each o…
DecoderQuantizationLearning Better Encoding for Approximate Nearest Neighbor Search with Dictionary Annealing
We introduce a novel dictionary optimization method for high-dimensional vector quantization employed in approximate nearest neighbor (ANN) search. Vector quantization methods first seek a series of dictionaries, then ap…
Dictionary LearningGPUQuantizationMultiscale Quantization for Fast Similarity Search
We propose a multiscale quantization approach for fast similarity search on large, high-dimensional datasets. The key insight of the approach is that quantization methods, in particular product quantization, perform poor…
QuantizationProduct Quantizer Aware Inverted Index for Scalable Nearest Neighbor Search
The inverted index is one of the most commonly used structures for non-exhaustive nearest neighbor search on large-scale datasets. It allows a significant factor of acceleration by a reduced number of distance comput…
Quantization