Approximate Nearest Neighbor Search by Residual Vector Quantization

By Yongjian Chen, Tao Guan, Cheng Wang. 2010

178 citations recorded by the source corpus.

A recently proposed product quantization method is efficient for large scale approximate nearest neighbor search, however, its performance on unstructured vectors is limited. This paper introduces residual vector quantization based approaches that are appropriate for unstructured vectors. Database vectors are quantized by residual vector quantizer. The reproductions are represented by short codes composed of their quantization indices. Euclidean distance between query vector and database vector is approximated by asymmetric distance, i.e., the distance between the query vector and the reproduction of the database vector. An efficient exhaustive search approach is proposed by fast computing the asymmetric distance. A straight forward non-exhaustive search approach is proposed for large scale search. Our approaches are compared to two state-of-the-art methods, spectral hashing and product quantization, on both structured and unstructured datasets. Results show that our approaches obtain the best results in terms of the trade-off between search quality and memory usage.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Compressing Deep Convolutional Networks using Vector Quantization (2014, methodology): “In this work, instead of the traditional matrix factorization methods considered in (Denton et al., 2014; Jaderberg et al., 2014), we mainly consider a series of information theoretical vector quantization methods (Jegou et al., 2011; Chen et al., 2010) for compressing dense connected layers.”
Dynamic Capacity Networks (2015, background): “, 2014) and quantization schemes (Chen et al., 2010; Jégou et al., 2011; Gong et al., 2014) take the same computational shortcuts for all instances of the data.”
Polysemous Codes (2016, methodology): “…general formulation, good trade-oﬀs are achieved by residual quantizers [11,31], which are routinely used in the non-exhaustive PQ variant [28] to reduce the quantization loss by encoding the residual error vector instead of the original vector, but also as a coding strategy on its own [13,39,1].”
The Faiss Library (2024, unknown): “The residual quantizer ( ResidualQuantizer ) proceeds sequentially, by encoding the difference (residual) of the vector to encode and the one that is reconstructed by the previous sub-quantizers [62].”
Hyper-Sphere Quantization: Communication-Efficient SGD for Federated Learning (2019, methodology): “Inspired by vector quantization techniques (Chen et al., 2010; Ge et al., 2013; Jegou et al., 2011; Wu et al., 2017), HSQ adopts a paradigm that is fundamentally different from existing gradient compression algorithms (Bernstein et al., 2018; Wen et al., 2017).”
Efficient Indexing of Billion-Scale Datasets of Deep Descriptors (2016, methodology): “[8] also introduces the IVFRVQ system that allows to perform non-exhaustive search.”
Compression of Deep Neural Networks on the Fly (2015, methodology): “In their work, instead of the traditional matrix factorization methods considered in [12, 13], they consider series of information theoretical vector quantization methods [15, 16] for compressing dense connected layers.”
A Survey of Model Architectures in Information Retrieval (2025, unknown): “Zeng et al. (2024) utilized the residual quantization technique (Chen et al., 2010) to construct hierarchical DocIDs and achieved comparable performance to dense retrievers on MS MARCO dataset.”