The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
Kernelized Locality-Sensitive Hashing
Abstract
Fast retrieval methods are critical for many 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 sublinear 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 data sets, and show that it enables accurate and fast performance for several vision problems, including example-based object classification, local feature matching, and content-based retrieval.
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
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
Asymptotic Theory of Certain "Goodness of Fit" Criteria Based on Stochastic Processes
Anderson, T. W., & Darling, D. A. (1952) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729437 · Cited by 3,542
Learning realistic human actions from movies
Laptev, I., Marszalek, M., Schmid, C., & Rozenfeld, B. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587756 · Cited by 3,444
Scale & Affine Invariant Interest Point Detectors
Mikolajczyk, K., & Schmid, C. (2004) · International Journal of Computer Vision · doi:10.1023/b:visi.0000027790.02288.f2 · Cited by 3,436
(1999) · Cited by 3,186
Mathematical Statistics and Data Analysis
Rabinowitz, L. (1989) · Technometrics · doi:10.1080/00401706.1989.10488573 · Cited by 3,116
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,389
Fei-Fei, L., Fergus, R., & Perona, P. (2007) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2005.09.012 · Cited by 2,359
Similarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
Information-theoretic metric learning
Davis, J. V., Kulis, B., Jain, P., Sra, S., & Dhillon, I. S. (2007) · Proceedings of the 24th international conference on Machine learning · doi:10.1145/1273496.1273523 · Cited by 2,006
Self-citationZhang, J., Marszałek, M., Lazebnik, S., & Schmid, C. (2007) · International Journal of Computer Vision · doi:10.1007/s11263-006-9794-4 · Cited by 1,923
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
On the resemblance and containment of documents
Broder, A. Z. (2002) · Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) · doi:10.1109/sequen.1997.666900 · Cited by 1,698
M-tree: An Efficient Access Method for Similarity Search in Metric Spaces
Ciaccia, P., Patella, M., & Zezula, P. (1997) · Cited by 1,527
The pyramid match kernel: discriminative classification with sets of image features
Grauman, K., & Darrell, T. (2005) · Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 · doi:10.1109/iccv.2005.239 · Cited by 1,481
Self-citationRobust Wide Baseline Stereo from Maximally Stable Extremal Regions
Matas, J., Chum, O., Urban, M., & Pajdla, T. (2002) · Procedings of the British Machine Vision Conference 2002 · doi:10.5244/c.16.36 · Cited by 1,350
Salakhutdinov, R., & Hinton, G. (2009) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2008.11.006 · Cited by 1,246
SVM-KNN: Discriminative Nearest Neighbor Classification for Visual Category Recognition
Zhang, H., Berg, A. C., Maire, M., & Malik, J. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.301 · Cited by 1,114
Kernelized locality-sensitive hashing for scalable image search
Kulis, B., & Grauman, K. (2009) · 2009 IEEE 12th International Conference on Computer Vision · doi:10.1109/iccv.2009.5459466 · Cited by 890
Self-citationShape indexing using approximate nearest-neighbour search in high-dimensional spaces
Beis, J. S., & Lowe, D. G. (2002) · Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.1997.609451 · Cited by 879
Learning to Hash with Binary Reconstructive Embeddings
Kulis, B., & Darrell, T. (2009) · Cited by 806
Self-citationFast pose estimation with parameter-sensitive hashing
Shakhnarovich, Viola, & Darrell (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238424 · Cited by 758
Small 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
Photo tourism: exploring photo collections in 3D
Snavely, N., Seitz, S. M., & Szeliski, R. (2006) · ACM SIGGRAPH 2006 Papers on - SIGGRAPH '06 · doi:10.1145/1179352.1141964 · Cited by 696
Satisfying general proximity / similarity queries with metric trees
Uhlmann, J. K. (1991) · Information Processing Letters · doi:10.1016/0020-0190(91)90074-r · Cited by 690
Similarity estimation techniques from rounding algorithms
Charikar, M. (2002) · doi:10.1145/509961.509965 · Cited by 659
Locality-sensitive binary codes from shift-invariant kernels
Raginsky, M., & Lazebnik, S. (2009) · Cited by 600
Learning The Discriminative Power-Invariance Trade-Off
Varma, M., & Ray, D. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408875 · Cited by 520
Near Duplicate Image Detection: min-Hash and tf-idf Weighting
Chum, O., Philbin, J., & Zisserman, A. (2008) · Procedings of the British Machine Vision Conference 2008 · doi:10.5244/c.22.50 · Cited by 460
Nearest-Neighbor Methods in Learning and Vision: Theory and Practice
(2006) · The MIT Press eBooks · doi:10.7551/mitpress/4908.001.0001 · Cited by 440
Fast image search for learned metrics
Jain, P., Kulis, B., & Grauman, K. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587841 · Cited by 279
Self-citationFast Similarity Search for Learned Metrics
Kulis, B., Jain, P., & Grauman, K. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.151 · Cited by 256
Self-citationWhen is scene identification just texture recognition?
Renninger, L. W., & Malik, J. (2004) · Vision Research · doi:10.1016/j.visres.2004.04.006 · Cited by 224
Discriminant Embedding for Local Image Descriptors
Hua, G., Brown, M., & Winder, S. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408857 · Cited by 175
Boostmap: a method for efficient approximate similarity rankings
Athitsos, V., Alon, J., Sclaroff, S., & Kollios, G. (2004) · 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.2004.1315173 · Cited by 149
Kernels as features: On kernels, margins, and low-dimensional mappings
Balcan, M.-F., Blum, A. L., & Vempala, S. (2006) · Machine Learning · doi:10.1007/s10994-006-7550-1 · Cited by 124
Kernel ICA: An alternative formulation and its application to face recognition
Yang, J. J., Gao, X., Zhang, D. D., & Yang, J. (2005) · Pattern Recognition · doi:10.1016/j.patcog.2005.01.023 · Cited by 101
Proximity Distribution Kernels for Geometric Context in Category Recognition
Ling, H., & Soatto, S. (2007) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2007.4408859 · Cited by 99
Nearest neighbor search : the old, the new, and the impossible
Andoni, A. (2009) · Cited by 88
Sub-linear Indexing for Large Scale Object Recognition
Obdržálek, Š., & Matas, J. (2005) · British Machine Vision Conference (BMVC) · doi:10.5244/c.19.3 · Cited by 85
Pyramid Match Hashing: Sub-Linear Time Indexing Over Partial Correspondences
Grauman, K. L., & Darrell, T. (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.383225 · Cited by 65
Self-citationWhen is scene recognition just texture recognition?
Walker, L. L., & Malik, J. (2010) · Journal of Vision · doi:10.1167/2.7.255 · Cited by 44
Cited by
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
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
Supervised Learning of Semantics-Preserving Hash via Deep Convolutional Neural Networks
Yang, H.-F., Lin, K., & Chen, C.-S. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2666812 · Cited by 314
Large-scale retrieval for medical image analytics: A comprehensive review
Li, Z., Zhang, X., Müller, H., & Zhang, S. (2018) · Medical Image Analysis · doi:10.1016/j.media.2017.09.007 · Cited by 262
Grauman, K., & Leibe, B. (2011) · Synthesis Lectures on Artificial Intelligence and Machine Learning · doi:10.2200/s00332ed1v01y201103aim011 · Cited by 126
Self-citation
Metadata
- Authors
- Kulis, B., & Grauman, K.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2012-06
- Volume
- 34
- Issue
- 6
- Pages
- 1092-1104
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W1990537115
- Cited by
- 331
- References
- 50
- FWCI
- 18.98
- 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.