我试图理解本文有关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回答后编辑：
我大部分都知道答案，但是我仍然有一些疑问：
说执行N置换的总成本是正确的O(Nnlogn)，因为我们必须对每个置换进行排序？
N
O(Nnlogn)
上述的排列+排序过程在预处理期间或对于 每个 查询仅执行一次q。O(Nnlogn)即使在预处理中，它似乎已经非常昂贵，如果我们必须在查询时执行此操作，那将是一场灾难：D
q
在最后一点，我们与v0和v4进行比较q，我们比较它们的排列版本或原始版本（在排列之前）？
v0
v4
这个问题在某种程度上是广泛的，所以在这里我将给出一个最小的（抽象的）示例：
我们n的数据集中有6个（= ）向量，d每个向量都有位。假设我们进行2（= N）个随机排列。
n
d
让第一个随机置换开始！请记住，我们置换 位 ， 而不是向量的次序 。在对位进行排列后，它们保持顺序，例如：
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。
一次 。
我 认为 他们使用置换版本（请参阅2N本文前面的括号）来完成此操作。但这没有什么区别，因为它们q也使用相同的置换（σ）进行置换。
2N
σ
这个法定答案也可能会有所启发。
