The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Optimized Product Quantization
Abstract
Product quantization (PQ) is an effective vector quantization method. A product quantizer can generate an exponentially large codebook at very low memory/time cost. The essence of PQ is to decompose the high-dimensional vector space into the Cartesian product of subspaces and then quantize these subspaces separately. The optimal space decomposition is important for the PQ performance, but still remains an unaddressed issue. In this paper, we optimize PQ by minimizing quantization distortions w.r.t the space decomposition and the quantization codebooks. We present two novel solutions to this challenging optimization problem. The first solution iteratively solves two simpler sub-problems. The second solution is based on a Gaussian assumption and provides theoretical analysis of the optimality. We evaluate our optimized product quantizers in three applications: (i) compact encoding for exhaustive ranking [1], (ii) building inverted multi-indexing for non-exhaustive search [2], and (iii) compacting image representations for image retrieval [3]. In all applications our optimized product quantizers outperform existing solutions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Distinctive Image Features from Scale-Invariant Keypoints
Lowe, D. G. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000029664.99615.94 · Cited by 55,589
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
(1967) · Cited by 23,719
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Video Google: a text retrieval approach to object matching in videos
Sivic, & Zisserman (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238663 · Cited by 6,367
Modeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope
Oliva, A., & Torralba, A. (2001) · International Journal of Computer Vision · doi:10.1023/a:1011139631724 · Cited by 6,319
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Scalable Recognition with a Vocabulary Tree
Nister, D., & Stewenius, H. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.264 · Cited by 3,579
Product Quantization for Nearest Neighbor Search
Jégou, H., Douze, M., & Schmid, C. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.57 · Cited by 2,956 · cited 10×
“In the exhaustive search, the data are quantized into codewords [1], [8], [9]; the distances of vectors are approximated by the distances of codewords.”
BackgroundMethodInfluentialAggregating local descriptors into a compact image representation
Jegou, H., Douze, M., Schmid, C., & Perez, P. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5540039 · Cited by 2,692
Cited by
Billion-scale similarity search with GPUs
Johnson, J., Douze, M., & Jégou, H. (2017) · arXiv · doi:10.48550/arxiv.1702.08734 · Cited by 4,140
Billion-scale similarity search with GPUs
Johnson, J., Douze, M., & Jegou, H. (2021) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2019.2921572 · Cited by 4,228
Sketch-based manga retrieval using manga109 dataset
Matsui, Y., Ito, K., Aramaki, Y., Fujimoto, A., Ogawa, T., Yamasaki, T., & Aizawa, K. (2017) · Multimedia Tools and Applications · doi:10.1007/s11042-016-4020-z · Cited by 1,432
Exploring the Limits of Weakly Supervised Pretraining
Mahajan, D., Girshick, R., Ramanathan, V., He, K., Paluri, M., Li, Y., Bharambe, A., & van der Maaten, L. (2018) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-01216-8_12 · Cited by 1,224
Self-citationAccelerating Very Deep Convolutional Networks for Classification and Detection
Zhang, X., Zou, J., He, K., & Sun, J. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2502579 · Cited by 832
Self-citationLi, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., & Lin, X. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2909204 · Cited by 454
(2021) · doi:10.1145/3448016.3457550 · Cited by 416
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search
Kalantidis, Y., & Avrithis, Y. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.298 · Cited by 275
Get Out of My Lab: Large-scale, Real-Time Visual-Inertial Localization
Lynen, S., Sattler, T., Bosse, M., Hesch, J., Pollefeys, M., & Siegwart, R. (2015) · Robotics: Science and Systems XI · doi:10.15607/rss.2015.xi.037 · Cited by 243
A Survey on Deep Hashing Methods
Luo, X., Wang, H., Wu, D., Chen, C., Deng, M., Huang, J., & Hua, X.-S. (2023) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3532624 · Cited by 241
From Matching to Generation: A Survey on Generative Information Retrieval
Li, X., Jin, J., Zhou, Y., Zhang, Y., Zhang, P., Zhu, Y., & Dou, Z. (2025) · ACM Transactions on Information Systems · doi:10.1145/3722552 · Cited by 172
Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance
Zhan, J., Mao, J., Liu, Y., Guo, J., Zhang, M., & Ma, S. (2021) · Proceedings of the 30th ACM International Conference on Information & Knowledge Management · doi:10.1145/3459637.3482358 · Cited by 91
Zhan, J., Mao, J., Liu, Y., Guo, J., Zhang, M., & Ma, S. (2022) · Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining · doi:10.1145/3488560.3498443 · Cited by 72
Scalable and Effective Generative Information Retrieval
Zeng, H., Luo, C., Jin, B., Sarwar, S. M., Wei, T., & Zamani, H. (2024) · Proceedings of the ACM Web Conference 2024 · doi:10.1145/3589334.3645477 · Cited by 32
Shall We Pretrain Autoregressive Language Models with Retrieval? A Comprehensive Study
Wang, B., Ping, W., Xu, P., McAfee, L., Liu, Z., Shoeybi, M., Dong, Y., Kuchaiev, O., Li, B., Xiao, C., et al. (2023) · Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing · doi:10.18653/v1/2023.emnlp-main.482 · Cited by 21
Metadata
- Authors
- Ge, T., He, K., Ke, Q., & Sun, J.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2014-04
- Volume
- 36
- Issue
- 4
- Pages
- 744-755
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2077815765
- Cited by
- 391
- References
- 36
- FWCI
- 23.15
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.