computational-geometry - Locality Sensitive Hashing (LSH) 中的 ε (epsilon) 参数是什么？

Question

我已经阅读了关于 Locality Sensitive Hashing的原始论文。

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

你能解释一下它的含义吗？

Answer 1

ε 是近似参数。

LSH（作为FLANN和kd-GeRaF）是为高维数据设计的。在那个空间中，k-NN不能很好地工作，实际上它几乎和蛮力一样慢，因为维度的诅咒。

出于这个原因，我们专注于解决近似的k-NN。检查我们论文中的定义 1 ，它基本上说返回一个近似邻居是可以的，它位于 (1 + ε) 比精确邻居更远的距离内。

检查下图：

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

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