In this note, we show that one can use average embeddings, introduced recently in [Naor'20, arXiv:1905.01280], to obtain efficient algorithms for approximate nearest neighbor search. In particular, a metric $X$ embeds into $\ell_2$ on average, with distortion $D$, if, for any distribution $\mu$ on $X$, the embedding is $D$ Lipschitz and the (square of) distance does not decrease on average (wrt $\mu$). In particular existence of such an embedding (assuming it is efficient) implies a $O(D^3)$ approximate nearest neighbor search under $X$. This can be seen as a strengthening of the classic (bi-Lipschitz) embedding approach to nearest neighbor search, and is another application of data-dependent hashing paradigm.

翻译：在本说明中,我们表明,人们可以使用最近在[Naor'20, arXiv:1905.01280] 中引入的平均嵌入器,以获得近邻搜索的有效算法。特别是,如果任何分配款按X美元计算,嵌入器用Lipschitz美元和(平方)距离平均不减少(售出 $\ mu$ ), 则可以使用平均嵌入器,以获得约近邻搜索所需的有效算法。 特别是,如果存在这种嵌入器(假设有效),则意味着大约近邻搜索用$(D3)在X美元以下。 这可被视为对近邻搜索的经典(Bi-Lipschitz)嵌入法的强化,也是依赖数据的集水模式的另一种应用。