A Bi-metric Framework for Fast Similarity Search
summary
Proposes a bi-metric pipeline that builds indices with a cheap proxy (Euclidean embeddings, sketched) and queries with an expensive ground-truth (cross-encoder / large ML model), proving DiskANN and Cover Tree can be adapted so final approximation is arbitrarily close to 1 while paying a query/space blowup (cost scales with distortion c). Empirically on MTEB text retrieval the modified DiskANN cuts expensive metric calls by factors like ~4× (example: ~8k → ~2k) and improves the accuracy–efficiency tradeoff versus standard reranking. proxy vs ground-truth gap spans multiple orders of magnitude.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 0:54Problem definitions
- 1:58Relaxation techniques
- 7:43Filtering and reranking
- 11:56Challenges and goals
- 16:12Theoretical framework
- 24:20Practical evaluation
- 31:28Discussion and conclusions
related talks
41mSemantic Multimodal Multilingual Similarity Engine
41mFrom Embeddings To Index: A Practitioner's Guide To Domain-Adapted Neural Search
19mHow to look at your data
01h 09mVector Search: Ask Me Anything!
30mFuzzy Matching at Scale
37mSimilarity Search for Product Matching @ Semantics3
49mMetric Representations: Algorithms and Geometry
43mMetric Learning for Individual Fairness