The DOI matches its Crossref record; 31 of the 35 references it cites were found in a registry or an index.
Product Quantization for Nearest Neighbor Search
Open accessAbstract
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The text we found for this paper looks like another document, so the self-check wasn’t run.
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 · cited 1×
“An exhaustive comparison of the query vector with all codes is prohibitive for very large datasets.”
BackgroundVideo 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 · cited 3×
“Similarly to the “Video-Google” approach [24], a codebook is”
BackgroundMethodInfluentialModeling the Shape of the Scene: A Holistic Representation of the Spatial Envelope
Oliva, A., & Torralba, A. B. (2001) · International Journal of Computer Vision · doi:10.1023/a:1011139631724 · Cited by 6,321
Scalable Recognition with a Vocabulary Tree
Nistér, D., & Stewénius, H. (2006) · 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.2006.264 · Cited by 3,641 · cited 2×
“Lattice quantizers offer better quantization properties for uniform vector distributions, but this condition is rarely satisfied by real world vectors.”
BackgroundMethod(1999) · Cited by 3,186
Locality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. (2004) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/997817.997857 · Cited by 2,971 · cited 9×
“In this case, one of the most popular ANN algorithms is the Euclidean Locality-Sensitive Hashing (E2LSH) [7], [11], which provides theoretical guarantees on the search quality with limited assumptions.”
BackgroundMethodInfluentialObject retrieval with large vocabularies and fast spatial matching
Philbin, J. F., Chum, O., Isard, M., Šivic, J., & Zisserman, A. (2007) · 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.2007.383172 · Cited by 2,931
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,802 · cited 1×
“( Several multi-dimensional indexing methods, such as the popular KD-tree [5] or other branch and bound techniques, have been proposed to reduce the search time.”
MethodFAST APPROXIMATE NEAREST NEIGHBORS WITH AUTOMATIC ALGORITHM CONFIGURATION
(2009) · Proceedings of the Fourth International Conference on Computer Vision Theory and Applications · doi:10.5220/0001787803310340 · Cited by 2,640 · cited 3×
“An evaluation of the parameters of our approach and a comparison with the state of the art is given in Section V. II.”
BackgroundMethodWhen Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403
Research works printed but not linked: 2
- Weber, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, 194
- Knuth, 1998, The Art of Computer Programming, Sorting and Searching, 3
Cited by
Sorted by citations
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474
“For vector quantization, encoding residual vectors [17] is shown to be more effective than encoding original vectors.”
BackgroundDeep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2015) · arXiv · doi:10.48550/arxiv.1512.03385 · Cited by 4,196
“For vector quantization, encoding residual vectors [17] is shown to be more effective than encoding original vectors.”
BackgroundBillion-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
“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 the vectors. Our pap…”
BackgroundMethodInfluentialSelf-citationAggregating local descriptors into a compact image representation
Jeǵou, H., Douze, M., Schmid, C., & Pérez, P. (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.5540039 · Cited by 2,679
Self-citationNetVLAD: CNN Architecture for Weakly Supervised Place Recognition
Arandjelović, R., Gronát, P., Torii, A., Pajdla, T., & Šivic, J. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/cvpr.2016.572 · Cited by 3,532
“e vector representation for the entire image such as bag-of-visualwords [53,74], VLAD [3,29] or Fisher vector [31,52]. The resulting representation is then usually compressed and effi- ciently indexed [28,74]. The image database can be further augmented by 3D structure that enables recovery of accurate camera pose [40,…”
Backgroundwav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations
Baevski, A., Zhou, H., Mohamed, A., & Auli, M. (2020) · arXiv · doi:10.48550/arxiv.2006.11477 · Cited by 2,369
FitNets: Hints for Thin Deep Nets
Romero, A., Ballas, N., Kahou, S. E., Chassang, A., Gatta, C., & Bengio, Y. (2014) · arXiv · doi:10.48550/arxiv.1412.6550 · Cited by 2,859
“Other works related to quantization schemes (Chen et al., 2010; J´egou et al., 2011; Gong et al., 2014) aim at reducing storage requirements.”
BackgroundGong, Y., Lazebnik, S., Gordo, A., & Perronnin, F. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.193 · Cited by 1,846
“Another family of methods uses dimensionality reduction prior to binary coding, with PCA being the most common choice [13], [14], [18], [49], [50], [51].”
Malkov, Y. A., & Yashunin, D. A. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2889473 · Cited by 1,904
Deep Metric Learning via Lifted Structured Feature Embedding
Song, H. O., Yu, X., Jegelka, S., & Savarese, S. (2016) · 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.2016.434 · Cited by 1,710
“We can observe that the embedding clusters the images from the same brand of cars despite the significant pose variations and the changes in the body paint.”
BackgroundMethodNetVLAD: CNN architecture for weakly supervised place recognitionPreprint
Arandjelović, R., Gronát, P., Torii, A., Pajdla, T., & Šivic, J. (2015) · arXiv (Cornell University) · Cited by 1,790
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
“Some authors address the efficiency and memory constraints by using GIST descriptors [16], and by converting them to compact binary vectors [17], [11], [18].”
BackgroundSelf-citationImage Classification with the Fisher Vector: Theory and Practice
Sánchez, J., Perronnin, F., Mensink, T., & Verbeek, J. (2013) · International Journal of Computer Vision · doi:10.1007/s11263-013-0636-x · Cited by 1,498
Sketch-based manga retrieval using manga109 dataset
Matsui, Y., Ito, K., Aramaki, Y., Fujimoto, A., Ogawa, T., Yamasaki, T., & Aizawa, K. (2016) · Multimedia Tools and Applications · doi:10.1007/s11042-016-4020-z · Cited by 1,454
“This window-based representation is simple and efficient at finding a matching area in the page because a feature implicitly contains its position in the page, which is particularly useful for manga pages, and so this approach effectively solves the retrieval–localization problem.”
BackgroundScalable Nearest Neighbor Algorithms for High Dimensional Data
Muja, M., & Lowe, D. G. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2321376 · Cited by 1,446
“Dimensionality reduction has been used in the literature with good results ([7], [27], [28], [32], [57]), however even with dimensionality reduction it can be challenging to fit the data in the memory of a single machine for very large data sets.”
BackgroundMethod(2016) · neural information processing systems · Cited by 1,572
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
Quantized Convolutional Neural Networks for Mobile Devices
Wu, J., Leng, C., Wang, Y., Hu, Q., & Cheng, J. (2016) · 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.2016.521 · Cited by 1,273
“Product quantization [14] is widely used in approximate nearest neighbor search, demonstrating better performance than hashing-based methods [21, 22].”
MethodImage retrieval using scene graphs
Johnson, J., Krishna, R., Stark, M., Li, L.-J., Shamma, D. A., Bernstein, M. S., & Fei-Fei, L. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298990 · Cited by 1,101
“We adapt the metrics from [27]; specifically, for each method we report the median rank of the highest ranked true positive image I 2 , . . . Fig.”
MethodA Survey of Quantization Methods for Efficient Neural Network Inference
Gholami, A., Kim, S., Dong, Z., Yao, Z., Mahoney, M. W., & Keutzer, K. (2022) · Low-Power Computer Vision · doi:10.1201/9781003162810-13 · Cited by 1,219
“In particular, the work of [1, 30, 74, 83, 116, 166, 176, 184, 248] clusters the weights into different groups and use the centroid of each group as quantized values during inference.”
DINOv2: Learning Robust Visual Features without Supervision
Oquab, M., Darcet, T., Moutakanni, T., Vo, H., Szafraniec, M., Khalidov, V., Fernandez, P., Haziza, D., Massa, F., El-Nouby, A., et al. (2023) · arXiv · doi:10.48550/arxiv.2304.07193 · Cited by 1,078
“In particular, we heavily leverage its support for GPU-accelerated indices, using inverted file indices with product quantization codes (Jegou et al., 2010).”
MethodSelf-citationWang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 1,055
“BRE = binary reconstructive embedding [66], MLH = minimal loss hashing [107], LSH = locality sensitive hashing [14], ITQ = iterative quantization [35], [36], SH = spectral hashing [156], AGH-2 = two-layer hashing with graphs [86], USPLH = unsupervised sequential projection learning hashing [143], PQ = product quantiza…”
BackgroundMethodResultInfluentialDeep face recognition: A survey
Wang, M., & Deng, W. (2020) · Neurocomputing · doi:10.1016/j.neucom.2020.10.081 · Cited by 1,268
“[160] first used product quantization (PQ) [79] to directly retrieve the top-k most similar faces and re-ranked these faces by combining similarities from deep features and the COTS matcher [54].”
MethodSupervised Hashing for Image Retrieval via Image Representation Learning
Xia, R., Pan, Y., Lai, H., Liu, C., & Yan, S. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8952 · Cited by 979
“…amount of available image data on the web, approximate nearest neighbor (ANN) search in large-scale datasets with millions or billions images has recently received considerable attention (Jegou, Douze, and Schmid 2011; Wang, Kumar, and Chang 2010; Kulis and Grauman 2009; Liu et al. 2012).”
BackgroundCompressing Deep Convolutional Networks using Vector QuantizationPreprint
Gong, Y., Liu, L., Yang, M., & Bourdev, L. D. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.6115 · Cited by 1,047
“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.”
MethodDeep Supervised Hashing for Fast Image Retrieval
Liu, H., Wang, R., Shan, S., & Chen, X. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.227 · Cited by 933
HD-CNN: Hierarchical Deep Convolutional Neural Networks for Large Scale Visual Recognition
Yan, Z., Zhang, H., Piramuthu, R., Jagadeesh, V., DeCoste, D., Di, W., & Yu, Y. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.314 · Cited by 936
“Specifically, we choose product quantization [14] to compress the parameter matrix W ∈ Rm×n.”
MethodFastText.zip: Compressing text classification models
Joulin, A., Grave, E., Bojanowski, P., Douze, M., Jégou, H., & Mikolov, T. (2016) · arXiv · doi:10.48550/arxiv.1612.03651 · Cited by 887
Self-citationBRIEF: Computing a Local Binary Descriptor Very Fast
Calonder, M., Lepetit, V., Özuysal, M., Trzcinski, T. P., Strecha, C., & Fua, P. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.222 · Cited by 867
scmap: projection of single-cell RNA-seq data across data sets
(2018) · doi:10.1038/nmeth.4644 · Cited by 735
Large-Scale Image Retrieval with Attentive Deep Local Features
Noh, H., Araújo, A. D. M., Sim, J., Weyand, T., & Han, B. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.374 · Cited by 875
“Our image retrieval system is based on nearest neighbor search, which is implemented by a combination of KD-tree [7] and Product Quantization (PQ) [17].”
MethodLabel-Embedding for Image Classification
Akata, Z., Perronnin, F., Harchaoui, Z., & Schmid, C. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2487986 · Cited by 787
“This includes work on patch encoding (see [40] for a recent comparison), on kernel-based methods [41] with a recent focus on explicit embeddings [42], [43], on dimensionality reduction [41] and on compression [44], [45], [46].”
MethodSelf-citationSIFT Meets CNN: A Decade Survey of Instance Retrieval
Zheng, L., Yang, Y., & Tian, Q. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2709749 · Cited by 773
HashNet: Deep Learning to Hash by Continuation
Cao, Z., Long, M., Wang, J., & Yu, P. S. (2017) · 2017 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.598 · Cited by 777
“Typical learning criteria include reconstruction error minimization [30, 12, 16] and graph learning[36, 24].”
BackgroundDeep Hashing Network for Efficient Similarity Retrieval
Zhu, H., Long, M., Wang, J., & Cao, Y. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10235 · Cited by 664
“Typical learning criteria include reconstruction error minimization (Salakhutdinov and Hinton 2007; Jegou, Douze, and Schmid 2011), neighborhood preserving as graph-based hashing (Weiss, Torralba, and Fergus 2009; Liu et al. 2011), and quantization error minimization as Iterative Quantization (ITQ)…”
BackgroundLabel-Embedding for Attribute-Based Classification
Akata, Z., Perronnin, F., Harchaoui, Z., & Schmid, C. (2013) · 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.2013.111 · Cited by 647
“how to represent an image? This includes works on patch encoding (see [4] for a recent comparison), on kernel-based methods [32] with a recent focus on explicit embeddings [20, 35], on dimensionality reduction [32] and on compression [13, 30, 36].”
BackgroundMethodSelf-citationLDAHash: Improved Matching with Smaller Descriptors
Strecha, C., Bronstein, A. M., Bronstein, M. M., & Fua, P. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.103 · Cited by 605
Unsupervised Cross-Lingual Representation Learning for Speech Recognition
Conneau, A., Baevski, A., Collobert, R., Mohamed, A., & Auli, M. (2021) · Interspeech 2021 · doi:10.21437/interspeech.2021-329 · Cited by 637
“The quantization is based on product quantization (Jegou et al., 2011; Baevski et al., 2020b) by choosing quantized representations from G = 2 codebooks with V = 320 entries each.”
MethodXLS-R: Self-supervised Cross-lingual Speech Representation Learning at Scale
Babu, A., Wang, C., Tjandra, A., Lakhotia, K., Xu, Q., Goyal, N., Singh, K., von Platen, P., Saraf, Y., Pino, J., et al. (2022) · Interspeech 2022 · doi:10.21437/interspeech.2022-143 · Cited by 586
“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).”
MethodDeep Metric Learning with Angular Loss
Wang, J., Zhou, F., Wen, S., Liu, X., & Lin, Y. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.283 · Cited by 565
“This quantity is also known as Recall@R, the defacto metric [15] for image retrieving evaluation.”
BackgroundEnd-to-End Learning of Deep Visual Representations for Image Retrieval
Gordo, A., Almazán, J., Revaud, J., & Larlus, D. (2017) · International Journal of Computer Vision · doi:10.1007/s11263-017-1016-8 · Cited by 547
“…have been made to allow deep architectures to accurately represent input images of different sizes and aspect ratios (Babenko and Lempitsky, 2015; Kalantidis et al, 2016; Tolias et al, 2016) or to address the lack of geometric invariance of CNN-based features (Gong et al, 2014; Razavian et al,…”
Background24/7 place recognition by view synthesis
Torii, A., Arandjelović, R., Šivic, J., Okutomi, M., & Pajdla, T. (2015) · 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.2015.7298790 · Cited by 543
“file [33, 39] or product quantization [20] indexing techniques.”
Word Spotting and Recognition with Embedded Attributes
Almazán, J., Gordo, A., Fornés, A., & Valveny, E. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2339814 · Cited by 514
Transformation-Consistent Self-Ensembling Model for Semisupervised Medical Image Segmentation
Li, X., Yu, L., Chen, H., Fu, C., Xing, L., & Heng, P. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2995319 · Cited by 553
“4) Implementation of π operation: Multi-scale ensembling is shown to be effective for image recognition [25–27].”
BackgroundMethodProceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Gao, L., Zhu, X., Song, J., Zhao, Z., & Shen, H. T. (2019) · doi:10.24963/ijcai.2019 · Cited by 538
Learning to Hash for Indexing Big Data—A Survey
Wang, J., Liu, W., Kumar, S., & Chang, S. (2015) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2487976 · Cited by 534
“Unlike the recursive partitioning used by tree-based indexing methods, hashing methods repeatedly partition the entire dataset and derive a single hash ’bit’2 from each par- 2 Depending on the type of the hash function used, each hash may return either an integer or simply a binary bit.”
MethodHalder, R. K., Uddin, M. N., Uddin, M. A., Aryal, S., & Khraisat, A. (2024) · Journal Of Big Data · doi:10.1186/s40537-024-00973-y · Cited by 624
Hamming Distance Metric Learning
Norouzi, M., Fleet, D. J., & Salakhutdinov, R. (2012) · Cited by 562
Land Use Classification in Remote Sensing Images by Convolutional Neural NetworksPreprint
Castelluccio, M., Poggi, G., Sansone, C., & Verdoliva, L. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1508.00092 · Cited by 594
“Strong improvements also come from using more recent encoding methods as done in [22], where Fisher vectors (FV) [23], vectors of locally aggregated descriptors (VLAD) [24], and vectors of locally aggregated tensors (VLAT) [25] are used in combination with HOG and color features.”
MethodPix3D: Dataset and Methods for Single-Image 3D Shape Modeling
Sun, X., Wu, J., Zhang, X., Zhang, Z., Zhang, C., Xue, T., Tenenbaum, J. B., & Freeman, W. T. (2018) · 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.2018.00314 · Cited by 456
“For each test image, we retrieve its K nearest neighbors from the test set, and use Recall@K [28] to compute how many retrieved images are actually depicting the same shape.”
MethodDouze, M., Guzhva, A., Deng, C., Johnson, J., Szilvasy, G., Mazaré, P.-E., Lomeli, M., Hosseini, L., & Jégou, H. (2026) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2025.3618474 · Cited by 478
“Given this search algorithm, relying on a pure k-nearest neighbor graph is not optimal because neighbors are redundant.”
InfluentialSelf-citationWeakly Supervised Object Localization with Multi-Fold Multiple Instance Learning
Cinbis, R. G., Verbeek, J., & Schmid, C. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2016.2535231 · Cited by 420
“We reduce the memory footprint, and speed up our iterative training procedure, by using the PQ and Blosc feature compression [3], [26].”
MethodSelf-citationLi, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., & Lin, X. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2909204 · Cited by 501
“(PQ) [5] is a popular methods for ANNS, which decomposes”
A discriminative CNN video representation for event detection
Xu, Z., Yang, Y., & Hauptmann, A. G. (2015) · 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.2015.7298789 · Cited by 438
“In addition, we propose to use Product Quantization [15] based on CNN video representation to speed up the execution (event search) time.”
MethodInfluentialDistance-Based Image Classification: Generalizing to New Classes at Near-Zero Cost
Mensink, T., Verbeek, J. J., Perronnin, F., & Csurka, G. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.83 · Cited by 434
“To allow metric learning on high-dimensional image features of datasets that are too large to fit in memory, we use in addition product quantization [14], a data compression technique that was recently used with success for large-scale image retrieval [15] and classifier training [1].”
Methodvq-wav2vec: Self-Supervised Learning of Discrete Speech RepresentationsPreprint
Baevski, A., Schneider, S., & Auli, M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.05453 · Cited by 500
“In the following, we describe another strategy where we independently quantize partitions of z , similar to product quantization (Jegou et al., 2011).”
MethodK-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
“[10] further proposes the Asymmetric Distance Computation (ADC).”
BackgroundMethodInfluentialNegative Evidences and Co-occurences in Image Retrieval: The Benefit of PCA and Whitening
Jeǵou, H., & Chum, O. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-33709-3_55 · Cited by 391
“In this paper, we will mainly focus on more scalable approaches in the spirit of recent work on compact images representations [6–8], where the image description is a short vector, which is subsequently encoded in compact codes using binarization [6, 9] or product quantization techniques [10].”
MethodResultOptimized Product Quantization
Ge, T., He, K., Ke, Q., & Sun, J. Z. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.240 · Cited by 435
“In the exhaustive search, the data are quantized into codewords [1], [8], [9]; the distances of vectors are approximated by the distances of codewords.”
BackgroundMethodInfluentialOptimized Product Quantization for Approximate Nearest Neighbor Search
Ge, T., He, K., Ke, Q., & Sun, J. Z. (2013) · 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.2013.379 · Cited by 401
“Experiments show that our two solutions outperform the original PQ [10] and other alternatives like transform coding [3] and iterative quantization [6], even when the prior knowledge about the structure of the input data is used by PQ [10].”
BackgroundMethodInfluential(2021) · doi:10.1145/3448016.3457550 · Cited by 416
“• Vector query: This query type is the traditional vector similarity search [33, 41, 48, 49], where each entity is described”
BackgroundMethodInfluentialDeep Cauchy Hashing for Hamming Space Retrieval
Cao, Y., Long, M., Liu, B., & Wang, J. (2018) · 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.2018.00134 · Cited by 389
“Typical methods include reconstruction error minimization [27, 12, 14] and graph embedding [32, 23].”
MethodHashing for Similarity Search: A SurveyPreprint
Wang, J., Shen, H. T., Song, J., & Ji, J. (2014) · arXiv (Cornell University) · doi:10.4230/lipics.cpm.2023.20 · Cited by 458
A review of convolutional neural network architectures and their optimizations
Cong, S., & Zhou, Y. (2022) · Artificial Intelligence Review · doi:10.1007/s10462-022-10213-5 · Cited by 419
“developed a product quantization (PQ) algorithm for FC layers (Jegou et al. 2010).”
MethodHeo, J., Lee, Y., He, J., Chang, S., & Yoon, S. (2012) · 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.2012.6248024 · Cited by 373
“• GIST-1M-960D: A set of 960 dimensional, one million GIST descriptors that are also used in [14].”
BackgroundSelf-supervised speech representation learning: A review
Mohamed, A., Lee, H.-Y., Borgholt, L., Havtorn, J. D., Edin, J., Igel, C., Kirchhoff, K., Li, S.-W., Livescu, K., Maaløe, L., et al. (2022) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2022.3207050 · Cited by 372
“0 concatenates quantized representations from multiple codebooks at each timestep, so-called Product Quantization (PQ) [136].”
BackgroundVisual Place Recognition with Repetitive Structures
Torii, A., Šivic, J., Pajdla, T., & Okutomi, M. (2013) · 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.2013.119 · Cited by 364
“Examples include: (i) learning better visual vocabularies [21, 28]; (ii) developing quantization methods less prone to quantization errors [14, 27, 44]; (iii) combining returns from multiple query images depicting the same scene [4, 6]; (iv) exploiting the 3D or graph structure of the database [11, 20, 29, 42, 43, 47]…”
Fast approximate nearest neighbor search with the navigating spreading-out graph
Fu, C., Xiang, C. J., Wang, C., & Cai, D. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3303753.3303754 · Cited by 562
Challenges in KNN Classification
Zhang, S. (2021) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3049250 · Cited by 367
“For example, Jegou, Douze and Schmid proposed a product quantization for nearest neighbor search [71].”
BackgroundLearning descriptors for object recognition and 3D pose estimation
Wohlhart, P., & Lepetit, V. (2015) · 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.2015.7298930 · Cited by 458
“So far the only recognition approaches that have been demonstrated to work on large scale problems are based on Nearest Neighbor (NN) classification [23, 16, 8], because extremely efficient methods for NN search exist with an average complexity of O(1) [24, 21].”
MethodColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction
Santhanam, K., Khattab, O., Saad-Falcon, J., Potts, C., & Zaharia, M. (2022) · Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies · doi:10.18653/v1/2022.naacl-main.272 · Cited by 353
“Product quantization (Gray, 1984; Jegou et al., 2010) compresses a single vector by splitting it into small sub-vectors and encoding each of them using an ID within a codebook.”
BackgroundSmart Mining for Deep Metric Learning
Harwood, B., G, V. K. B., Carneiro, G., Reid, I. D., & Drummond, T. W. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.307 · Cited by 358
“For the experiments, we follow the protocol used in previous papers [18, 19, 13], which uses unseen classes from the CUB- 200-2011 [23] and Cars196 [8] datasets in order to assess the clustering quality and k nearest neighbour retrieval [7].”
MethodDeep Learning Advances in Computer Vision with 3D Data
Ioannidou, A., Chatzilari, E., Nikolopoulos, S., & Kompatsiaris, I. Y. (2017) · ACM Computing Surveys · doi:10.1145/3042064 · Cited by 334
“It was proven experimentally that structured quantization methods like product quantization [Jegou et al. 2011] perform best while even a simple k-means can lead to satisfying results.”
Norouzi, M., & Fleet, D. J. (2013) · 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.2013.388 · Cited by 306
“To derive the learning algorithm for ok-means we first rewrite the objective in matrix terms.”
BackgroundMethodInfluentialDeep Metric Learning via Facility Location
Song, H. O., Jegelka, S., Rathod, V., & Murphy, K. P. (2017) · 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.2017.237 · Cited by 295
“Following the experimental protocol in [30, 29], we evaluate the clustering and k nearest neighbor retrieval [13] results on data from previously unseen classes on the CUB200-2011 [37], Cars196 [18], and Stanford Online Products [30] datasets.”
MethodSearching in one billion vectors: Re-rank with source coding
Jeǵou, H., Tavenard, R., Douze, M., & Amsaleg, L. (2011) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2011.5946540 · Cited by 317
“They are, however, significantly outperformed in terms of the trade-off between memory usage and accuracy by recent methods that cast high dimensional indexing to a source coding problem [11, 5, 6], in particular the product quantization-based method of [5] exhibits impressive results for large scale image search [6].”
BackgroundMethodInfluentialSelf-citationLocally Optimized Product Quantization for Approximate Nearest Neighbor Search
Kalantidis, Y., & Avrithis, Y. (2014) · 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.2014.298 · Cited by 291
“All methods are non-exhaustive as in section 4.1, i.e. using a coarse quantizer, inverted lists and PQ-encoded residuals; however, all optimization variants are global except for LOPQ.”
BackgroundMethodInfluentialLinear cross-modal hashing for efficient multimedia search
Zhu, X., Huang, Z. H., Shen, H. T., & Zhao, X. (2013) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/2502081.2502107 · Cited by 285
“…Search Process Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.”
BackgroundAdditive Quantization for Extreme Vector Compression
Babenko, A., & Lempitsky, V. (2014) · 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.2014.124 · Cited by 289
“SIFT-1M: This dataset introduced in [10] contains one million of 128-dimensional SIFT descriptors [13], plus 100,000 descriptors in a hold out set.”
BackgroundMethodInfluentialGirod, B., Chandrasekhar, V., Chen, D. M., Cheung, N. M., Grzeszczuk, R., Reznik, Y. A., Gabriel Takacs, A., Tsai, S. S., & Vedantham, R. (2011) · IEEE Signal Processing Magazine · doi:10.1109/msp.2011.940881 · Cited by 290
“The VQ schemes based on the product quantizer [ 34 ] or a tree-structured vector quantizer [10] are complex and require storage of large codebooks on the mobile device.”
Metric Learning for Large Scale Image Classification: Generalizing to New Classes at Near-Zero Cost
Mensink, T., Verbeek, J., Perronnin, F., & Csurka, G. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-33709-3_35 · Cited by 281
“Product quantization (PQ) was introduced in [6] as a lossy compression mechanism for local SIFT descriptors in a bag-of-features image retrieval system.”
Joint Detection and Recounting of Abnormal Events by Learning Deep Generic Knowledge
Hinami, R., Mei, T., & Satoh, S. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.391 · Cited by 277
Delving deep into spatial pooling for squeeze-and-excitation networks
Jin, X. Y., Xie, Y., Wei, X.-S., Zhao, B., Chen, Z.-M., & Tan, X. (2021) · Pattern Recognition · doi:10.1016/j.patcog.2021.108159 · Cited by 299
Embedding-based Retrieval in Facebook Search
Huang, J.-T., Sharma, A., Sun, S., Xia, L., Zhang, D., Pronin, P., Padmanabhan, J., Ottaviano, G., & Yang, L. (2020) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3394486.3403305 · Cited by 386
“onents for the embedding quantization, one is the coarse quantization which quantizes embedding vectors into coarse clusters typically through K-means algorithm, and the other is product quantization [8] which does a fine-grained quantization to enable efficient calculation of embedding distances. There are several im…”
High-dimensional signature compression for large-scale image classification
Sanchez, J., & Perronnin, F. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995504 · Cited by 272
“[13] proposed product quantizers (PQ) for NN-search of SIFT vectors.”
BackgroundMethodFast search in Hamming space with multi-index hashing
Norouzi, M., Punjani, A., & Fleet, D. J. (2012) · 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.2012.6248043 · Cited by 263
“, [1, 10, 15]), we restrict our attention in this paper to the use of compact binary codes.”
BackgroundWang, M., Xu, X., Yue, Q., & Wang, Y. (2021) · Proceedings of the VLDB Endowment · doi:10.14778/3476249.3476255 · Cited by 411
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
WikiMatrix: Mining 135M Parallel Sentences in 1620 Language Pairs from Wikipedia
Schwenk, H., Chaudhary, V., Sun, S., Gong, H., & Guzmán, F. (2021) · Conference of the European Chapter of the Association for Computational Linguistics · doi:10.18653/v1/2021.eacl-main.115 · Cited by 317
“In this work, we chose a rather aggressive compression based on a 64-bit productquantizer (Jégou et al., 2011), and portioning the search space in 32k cells.”
MethodREMIND Your Neural Network to Prevent Catastrophic Forgetting
Hayes, T. L., Kafle, K., Shrestha, R., Acharya, M., & Kanan, C. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-58598-3_28 · Cited by 286
Optimizing Dense Retrieval Model Training with Hard Negatives
Zhan, J., Mao, J., Liu, Y., Guo, J., Zhang, M., & Ma, S. (2021) · Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval · doi:10.1145/3404835.3462880 · Cited by 248
Jin, Z., Li, C., Lin, Y., & Cai, D. (2013) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2013.2283497 · Cited by 226
“ing methods [3], [6], [13]–[16], [18]–[20], [25], [28]–[32],”
BackgroundA neural algorithm for a fundamental computing problem
Dasgupta, S., Stevens, C. F., & Navlakha, S. (2017) · Science · doi:10.1126/science.aam9868 · Cited by 231
A survey on Visual-Based Localization: On the benefit of heterogeneous data
Piasco, N., Sidibé, D., Demonceaux, C., & Gouet-Brunet, V. (2017) · Pattern Recognition · doi:10.1016/j.patcog.2017.09.013 · Cited by 244
Deep Quantization Network for Efficient Image Retrieval
Cao, Y., Long, M., Wang, J., Zhu, H., & Wen, Q. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10455 · Cited by 224
“…in M codebooks can be pre-computed and stored in a queryspecific M ×K lookup table, which is used to compute AQD between the query and all database points h i , each entails M table lookups and additions and is only slightly more costly than Hamming distance (Jegou, Douze, and Schmid 2011).”
BackgroundMethodInfluentialRecent advances in efficient computation of deep convolutional neural networks
Cheng, J., Wang, P., Li, G., Hu, Q., & Lu, H. (2018) · Frontiers of Information Technology & Electronic Engineering · doi:10.1631/fitee.1700789 · Cited by 251
“In addition, the product quantization algorithm (PQ) [36], a special case of vector quantization, was leveraged to compress the fully connected layers.”
MethodA Sparse Embedding and Least Variance Encoding Approach to Hashing
Zhu, X., Zhang, L., & Huang, Z. H. (2014) · IEEE Transactions on Image Processing · doi:10.1109/tip.2014.2332764 · Cited by 226
Efficient Natural Language Response Suggestion for Smart ReplyPreprint
Henderson, M., Al‐Rfou, R., Strope, B. P., Sung, Y.-H., Lukacs, L., Guo, R., Kumar, S., Miklos, B., & Kurzweil, R. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.00652 · Cited by 449
Revisiting the VLAD image representation
Delhumeau, J., Gosselin, P.-H., Jeǵou, H., & Pérez, P. (2013) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/2502081.2502171 · Cited by 214
“Table 3 shows that the relative improvement of our technique is comparatively reduced when applying dimensionality reduction and using compact codes obtained by product quantization [7].”
BackgroundMethodInfluentialA 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
“Similar statement was proposed in [62] from the statistical perspective: the distance reconstruction error is statistically bounded by the quantization error.”
Background
Metadata
- Authors
- Jégou, H., Douze, M., & Schmid, C.
- Affiliations
- Institut national de recherche en sciences et technologies du numérique (FR)
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2011-01
- Volume
- 33
- Issue
- 1
- Pages
- 117-128
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2124509324
- Semantic Scholar
- 4748d22348e72e6e06c2476486afddbc76e5eca7
- Cited by
- 2,956
- References
- 35
- Citations by year
- 2026: 260 · 2025: 295 · 2024: 233 · 2023: 211 · 2022: 195 · 2021: 204 · 2020: 187 · 2019: 207 · 2018: 201 · 2017: 184 · 2016: 196 · 2015: 196 · 2014: 159 · 2013: 116 · 2012: 71
- FWCI
- 84.24
- Type
- journal article
- Language
- en
- Open access
- green
- inria.hal.science
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- PubMed (publishedVersion)
- HAL (submittedVersion, other-oa)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Image and Video Retrieval Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Image Retrieval and Classification Techniques
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Data Compression Techniques
- Keywords
- product quantization, approximate nearest neighbor search, subspace decomposition, inverted index, SIFT descriptors, GIST descriptors, image retrieval, scalability
- MeSH terms
- Algorithms, Artificial Intelligence, Image Interpretation, Computer-Assisted, Image Processing, Computer-Assisted, Pattern Recognition, Automated, Models, Statistical, Cluster Analysis, Information Storage and Retrieval
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.
A second model labelled each claim on 2026-10-08 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
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
