2

我试图理解本文关于 LSH 的第 5 节，特别是如何存储生成的哈希。引用链接的论文：

给定每个由 d 位组成的位向量，我们选择 N = O(n 1/(1+epsilon) ) 位的随机排列。对于每个随机排列 σ，我们维护位向量的排序顺序 O σ，按照由 σ 排列的位的字典顺序。给定一个查询位向量 q，我们通过执行以下操作找到近似最近邻： 对于每个排列 σ，我们对 O σ 执行二进制搜索，以定位最接近 q 的两个位向量（按获得的字典顺序）由 σ 置换的位）。我们现在按照与 q 匹配的最长前缀的长度的顺序在每个排序顺序 O σ 中搜索由二分搜索返回的位置上方和下方的元素。这可以通过为每个排序顺序 O σ 维护两个指针来完成（一个向上移动，另一个向下移动）。在每一步中，我们向上或向下移动与具有最长匹配前缀的元素相对应的指针之一。（这里 O σ 中最长匹配前缀的长度是相对于 q 计算的，其位由 σ 置换）。我们以这种方式检查 2N = O(n 1/(1+epsilon) ) 位向量。在检查的所有位向量中，我们将具有最小汉明距离的位向量返回到 q。

我对这个算法感到困惑，我认为我不明白它是如何工作的。

我已经在该主题上找到了这个问题，但我不明白评论中的答案。同样在第 2 点的这个问题中，描述了相同的算法，但同样，我不明白它是如何工作的。

你能试着向我解释它是如何工作的，并尽可能地简单吗？

我什至试着把我看不懂的东西列个清单，但实际上写得太糟糕了，我看不懂大部分句子！

在 gsamaras 回答后编辑：

我基本上明白了答案，但我仍然有一些疑问：

  1. 是否正确地说执行N排列的总成本是O(Nnlogn)，因为我们必须对它们中的每一个进行排序？

  2. 上述排列+排序过程在预处理期间或每个查询中只执行一次q？O(Nnlogn)即使在预处理中，它似乎已经相当昂贵，如果我们必须在查询时这样做，那将是一场灾难：D

  3. 在最后一点，我们比较v0和v4，q我们比较它们的置换版本还是原始版本（在它们置换之前）？

4

1 回答 1

3

这个问题有点宽泛，所以我在这里只给出一个最小（抽象）的例子：

我们的数据集中有 6 个 (= n) 向量，d每个向量都有位。假设我们做了 2 (= N) 次随机排列。

让第一个随机排列开始！请记住，我们置换的是位，而不是向量的顺序。排列位后，它们保持顺序，例如：

v1
v5
v0
v3
v2
v4

现在查询向量q到达了，但它（几乎）不太可能与我们数据集中的向量相同（在排列之后），因此我们不会通过执行二分搜索找到它。

然而，我们最终会在两个向量之间结束。所以现在我们可以想象这个场景是这样的（例如q位于 v0 和 v3 之间：

v1
v5
v0 <-- up pointer
   <-- q lies here
v3 <-- down pointer
v2
v4

现在我们向上或向下移动指针，寻找与 匹配最多位的 vi 向量q。假设它是 v0。

类似地，我们进行第二次置换，我们找到向量 vi，比如说 v4。我们现在比较第一个排列中的 v0 和 v4，看看哪个最接近q，即哪个具有最多等于 的位q。

编辑：

说执行 N 个排列的总成本是 O(Nnlogn) 是否正确，因为我们必须对它们中的每一个进行排序？

如果他们真的从头开始对每个排列进行排序，那么是的，但我不清楚他们是如何做到的。

上述排列+排序过程在预处理期间或每个查询中只执行一次q？

一次。

在最后一点，我们比较v0和v4，q我们比较它们的置换版本还是原始版本（在它们置换之前）？

我认为他们使用置换版本来做到这一点（参见2N论文前面的括号）。但这不会有任何区别，因为它们q也使用相同的置换 ( σ) 置换。

这个quora的答案也可能会有所启发。

于 2016-05-22T21:26:40.387 回答