The DOI matches its Crossref record; 61 of the 61 references it cites were found in a registry or an index.
Fast Similarity Search for Learned Metrics
Abstract
We introduce a method that enables scalable similarity search for learned metrics. Given pairwise similarity and dissimilarity constraints between some examples, we learn a Mahalanobis distance function that captures the examples' underlying relationships well. To allow sublinear time similarity search under the learned metric, we show how to encode the learned metric parameterization into randomized locality-sensitive hash functions. We further formulate an indirect solution that enables metric learning and hashing for vector spaces whose high dimensionality makes it infeasible to learn an explicit transformation over the feature dimensions. We demonstrate the approach applied to a variety of image data sets, as well as a systems data set. The learned metrics improve accuracy relative to commonly used metric baselines, while our hashing construction enables efficient indexing with learned distances and very large databases.
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
(2012) · Encyclopedia of the Sciences of Learning · doi:10.1007/978-1-4419-1428-6_5195 · Cited by 19,370
Advances in Neural Information Processing Systems 19
(2007) · The MIT Press eBooks · doi:10.52202/085713 · Cited by 15,539
Nonlinear Dimensionality Reduction by Locally Linear Embedding
Roweis, S. T., & Saul, L. K. (2000) · Science · doi:10.1126/science.290.5500.2323 · Cited by 14,965
A Global Geometric Framework for Nonlinear Dimensionality Reduction
Tenenbaum, J. B., Silva, V. D., & Langford, J. C. (2000) · Science · doi:10.1126/science.290.5500.2319 · Cited by 13,585
Advances in Neural Information Processing Systems 14: Proceedings of the 2001 Conference
(2002) · The MIT Press eBooks · doi:10.7551/mitpress/1120.001.0001 · Cited by 8,890
Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories
Lazebnik, S., Schmid, C., & Ponce, J. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.68 · Cited by 7,916
Dimensionality Reduction by Learning an Invariant Mapping
Hadsell, R., Chopra, S., & LeCun, Y. (2006) · 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 2 (CVPR'06) · doi:10.1109/cvpr.2006.100 · Cited by 5,336
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
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Weinberger, K. Q., & Saul, L. K. (2009) · Journal of Machine Learning Research · doi:10.5555/1577069.1577078 · Cited by 4,044
Robust wide-baseline stereo from maximally stable extremal regions
Matas, J., Chum, O., Urban, M., & Pajdla, T. (2004) · Image and Vision Computing · doi:10.1016/j.imavis.2004.02.006 · Cited by 3,686
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
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
A comparison of event models for naive bayes text classification
McCallum, A., & Nigam, K. (1998) · Cited by 3,289
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
Distance Metric Learning with Application to Clustering with Side-Information
Xing, E. P., Jordan, M. I., Russell, S., & Ng, A. Y. (2002) · Cited by 2,700
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
Fei-Fei, L., Fergus, R., & Perona, P. (2005) · 2004 Conference on Computer Vision and Pattern Recognition Workshop · doi:10.1109/cvpr.2004.383 · Cited by 2,502
Barker, L. (2002) · Technometrics · doi:10.1198/tech.2002.s659 · Cited by 2,477
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
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 16
Storkey, A. (2004) · neural information processing systems · Cited by 2,085
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-citation80 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
Neighbourhood Components Analysis
Goldberger, J., Hinton, G. E., Roweis, S. T., & Salakhutdinov, R. (2004) · Cited by 1,855
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Weinberger, K. Q., Blitzer, J. C., & Saul, L. K. (2005) · Cited by 1,690
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-citationRepresenting shape with a spatial pyramid kernel
Bosch, A., Zisserman, A., & Munoz, X. (2007) · Proceedings of the 6th ACM international conference on Image and video retrieval · doi:10.1145/1282280.1282340 · Cited by 1,399
Robust 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
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
Shape 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
Fast 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
Metric Learning by Collapsing Classes
Globerson, A., & Roweis, S. T. (2005) · Cited by 665
Similarity estimation techniques from rounding algorithms
Charikar, M. (2002) · doi:10.1145/509961.509965 · Cited by 659
Learning a Distance Metric from Relative Comparisons
Schultz, M., & Joachims, T. (2003) · Cited by 609
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
Learning a Mahalanobis Metric from Equivalence Constraints
Bar-Hillel, A., Hertz, T., Shental, N., & Weinshall, D. (2005) · Cited by 517
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
Mean shift based clustering in high dimensions: a texture classification example
Georgescu, Shimshoni, & Meer (2003) · Proceedings Ninth IEEE International Conference on Computer Vision · doi:10.1109/iccv.2003.1238382 · Cited by 412
Nearest-neighbor methods in learning and vision : theory and practice
Shakhnarovich, G., Indyk, P., & Darrell, T. (2005) · Cited by 399
Estimating 3D hand pose from a cluttered image
Athitsos, V., & Sclaroff, S. (2003) · 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings. · doi:10.1109/cvpr.2003.1211500 · Cited by 379
Frome, A., Singer, Y., Sha, F., & Malik, J. (2007) · 2007 IEEE 11th International Conference on Computer Vision · doi:10.1109/iccv.2007.4408839 · Cited by 347
The Pyramid Match Kernel: Efficient Learning with Sets of Features
Grauman, K. L., & Darrell, T. (2007) · doi:10.5555/1248659.1248685 · Cited by 325
Self-citationFast 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-citationImage Retrieval and Classification Using Local Distance Functions
Frome, A., Singer, Y., & Malik, J. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0057 · Cited by 193
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
Video data mining using con .gurations of viewpoint invariant regions
Šivic, J., & Zisserman, A. (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.1315071 · Cited by 153
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
Crammer, K., Keshet, J., & Singer, Y. (2002) · Cited by 122
Learning distance functions for image retrieval
Hertz, T., Bar-Hillel, A., & Weinshall, D. (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.1315215 · Cited by 117
Building kernels from binary strings for image matching
Odone, F., Barla, A., & Verri, A. (2005) · IEEE Transactions on Image Processing · doi:10.1109/tip.2004.840701 · Cited by 113
Approximate Correspondences in High Dimensions
Grauman, K. L., & Darrell, T. (2007) · The MIT Press eBooks · doi:10.7551/mitpress/7503.003.0068 · Cited by 110
Self-citationProximity 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
Learning a kernel function for classification with small training samples
Hertz, T., Bar-Hillel, A., & Weinshall, D. (2006) · International Conference on Machine Learning · doi:10.1145/1143844.1143895 · Cited by 93
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-citationConditional Random People: Tracking Humans with CRFs and Grid Filters
Taycher, L., Demirdjian, D., Darrell, T. J., & Shakhnarovich, G. (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.83 · Cited by 53
Cited by
Adapting visual category models to new domains
Saenko, K., Kulis, B., Fritz, M., & Darrell, T. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15561-1_16 · Cited by 2,847
Self-citationSupervised 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
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
Visual simultaneous localization and mapping: a survey
Fuentes-Pacheco, J., Ruiz-Ascencio, J., & Rendón-Mancha, J. M. (2015) · Artificial Intelligence Review · doi:10.1007/s10462-012-9365-8 · Cited by 883
What you saw is not what you get: Domain adaptation using asymmetric kernel transforms
Kulis, B., Saenko, K., & Darrell, T. (2011) · CVPR 2011 · doi:10.1109/cvpr.2011.5995702 · Cited by 688
Self-citation
Metadata
- Authors
- Kulis, B., Jain, P., & Grauman, K.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2009-12
- Volume
- 31
- Issue
- 12
- Pages
- 2143-2157
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2144892774
- Cited by
- 256
- References
- 61
- FWCI
- 15.39
- 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.