Product Quantization for Nearest Neighbor Search
By Herv'e J'egou, Matthijs Douze, Cordelia Schmid. 2011
3,514 citations recorded by the source corpus.
This paper introduces a product quantization-based approach for approximate nearest neighbor search. The idea is to decompose the space into a Cartesian product of low-dimensional subspaces and to quantize each subspace separately. A vector is represented by a short code composed of its subspace quantization indices. The euclidean distance between two vectors can be efficiently estimated from their codes. An asymmetric version increases precision, as it computes the approximate distance between a vector and a code. Experimental results show that our approach searches for nearest neighbors efficiently, in particular in combination with an inverted file system. Results for SIFT and GIST image descriptors show excellent search accuracy, outperforming three state-of-the-art approaches. The scalability of our approach is validated on a data set of two billion vectors.
Subfields: Computer Vision and Pattern Recognition, Media Technology, Information Retrieval & Search
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
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Xiaogang Wang
- Ming-Hsuan Yang
- Yi Yang
- Jitendra Malik
- Andrew Zisserman
In Media Technology
- Jingdong Wang
- Andrew Zisserman
- Yi Yang
- Qi Tian
- Victor S. Lempitsky
- Cordelia Schmid
- Kaiming He
- Josef Sivic
In Information Retrieval & Search
- Herv'e J'egou
- Jingdong Wang
- Matthijs Douze
- Victor S. Lempitsky
- Artem Babenko
- Edouard Grave
- Sebastian Riedel
- Danqi Chen
Citations in the corpus
- Deep Residual Learning for Image Recognition (2015, background): “For vector quantization, encoding residual vectors [17] is shown to be more effective than encoding original vectors.”
- FitNets: Hints for Thin Deep Nets (2014, background): “Other works related to quantization schemes (Chen et al., 2010; J´egou et al., 2011; Gong et al., 2014) aim at reducing storage requirements.”
- Aggregating Local Image Descriptors into Compact Codes (2012, background): “Some authors address the efficiency and memory constraints by using GIST descriptors [16], and by converting them to compact binary vectors [17], [11], [18].”
- Few-shot Learning with Retrieval Augmented Language Models (2022, methodology): “Following Izacard et al. (2020), we explore the effect of Product Quantization (PQ, Jégou et al., 2011), a popular lossy compression technique on Atlas -3B’s accuracy for the 64-shot NQ task at different compression levels.”
- Augmented Language Models: a Survey (2023, methodology): “, 2022) uses product quantisation (Jégou et al., 2011) to reduce the memory footprint of the retriever without sacrificing accuracy in downstream tasks in terms of exact match and recall@50 metrics of Q&A.”
- Large Memory Layers with Product Keys (2019, methodology): “ing time raises several challenges in terms of optimization, because approximate indexes are not accurate in high-dimensional spaces. In our paper, we borrow some ideas from product quantization (PQ) [21]. This is an approximate search technique that maps database vectors into compact codes. However”
- Billion-Scale Similarity Search with GPUs (2017, methodology): “ing a minimal accuracy loss results in orders of magnitude of compression [21]. The most popular vector compression methods can be classied into either binary codes [18, 22], or quantization methods [25, 37]. Both have the desirable property that searching neighbors does not require reconstructing t”
- Real-Time Open-Domain Question Answering with Dense-Sparse Phrase Index (2019, methodology): “In future, more advanced methods such as Product Quantization (Jegou et al., 2011) can be considered.”
- Quantization based Fast Inner Product Search (2015, methodology): “In fact, the above asymmetric computation for all the database vectors can still be carried out very efficiently via look up tables similar to [11], except that each entry in the k table is a dot product between q and columns of U (k) .”
- Hindsight: Posterior-guided training of retrievers for improved open-ended generation (2021, methodology): “The advent of efficient nearest-neighbour search algorithms (Jegou et al., 2010; Johnson et al., 2017) opened up the possibility of encoding the query and the passage collection into a vector space and finding the relevant passage as nearest neighbors to the query embedding.”
- A Memory Efficient Baseline for Open Domain Question Answering (2020, methodology): “A better approach in high-dimension, known as product quantization (Jegou et al., 2010), is to subdivide each vector of dimension d into n subvectors of dimension d/n and to quantize these independently, using k-means.”
- Unbounded cache model for online language modeling with open vocabulary (2017, methodology): “Product Quantization (PQ) is a popular quantization method that has shown competitive performance on many retrieval benchmarks [28].”
- CPlaNet: Enhancing Image Geolocalization by Combinatorial Partitioning of Maps (2018, methodology): “Compared to naïve average of the underlying classifiers denoted by Average[1-5] and Average[1-2], CPlaNet[1-5] and CPlaNet[1-2] have ∼ 16 % and ∼ 13 % of accuracy gains at street level, respectively, compared to their counterparts.”
- FastText.zip: Compressing text classification models (2016, methodology): “As baselines, we use Locality-Sensitive Hashing (LSH) (Charikar, 2002), PQ (Jegou et al., 2011) and OPQ (Ge et al., 2013) (the non-parametric variant).”
- wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations (2020, methodology): “For self-supervised training we discretize the output of the feature encoder z to a finite set of speech representations via product quantization [25].”
- XLS-R: Self-supervised Cross-lingual Speech Representation Learning at Scale (2021, methodology): “The quantization module uses a Gumbel softmax to choose entries form the codebooks and the chosen entries are concatenated to obtain q (Jegou et al., 2011; Jang et al., 2016; Baevski et al., 2020a).”
- Unsupervised Speech Recognition (2021, methodology): “The quantization module uses a Gumbel softmax to choose entries from E = 2 codebooks with V = 320 entries each and the chosen entries are concatenated to obtain q (Jegou et al., 2011; Jang et al., 2016; Baevski et al., 2020b).”