局部敏感哈希(LSH)中的ε(ε)参数是什么? [英] What is the ε (epsilon) parameter in Locality Sensitive Hashing (LSH)?

问题描述

我已经阅读了有关以下内容的原始论文本地敏感哈希.

I've read the original paper about Locality Sensitive Hashing.

复杂度取决于参数ε的函数，但我不知道它是什么.

The complexity is in function of the parameter ε, but I don't understand what it is.

您能解释一下它的意思吗?

Can you explain its meaning please?

推荐答案

ε是近似参数.

LSH(如法兰& k-NN 效果不佳，实际上几乎由于 curse，速度与蛮力一样慢维度.

LSH (as 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.

因此，我们专注于解决 近似 k- NN .从我们的纸张中检查定义1，该定义基本上说可以返回位于其中的近似邻居(1 +ε)比确切的邻居更远.

For that reason, we focus on solving the aproximate k-NN. Check Definition 1 from our paper, which basically say that it's OK to return an approximate neighbor lying in (1 + ε) further distance than the exact neighbor.

检查下面的图像:

在这里您看到找到精确/近似NN的含义.在传统的NNS(最近邻搜索)问题中，我们被要求找到确切的NN.在现代问题中，近似NNS要求我们在(1 +ε)半径内找到一些邻居，因此精确或近似NN都是有效的答案！

here you see what does it mean finding the exact/approximate NN. In the traditional problem of NNS (Nearest Neighbor Search), we are asked to find the exact NN. In the modern problem, the approximate NNS, we are asked to find some neighbor inside the (1+ε) radius, thus either the exact or approximate NN would be a valid answer!

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

So, with a high probability, LSH will return a NN inside that (1+ε) radius. For ε = 0, we actually solve the exact NN problem.

这篇关于局部敏感哈希(LSH)中的ε(ε)参数是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！