A Bi-metric Framework for Fast Similarity Search

Haike Xu, Sandeep Silwal, Piotr Indyk

We propose a new "bi-metric" framework for designing nearest neighbor data structures. Our framework assumes two dissimilarity functions: a ground-truth metric that is accurate but…