Optimized Product Quantization for Approximate Nearest Neighbor Search

By Tiezheng Ge, Kaiming He, Qifa Ke. 2013

491 citations recorded by the source corpus.

Subfields: Computer Vision and Pattern Recognition, 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

In Information Retrieval & Search

Citations in the corpus

Unbounded cache model for online language modeling with open vocabulary (2017, methodology): “Note that in PQ, the subspaces are aligned with the natural axis and improvements where made by Ge et al. [18] to align the subspaces to principal axes in the data.”
FastText.zip: Compressing text classification models (2016, methodology): “In the original PQ, the subspaces are aligned with the natural axis, while OPQ learns a rotation, which amounts to alleviating this constraint and to not depend on the original coordinate system.”
Embedding-based Retrieval in Facebook Search (2020, methodology): “ivial change of the model training task, e.g., add more hard negatives. •Always try OPQ. It is often useful to transform data prior to applying the quantization. We experimented with both PCA and OPQ [5] to transform the data, and observed that OPQ is generally more effective, as shown in Table 3 an”
Large-Scale Supervised Multimodal Hashing with Semantic Correlation Maximization (2014, background): “…and Indyk 2008; Kulis and Darrell 2009; Lin, Ross, and Yagnik 2010; Wang, Kumar, and Chang 2010; Norouzi and Fleet 2011; Kong, Li, and Guo 2012; Heo et al. 2012; Liu et al. 2012a; Kong and Li 2012b; Norouzi, Fleet, and Salakhutdinov 2012; Strecha et al. 2012; Ge et al. 2013; Neyshabur et al. 2013).”
Cartesian K-Means (2013, unknown): “A very similar generalization of PQ, was developed concurrently by Ge, He, Ke and Sun, and also appears in CVPR 2013 [4].”
Optimized Product Quantization (2014, background): “Concurrent with [12], a very similar work “Cartesian k-means” [13] is independently developed.”
A Survey on Learning to Hash (2016, methodology): “Thanks to the multi-sequence algorithm, the Cartesian quantization algorithms are also applied to the inverted index [4], [172], [31] (called inverted multi-index), in which”
The Faiss Library (2024, unknown): “The OPQ transformation [69] is a rotation of the input space that decorrelates the distribution of each sub-vector of a product quantizer.”
A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search (2021, methodology): “Then [33] compresses the original vector by OPQ [39] to obtain the seeds by quickly calculating the compressed vector.”
Sparse composite quantization (2015, methodology): “Cartesian k-means [22] (or optimized product quantization [6]) improves the compositionabilty, i.”
Web-Scale Image Clustering Revisited (2015, methodology): “For IQ-means, we permute the dimensions to balance the variance between the two subspaces before multi-indexing [13].”
Dense Text Retrieval Based on Pretrained Language Models: A Survey (2022, methodology): “In this part, we describe a product quantization (PQ) approach [261], [262] to compressing the text embeddings and accelerating similarity compute, reducing both time and memory costs.”
Polysemous Codes (2016, methodology): “These quantization-based methods include product quantization (PQ) [28] and its optimized versions “optimized product quantization” [19] and “Cartesian k -means” [40].”
The Inverted Multi-Index (2012, methodology): “The IVFADC system also allows to use the OPQ at the fine level for compression.”
Additive Quantization for Extreme Vector Compression (2014, background): “For other types, a significant gain in PQ performance can be obtained by transforming the vectors via rotation found by an optimization process [15, 8].”
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes (2013, methodology): “This decomposing method is called Eigenvalue Allocation, with its theoretical foundation in [4].”
Efficient Indexing of Billion-Scale Datasets of Deep Descriptors (2016, background): “Two recent works have therefore looked into finding an optimal transformation [10, 16].”
FANNG: Fast Approximate Nearest Neighbour Graphs (2016, background): “This means that if the graph has an edge from p1 to p2, then it is not necessary for it to have an edge from p1 to any vertex p3 that is closer to p2 than p1.”