局部敏感哈希 (LSH) 中的 ε (epsilon) 参数是什么？

Question

我已阅读 original paper 关于局部敏感哈希的文章。

复杂度是参数ε的函数，但我不明白它是什么。

能解释一下它的意思吗？

Answer 1

ε为近似参数.

LSH（如 FLANN & kd-GeRaF) is designed for high dimensional data. In that space, k-NN doesn't work well, in fact it is almost as slow as brute force, because of the curse of dimensionality.

出于这个原因，我们专注于解决 aproximate k-NN. Check Definition 1 from our paper，这基本上是说可以 return 一个比精确邻居更远 (1 + ε) 距离的近似邻居。

查看下图：

在这里你明白找到 exact/approximate NN 是什么意思。在 NNS（最近邻搜索）的传统问题中，我们被要求找到确切的 NN。在现代问题中，近似 NNS，我们被要求在 (1+ε) 半径内找到一些邻居，因此精确或近似 NN 将是一个有效的答案！

因此，LSH 很有可能会 return 在该 (1+ε) 半径内的 NN。对于 ε = 0，我们实际上解决了精确的 NN 问题。