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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389
A Generalized Solution of the Orthogonal Procrustes Problem
Schönemann, P. H. (1966) · Psychometrika · doi:10.1007/bf02289451 · Cited by 2,040
80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene Recognition
Torralba, A., Fergus, R., & Freeman, W. T. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.128 · Cited by 1,921
Gray, R. M., & Neuhoff, D. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720541 · Cited by 1,642
Fisher Kernels on Visual Vocabularies for Image Categorization
Perronnin, F., & Dance, C. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383266 · Cited by 1,641
Aggregating Local Image Descriptors into Compact Codes
Jegou, H., Perronnin, F., Douze, M., Sanchez, J., Perez, P., & Schmid, C. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.235 · Cited by 1,503
Supervised hashing with kernels
Liu, W., Wang, J., Ji, R., Jiang, Y.-G., & Chang, S.-F. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247912 · Cited by 1,351
In defense of Nearest-Neighbor based image classification
Boiman, O., Shechtman, E., & Irani, M. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587598 · Cited by 1,072
Iterative quantization: A procrustean approach to learning binary codes
Gong, Y., & Lazebnik, S. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995432 · Cited by 1,038
A feasible method for optimization with orthogonality constraints
Wen, Z., & Yin, W. (2013) · Mathematical Programming · doi:10.1007/s10107-012-0584-1 · Cited by 849
Learning to Hash with Binary Reconstructive Embeddings
Kulis, B., & Darrell, T. (2009) · Cited by 806
Minimal Loss Hashing for Compact Binary Codes
Norouzi, M., & Blei, D. M. (2011) · Cited by 694
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Har-Peled, S., Indyk, P., & Motwani, R. (2012) · Theory of Computing · doi:10.4086/toc.2012.v008a014 · Cited by 693
Semi-supervised hashing for scalable image retrieval
Wang, J., Kumar, S., & Chang, S.-F. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539994 · Cited by 601
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
He, K., Wen, F., & Sun, J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.378 · Cited by 395
Self-citationOptimized Product Quantization for Approximate Nearest Neighbor Search
Ge, T., He, K., Ke, Q., & Sun, J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.379 · Cited by 384
Self-citationNorouzi, M., & Fleet, D. J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.388 · Cited by 298
Kong, W., & Li, W.-J. (2012) · neural information processing systems · Cited by 277
Babenko, A., & Lempitsky, V. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248038 · Cited by 200
Computational Complexity and Statistical Physics
(2005) · Oxford University Press eBooks · doi:10.1093/oso/9780195177374.001.0001 · Cited by 179
Multidimensional Spectral Hashing
Weiss, Y., Fergus, R., & Torralba, A. B. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33715-4_25 · Cited by 157
The Easiest Hard Problem: Number Partitioning
Mertens, S. (2005) · Oxford University Press eBooks · doi:10.1093/oso/9780195177374.003.0012 · Cited by 116
Asymmetric Distances for Binary Embeddings
Gordo, A., Perronnin, F., Gong, Y., & Lazebnik, S. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.101 · Cited by 116
Transform coding for fast approximate nearest neighbor search in high dimensions
Brandt, J. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539852 · Cited by 109
Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces
Dong, W., Charikar, M., & Li, K. (2008) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/1390334.1390358 · Cited by 98
Sandhawalia, H., & Jeǵou, H. (2010) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2010.5495403 · Cited by 15
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-citation
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.