title: 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.
authors.affiliation: Electrical Engineering and Computer Science Department and the International Computer Science Institute, University of California at Berkeley, Berkeley, CA 94720, USA. kulis@eecs.berkeley.edu
authors.forename: Brian
authors.initials: B
authors.lastname: Kulis
authors.forename: Prateek
authors.initials: P
authors.lastname: Jain
authors.forename: Kristen
authors.initials: K
authors.lastname: Grauman
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016208:Databases, Factual; D006801:Humans; D007090:Image Interpretation, Computer-Assisted / Q000379:methods*; D010363:Pattern Recognition, Automated; D011187:Posture