在局部敏感散列中搜索
Search in locality sensitive hashing
我正在尝试理解 this paper 的第 5 部分关于 LSH 的内容，特别是如何对生成的哈希值进行存储。引用链接的论文：
Given bit vectors consisting of d bits each, we choose N = O(n 1/(1+epsilon)
) random permutations of the bits. For each random permutation σ, we
maintain a sorted order O σ of the bit vectors, in lexicographic order
of the bits permuted by σ. Given a query bit vector q, we find the
approximate nearest neighbor by doing the following: For each permu-
tation σ, we perform a binary search on O σ to locate the two bit
vectors closest to q (in the lexicographic order ob- tained by bits
permuted by σ). We now search in each of the sorted orders O σ
examining elements above and below the position returned by the binary
search in order of the length of the longest prefix that matches q.
This can be done by maintaining two pointers for each sorted order O σ
(one moves up and the other down). At each step we move one of the
pointers up or down corresponding to the element with the longest
matching prefix. (Here the length of the longest matching prefix in O
σ is computed relative to q with its bits permuted by σ). We examine
2N = O(n 1/(1+epsilon) ) bit vec- tors in this way. Of all the bit vectors
examined, we return the one that has the smallest Hamming distance to
q.
我对这个算法感到困惑，我不认为我理解它是如何工作的。
我已经 this question on the topic, but I didn't understand the answer in the comments. Also in this 发现第 2 点中描述了相同算法的问题，但同样，我不明白它是如何工作的。
你能试着逐步向我解释它是如何工作的吗？尽量简单一点？
我什至试图列出我不明白的东西，但实际上写得太糟糕了，以至于我看不懂大部分句子！
在 gsamaras 回答后编辑：
答案基本看懂了，但还有点疑惑：
执行 N 排列的总成本是 O(Nnlogn) 是否正确，因为我们必须对每个排列进行排序？
上述的排列+排序过程在预处理时只执行一次还是针对every查询q？即使在预处理中，它似乎已经相当昂贵 O(Nnlogn)，如果我们必须在查询时执行此操作，那将是一场灾难 :D
在最后一点，我们将 v0 和 v4 与 q 进行比较，我们比较它们的置换版本或原始版本（在置换之前） ?
这个问题有些宽泛，所以我在这里只举一个最小的（抽象的）例子：
我们的数据集中有 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
现在我们向上或向下移动指针，寻找与 q 匹配最多位的 vi 向量。假设它是 v0.
类似地，我们进行第二次排列，找到向量 vi，假设为 v4。我们现在比较第一个排列的 v0 和 v4，看看哪个最接近 q，即哪个有最多等于 q.
的位
编辑:
Is it correct to say that the total cost of performing the N permutations is O(Nnlogn), since we have to sort each one of them?
如果他们真的从头开始对每个排列进行排序，那么是，但我不清楚他们是如何做到的。
The permutation+sorting process described above is performed only once during the pre-processing or for every query q?
一次.
At the last point, where we compare v0 and v4 to q, we compare their permuted version or the original one (before their permutation)?
我 认为 他们使用置换版本来实现（请参阅论文中 2N 之前的括号）。但这没有任何区别，因为它们也使用相同的排列 (σ).
排列 q
这个 quora answer 也能说明一些问题。
我正在尝试理解 this paper 的第 5 部分关于 LSH 的内容，特别是如何对生成的哈希值进行存储。引用链接的论文：
Given bit vectors consisting of d bits each, we choose N = O(n 1/(1+epsilon) ) random permutations of the bits. For each random permutation σ, we maintain a sorted order O σ of the bit vectors, in lexicographic order of the bits permuted by σ. Given a query bit vector q, we find the approximate nearest neighbor by doing the following: For each permu- tation σ, we perform a binary search on O σ to locate the two bit vectors closest to q (in the lexicographic order ob- tained by bits permuted by σ). We now search in each of the sorted orders O σ examining elements above and below the position returned by the binary search in order of the length of the longest prefix that matches q. This can be done by maintaining two pointers for each sorted order O σ (one moves up and the other down). At each step we move one of the pointers up or down corresponding to the element with the longest matching prefix. (Here the length of the longest matching prefix in O σ is computed relative to q with its bits permuted by σ). We examine 2N = O(n 1/(1+epsilon) ) bit vec- tors in this way. Of all the bit vectors examined, we return the one that has the smallest Hamming distance to q.
我对这个算法感到困惑，我不认为我理解它是如何工作的。
我已经 this question on the topic, but I didn't understand the answer in the comments. Also in this 发现第 2 点中描述了相同算法的问题，但同样，我不明白它是如何工作的。
你能试着逐步向我解释它是如何工作的吗？尽量简单一点？
我什至试图列出我不明白的东西，但实际上写得太糟糕了，以至于我看不懂大部分句子！
在 gsamaras 回答后编辑：
答案基本看懂了，但还有点疑惑：
执行
N排列的总成本是O(Nnlogn)是否正确，因为我们必须对每个排列进行排序？上述的排列+排序过程在预处理时只执行一次还是针对every查询
q？即使在预处理中，它似乎已经相当昂贵O(Nnlogn)，如果我们必须在查询时执行此操作，那将是一场灾难 :D在最后一点，我们将
v0和v4与q进行比较，我们比较它们的置换版本或原始版本（在置换之前） ?
这个问题有些宽泛，所以我在这里只举一个最小的（抽象的）例子：
我们的数据集中有 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
现在我们向上或向下移动指针，寻找与 q 匹配最多位的 vi 向量。假设它是 v0.
类似地，我们进行第二次排列，找到向量 vi，假设为 v4。我们现在比较第一个排列的 v0 和 v4，看看哪个最接近 q，即哪个有最多等于 q.
编辑:
Is it correct to say that the total cost of performing the N permutations is O(Nnlogn), since we have to sort each one of them?
如果他们真的从头开始对每个排列进行排序，那么是，但我不清楚他们是如何做到的。
The permutation+sorting process described above is performed only once during the pre-processing or for every query
q?
一次.
At the last point, where we compare
v0andv4toq, we compare their permuted version or the original one (before their permutation)?
我 认为 他们使用置换版本来实现（请参阅论文中 2N 之前的括号）。但这没有任何区别，因为它们也使用相同的排列 (σ).
q
这个 quora answer 也能说明一些问题。