A Bi-metric Framework for Fast Similarity Search
This work addresses efficiency challenges in nearest neighbor search for applications like text retrieval, offering a novel framework that improves tradeoffs without being a paradigm shift.
The paper tackles the problem of fast similarity search by proposing a bi-metric framework that uses a cheap proxy metric to construct data structures, achieving the accuracy of an expensive ground-truth metric with limited computational calls. It demonstrates this through theoretical guarantees for algorithms like DiskANN and Cover Tree, and empirically shows a better accuracy-efficiency tradeoff on the MTEB benchmark compared to alternatives like re-ranking.
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 expensive to compute, and a proxy metric that is cheaper but less accurate. In both theory and practice, we show how to construct data structures using only the proxy metric such that the query procedure achieves the accuracy of the expensive metric, while only using a limited number of calls to both metrics. Our theoretical results instantiate this framework for two popular nearest neighbor search algorithms: DiskANN and Cover Tree. In both cases we show that, as long as the proxy metric used to construct the data structure approximates the ground-truth metric up to a bounded factor, our data structure achieves arbitrarily good approximation guarantees with respect to the ground-truth metric. On the empirical side, we apply the framework to the text retrieval problem with two dissimilarity functions evaluated by ML models with vastly different computational costs. We observe that for almost all data sets in the MTEB benchmark, our approach achieves a considerably better accuracy-efficiency tradeoff than the alternatives, such as re-ranking.