Embeddings into Similarity Measures for Nearest Neighbor Search

We introduce the notion of metric embeddings into a similarity measure over $\mathbb{R}_{+}^{m}$, such as the weighted Jaccard coefficient. We develop average embeddings into such similarity measures for a number of metric spaces, with (appropriately defined) distortion that is smaller than the best possible or known distortion of embedding into $\ell_{1}$ or $\ell_{2}$ spaces (biLipschitz or average). We complement our embeddings with a new algorithm for Approximate Nearest Neighbor Search (ANNS) that leverages such an embedding in a black box fashion. Combining these results, we obtain new efficient algorithms for ANNS under the following two classic metrics, achieving an exponential improvement to longstanding prior work: - Edit distance over length- k strings: $\operatorname{poly}(\log k)$ approximation; - $\ell_{p}$ over $\mathbb{R}^{d}$, for $p\gt2: O(\log p)$ approximation (known to be asymptotically optimal in relevant models of computation).