Fast similarity search for learned metrics.

Area of Science:

• Machine Learning
• Computer Vision
• Data Mining

Background:

• Efficient similarity search is crucial for large-scale data analysis.
• Learning metric spaces from data can improve similarity comparisons.
• High dimensionality poses challenges for metric learning and search.

Purpose of the Study:

• To develop a scalable method for similarity search with learned metrics.
• To enable sublinear time similarity search under learned Mahalanobis distances.
• To address metric learning and hashing in high-dimensional vector spaces.

Main Methods:

• Learned a Mahalanobis distance function from pairwise similarity/dissimilarity constraints.
• Encoded learned metric parameterization into randomized locality-sensitive hash functions.
• Formulated an indirect solution for high-dimensional vector spaces.

Main Results:

• The learned metrics improved accuracy compared to common baselines on image and systems datasets.
• The hashing construction enabled efficient indexing with learned distances for very large databases.
• The indirect solution handled high-dimensional vector spaces effectively.

Conclusions:

• The proposed method provides scalable and accurate similarity search for learned metrics.
• Randomized locality-sensitive hashing is effective for indexing learned distance functions.
• The approach is applicable to diverse datasets, including high-dimensional ones.