The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Kernelized locality-sensitive hashing for scalable image search
Abstract
Fast retrieval methods are critical for large-scale and data-driven vision applications. Recent work has explored ways to embed high-dimensional features or complex distance functions into a low-dimensional Hamming space where items can be efficiently searched. However, existing methods do not apply for high-dimensional kernelized data when the underlying feature embedding for the kernel is unknown. We show how to generalize locality-sensitive hashing to accommodate arbitrary kernel functions, making it possible to preserve the algorithm's sub-linear time similarity search guarantees for a wide class of useful similarity functions. Since a number of successful image-based kernels have unknown or incomputable embeddings, this is especially valuable for image retrieval tasks. We validate our technique on several large-scale datasets, and show that it enables accurate and fast performance for example-based object classification, feature matching, and content-based retrieval.
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
Nonlinear Component Analysis as a Kernel Eigenvalue Problem
Schölkopf, B., Smola, A., & Müller, K.-R. (1998) · Neural Computation · doi:10.1162/089976698300017467 · Cited by 8,084
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
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
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
(1999) · Cited by 3,186
Locality-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
Photo tourism: exploring photo collections in 3D
Snavely, N., Seitz, S. M., & Szeliski, R. (2006) · ACM Transactions on Graphics · doi:10.1145/1141911.1141964 · Cited by 2,866
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,813
Random Features for Large-Scale Kernel Machines
Rahimi, A., & Recht, B. (2007) · Cited by 2,783
Weiss, Y., Torralba, A. B., & Fergus, R. (2008) · neural information processing systems · Cited by 2,767
Cited by
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
“Most of the effort has been devoted to the Euclidean distance, though recent generalizations have been proposed for other metrics [10].”
BackgroundAggregating 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
Gong, Y., Lazebnik, S., Gordo, A., & Perronnin, F. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.193 · Cited by 1,834
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
Scalable 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,407
Shen, F., Shen, C., Liu, W., & Shen, H. T. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298598 · Cited by 1,231
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
Image Matching from Handcrafted to Deep Features: A Survey
Ma, J., Jiang, X., Fan, A., Jiang, J., & Yan, J. (2021) · International Journal of Computer Vision · doi:10.1007/s11263-020-01359-2 · Cited by 990
Supervised 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 952
Simultaneous feature learning and hash coding with deep neural networks
Lai, H., Pan, Y., Liu, Y., & Yan, S. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298947 · Cited by 884
Jiang, Q.-Y., & Li, W.-J. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.348 · Cited by 880
Semi-Supervised Hashing for Large-Scale Search
Wang, J., Kumar, S., & Chang, S.-F. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.48 · Cited by 810
Large-scale image retrieval with compressed Fisher vectors
Perronnin, F., Liu, Y., Sanchez, J., & Poirier, H. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5540009 · Cited by 761
Collective Matrix Factorization Hashing for Multimodal Data
Ding, G., Guo, Y., & Zhou, J. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.267 · Cited by 680
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
Deep hashing for compact binary codes learning
Liong, V. E., Lu, J., Wang, G., Moulin, P., & Zhou, J. (2015) · 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2015.7298862 · Cited by 545
A review of multimodal image matching: Methods and applications
Jiang, X., Ma, J., Xiao, G., Shao, Z., & Guo, X. (2021) · Information Fusion · doi:10.1016/j.inffus.2021.02.012 · Cited by 532
Learning to Hash for Indexing Big Data—A Survey
Wang, J., Liu, W., Kumar, S., & Chang, S.-F. (2016) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2487976 · Cited by 519
Deep Multi-View Enhancement Hashing for Image Retrieval
Yan, C., Gong, B., Wei, Y., & Gao, Y. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.2975798 · Cited by 504
Latent semantic sparse hashing for cross-modal similarity search
Zhou, J., Ding, G., & Guo, Y. (2014) · Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval · doi:10.1145/2600428.2609610 · Cited by 467
Radisic, A. (2025) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.17117444 · Cited by 462
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
Differentially Private High-Dimensional Approximate Range Counting, Revisited
Wang, J., Shen, H. T., Song, J., & Ji, J. (2014) · arXiv (Cornell University) · doi:10.4230/lipics.cpm.2023.20 · Cited by 370
Heo, J.-P., Lee, Y., He, J., Chang, S.-F., & Yoon, S.-E. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6248024 · Cited by 362
Kernelized Locality-Sensitive Hashing
Kulis, B., & Grauman, K. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.219 · Cited by 331
Self-citationColumn Sampling Based Discrete Supervised Hashing
Kang, W.-C., Li, W.-J., & Zhou, Z.-H. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10176 · Cited by 295
Deep Sketch Hashing: Fast Free-Hand Sketch-Based Image Retrieval
Liu, L., Shen, F., Shen, Y., Liu, X., & Shao, L. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.247 · Cited by 286
Linear cross-modal hashing for efficient multimedia search
Zhu, X., Huang, Z., Shen, H. T., & Zhao, X. (2013) · Proceedings of the 21st ACM international conference on Multimedia · doi:10.1145/2502081.2502107 · Cited by 282
Supervised hashing with latent factor models
Zhang, P., Zhang, W., Li, W.-J., & Guo, M. (2014) · Proceedings of the 37th international ACM SIGIR conference on Research & development in information retrieval · doi:10.1145/2600428.2609600 · Cited by 271
Asymmetric Deep Supervised Hashing
Jiang, Q.-Y., & Li, W.-J. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11814 · Cited by 266
High-throughput histopathological image analysis via robust cell segmentation and hashing
Zhang, X., Xing, F., Su, H., Yang, L., & Zhang, S. (2015) · Medical Image Analysis · doi:10.1016/j.media.2015.10.005 · Cited by 87
Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search
Boytsov, L., Novak, D., Malkov, Y., & Nyberg, E. (2016) · Proceedings of the 25th ACM International on Conference on Information and Knowledge Management · doi:10.1145/2983323.2983815 · Cited by 50
Evaluating robustness of perceptual image hashing algorithms
Drmic, A., Silic, M., Delac, G., Vladimir, K., & Kurdija, A. S. (2017) · 2017 40th International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO) · doi:10.23919/mipro.2017.7973569 · Cited by 35
Metadata
- Authors
- Kulis, B., & Grauman, K.
- Venue
- 2009 IEEE 12th International Conference on Computer Vision
- Publisher
- IEEE
- Published
- 2009-09
- Pages
- 2130-2137
- OpenAlex
- W2171790913
- Cited by
- 890
- References
- 36
- FWCI
- 36.80
- 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.