• Goal: – Maintain query time guarantees while performing approximate search with a learned metric. • Main idea: – Learn Mahalanobis distance parameterization. – Use it to