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
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389
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
Hamming Embedding and Weak Geometric Consistency for Large Scale Image Search
Jegou, H., Douze, M., & Schmid, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88682-2_24 · Cited by 1,901 · cited 15×
“Comparison with Hamming embedding methods: We compare our approach to spectral hashing (SH) [19], which maps vectors to binary signatures.”
MethodInfluentialSelf-citationGray, R. M., & Neuhoff, D. L. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720541 · Cited by 1,647
Lost in quantization: Improving particular object retrieval in large scale image databases
Philbin, J., Chum, O., Isard, M., Sivic, J., & Zisserman, A. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587635 · Cited by 1,478 · cited 1×
“First, the number of possible distances is significantly higher than for competing Hamming embedding methods [20], [17], [19], as the Hamming space used in these techniques allows for a few distinct distances only.”
MethodKernelized locality-sensitive hashing for scalable image search
Kulis, B., & Grauman, K. L. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459466 · Cited by 905 · cited 1×
“Most of the effort has been devoted to the Euclidean distance, though recent generalizations have been proposed for other metrics [10].”
BackgroundSearching in high-dimensional spaces
Böhm, C., Berchtold, S., & Keim, D. A. (2001) · ACM Computing Surveys · doi:10.1145/502807.502809 · Cited by 824 · cited 1×
“Nearest neighbor search is inherently expensive due to the curse of dimensionality [3], [4].”
BackgroundSmall codes and large image databases for recognition
Torralba, A., Fergus, R., & Weiss, Y. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587633 · Cited by 727
Optimised KD-trees for fast image descriptor matching
Silpa-Anan, C., & Hartley, R. I. (2008) · 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.2008.4587638 · Cited by 690 · cited 1×
“These methods include randomized KD-trees [14] and hierarchical k-means [15], both of which are implemented in the FLANN selection algorithm [9].”
MethodNearest-Neighbor Methods in Learning and Vision
(2006) · The MIT Press eBooks · doi:10.7551/mitpress/4908.001.0001 · Cited by 442
Nearest-neighbor methods in learning and vision : theory and practice
Shakhnarovich, G., Indyk, P., & Darrell, T. J. (2005) · Cited by 400
Evaluation of GIST descriptors for web-scale image search
Douze, M., Jeǵou, H., Sandhawalia, H., Amsaleg, L., & Schmid, C. (2009) · ACM International Conference on Image and Video Retrieval (CIVR) · doi:10.1145/1646396.1646421 · Cited by 394 · cited 1×
“When no supervision is used, this mapping is learned such that the neighborhood in the embedded space defined by the Hamming distance reflects the neighborhood in the Euclidean space of the original features.”
MethodSelf-citationEfficient near-duplicate detection and sub-image retrieval
Ke, Y. (2004) · Cited by 342
Minimum Sum-Squared Residue Co-clustering of Gene Expression Data
Cho, H., Dhillon, I. S., Guan, Y., et al. (2004) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.11 · Cited by 298 · cited 1×
“A possible solution is the minimum sumsquared residue coclustering [28] algorithm.”
Efficient representation of local geometry for large scale object retrieval
Perďoch, M., Chum, O., & Matas, J. (2009) · 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.2009.5206529 · Cited by 260 · cited 3×
“Note that some geometrical information can also be inserted in this entry, as proposed in [18] and [25].”
BackgroundMethodA contextual dissimilarity measure for accurate and efficient image search
Jeǵou, H., Harzallah, H., & Schmid, C. (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.382970 · Cited by 242 · cited 1×
“To address this problem, we use the multiple assignment strategy of [27].”
MethodSelf-citationNearest-Neighbor Methods in Learning and Vision (Shakhnarovich, G. et al., Eds.; 2006) [Book review]
Gianfelici, F. (2008) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.917504 · Cited by 236
Jeǵou, H., Douze, M., & Schmid, C. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459419 · Cited by 161 · cited 1×
“This memory cost can be reduced further using index compression [25], [26], which may reduce the average cost of storing the identifier to about 8 bits, depending on parameters.”
BackgroundSelf-citationRapid object indexing using locality sensitive hashing and joint 3D-signature space estimation
Matei, B., Shan, Y., Sawhney, H., Tan, Y., Kumar, R., Huber, D., & Hebert, M. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.148 · Cited by 106 · cited 1×
“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 This work was partly realized as part of the Quaero Programme, funded by OSEO, French State agency for innovation.”
MethodJeǵou, H., Douze, M., & Schmid, C. (2009) · Cited by 19
Self-citationSandhawalia, H., & Jeǵou, H. (2010) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2010.5495403 · Cited by 14 · cited 1×
“It is also related to the work [2] on source coding for nearest neighbor search.”
Background
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,…”
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
