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

Question

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

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

能解释一下它的含义吗？

Answer 1

ε 是近似参数。

LSH(如 FLANN 和 kd-GeRaF )专为高维数据而设计。在那个空间里，k-NN效果不佳，事实上它几乎和暴力一样慢，因为 curse of dimensionality .

因此，我们专注于解决 aproximate k-NN 。从我们的 paper 检查定义 1 ，这基本上是说可以返回比精确邻居距离 (1 + ε) 更远的近似邻居。

检查下面的图片:

在这里您可以看到找到精确/近似的神经网络意味着什么。在传统的 NNS(最近邻搜索)问题中，我们被要求找到精确的 NN。在现代问题中，近似 NNS，我们被要求在 (1+ε) 半径内找到一些邻居，因此精确或近似 NN 都是有效答案!

因此，LSH 很可能会在 (1+ε) 半径内返回一个 NN。对于 ε = 0，我们实际上解决了精确的神经网络问题。