两种使用局部敏感哈希查找最近邻居的算法，哪一种？

目前我正在研究如何使用局部敏感哈希来查找最近邻居。然而，当我阅读论文和搜索网络时，我发现了两种执行此操作的算法：

1-使用L个哈希表和L个随机LSH函数，从而增加两个相似文档获得相同签名的机会。例如，如果两个文档的相似度为 80%，那么它们有 80% 的机会从一个 LSH 函数获得相同的签名。但是，如果我们使用多个 LSH 函数，则从其中一个 LSH 函数获得文档相同签名的机会就更高。这种方法在维基百科中有解释，我希望我的理解是正确的：

http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search http://en.wikipedia.org/wiki/Locality-sensitive_hashing#LSH_algorithm_for_nearest_neighbor_search

2-另一种算法使用来自 Moses S. Charikar 的论文（第 5 节）中的方法，该论文名为：来自舍入算法的相似性估计技术。它基于使用一个 LSH 函数生成签名，然后对其应用 P 排列，然后对列表进行排序。其实我不太明白这个方法，希望有人能澄清一下。

我的主要问题是：为什么有人会使用第二种方法而不是第一种方法？我发现它更容易、更快。

我真的希望有人能帮忙！！！

编辑： 实际上我不确定@Raff.Edward 是否混合了“第一”和“第二”。因为只有第二种方法使用半径，而第一种方法只是使用由哈希族 F 组成的新哈希族 g。请检查维基百科链接。他们只是使用许多 g 函数来生成不同的签名，然后对于每个 g 函数都有一个相应的哈希表。为了找到一个点的最近邻居，您只需让该点通过 g 函数并检查相应的哈希表是否有冲突。因此，我将其理解为更多的功能……更多的碰撞机会。

我没有发现任何关于第一种方法的半径的提及。

对于第二种方法，他们只为每个特征向量生成一个签名，然后对其应用 P 排列。现在我们有 P 个排列列表，其中每个排列包含 n 个签名。现在，他们对 P 中的每个列表进行排序。在给定查询点 q 后，他们为其生成签名，然后对其应用 P 排列，然后对每个排列和排序的 P 列表使用二分搜索来查找最相似的签名查询 q。我在阅读了很多有关它的论文后得出了这个结论，但我仍然不明白为什么有人会使用这种方法，因为它在找到汉明距离方面似乎并不快！！！！

对我来说，我只需执行以下操作即可找到查询点 q 的最近邻居。给定一个签名列表 N，我将为查询点 q 生成签名，然后扫描列表 N 并计算 N 中每个元素与 q 签名之间的汉明距离。因此我最终会得到 q 的最近邻居。而且需要 O(N)！！！

你对第一个的理解有点偏差。碰撞发生的概率与相似度不成正比，而与是否小于预先定义的半径成正比。目标是半径内的任何物体都有很高的几率发生碰撞，半径 * (1+eps) 之外的任何物体发生碰撞的几率都很低（并且中间的区域有点模糊）。

第一种算法实际上很难实现，但是可以得到很好的结果。特别是，第一个算法适用于 L1 和 L2（以及技术上的更多）指标。

第二种算法实现起来非常简单，但根据问题的大小，简单的实现可能会占用太多内存而无法发挥作用。在这种情况下，碰撞概率与输入的相似度成正比。但是，它仅适用于余弦相似度（或基于相似度变换的距离度量。）

因此，您将使用哪一个主要取决于您为最近邻居（或任何其他应用程序）使用的距离度量。

第二个实际上比第一个更容易理解和实现，只是论文非常罗嗦。

简短版本：取一个随机向量 V 并为每个索引赋予一个独立的随机单位正态值。根据签名长度创建任意数量的向量。签名就是做矩阵向量乘积时每个索引的符号。现在，任意两个签名之间的汉明距离与各个数据点之间的余弦相似度相关。

因为您可以将签名编码为 int 数组，并使用带有位计数指令的 XOR 来非常快速地获取汉明距离，所以您可以非常快速地获得近似余弦相似度分数。

LSH 算法没有太多标准化，而且两篇论文（以及其他论文）使用不同的定义，因此有时会有点令人困惑。我最近才实现了这两种算法JSAT https://code.google.com/p/java-statistical-analysis-tool/，并且仍在努力充分理解它们。

编辑：回复您的编辑。维基百科的文章对 LSH 来说不太好。如果您阅读了原纸 http://people.csail.mit.edu/indyk/nips-nn.ps，您所说的第一种方法仅适用于固定半径。然后根据该半径创建哈希函数，并将其连接起来以增加碰撞中接近点的概率。然后，他们构建了一个系统，通过确定他们想要的 k 的最大值，然后找到最大的值，在此基础上进行 k-NN合理的他们找到第 k 个最近邻的距离。这样，半径搜索很可能会返回 k-NN 集合。为了加快速度，他们还创建了一些额外的小半径，因为密度通常不均匀，并且使用的半径越小，结果越快。

您链接的维基百科部分取自“稳定分布”部分的论文描述，该部分提供了搜索半径 r=1 的哈希函数。

对于第二篇论文，您描述的“排序”不是散列的一部分，而是更快地搜索汉明空间的单一方案的一部分。正如我所提到的，我最近实现了这个，你可以看到快速基准 I http://jsatml.blogspot.com/2013/06/cosine-similarity-locality-sensitive.html使用暴力搜索确实比朴素的神经网络方法快得多。同样，如果您需要 L2 或 L1 距离上的余弦相似度，您也可以选择此方法。您会发现许多其他论文提出了不同的方案来搜索签名创建的汉明空间。

如果您需要帮助来说服自己，即使您仍在使用蛮力，拟合也会更快 - 只需这样看：假设平均稀疏文档与另一个文档有 40 个常见单词（根据我的经验，这是一个非常保守的数字）。您有 n 个文档可供比较。强力余弦相似度将涉及大约 40*n 浮点乘法（以及一些额外的工作）。如果您有 1024 位签名，则只有 32 个整数。这意味着我们可以在 32*n 整数运算中进行强力 LSH 搜索，这比浮点运算快得多。

这里还有其他因素在起作用。对于稀疏数据集，我们必须保留双精度和整数索引来表示非零索引，因此稀疏点积会执行大量额外的整数运算来查看它们有哪些共同索引。 LSH 还允许我们节省内存，因为我们不需要为每个向量存储所有这些整数和双精度数，相反我们可以只保留它的散列 - 这只有几个字节。 减少内存使用可以帮助我们更好地利用CPU缓存。

你的 O(n) 是我在博客文章中使用的天真的方式。而且速度很快。但是，如果您事先对位进行排序，则可以在 O(log(n)) 中进行二分搜索。即使你有 L 个这样的列表，L