The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Locally Optimized Product Quantization for Approximate Nearest Neighbor Search
Abstract
We present a simple vector quantizer that combines low distortion with fast search and apply it to approximate nearest neighbor (ANN) search in high dimensional spaces. Leveraging the very same data structure that is used to provide non-exhaustive search, i.e., inverted lists or a multi-index, the idea is to locally optimize an individual product quantizer (PQ) per cell and use it to encode residuals. Local optimization is over rotation and space decomposition, interestingly, we apply a parametric solution that assumes a normal distribution and is extremely fast to train. With a reasonable space and time overhead that is constant in the data size, we set a new state-of-the-art on several public datasets, including a billion-scale one.
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
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 18×
“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.”
BackgroundMethodInfluentialLocality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. S. (2004) · Proceedings of the twentieth annual symposium on Computational geometry · doi:10.1145/997817.997857 · Cited by 2,936
FAST 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
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,389
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
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
Optimized Product Quantization
Ge, T., He, K., Ke, Q., & Sun, J. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.240 · Cited by 391
Optimized 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
Searching in one billion vectors: Re-rank with source coding
Jegou, H., Tavenard, R., Douze, M., & Amsaleg, L. (2011) · 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) · doi:10.1109/icassp.2011.5946540 · Cited by 313
Norouzi, M., & Fleet, D. J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.388 · Cited by 298
Locality sensitive hashing: A comparison of hash function types and querying mechanisms
Paulevé, L., Jégou, H., & Amsaleg, L. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2010.04.004 · Cited by 297
Fast search in Hamming space with multi-index hashing
Norouzi, M., Punjani, A., & Fleet, D. J. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248043 · Cited by 263
Revisiting the VLAD image representation
Delhumeau, J., Gosselin, P.-H., Jégou, H., & Pérez, P. (2013) · Proceedings of the 21st ACM international conference on Multimedia · doi:10.1145/2502081.2502171 · Cited by 214
Babenko, A., & Lempitsky, V. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248038 · Cited by 200
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
Xia, Y., He, K., Wen, F., & Sun, J. Z. (2013) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2013.424 · Cited by 62
Avrithis, Y. (2013) · IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2013.376 · Cited by 16
Self-citationExtremely Low Bit-Rate Nearest Neighbor Search Using a Set Compression Tree
Arandjelović, R., & Zisserman, A. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2339821 · Cited by 12
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
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
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
Wang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 971
Metadata
- Authors
- Kalantidis, Y., & Avrithis, Y.
- Venue
- 2014 IEEE Conference on Computer Vision and Pattern Recognition
- Publisher
- IEEE
- Published
- 2014-06
- Pages
- 2329-2336
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2133995768
- Cited by
- 275
- References
- 18
- FWCI
- 14.60
- Type
- conference paper
- 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.