我正在阅读一篇论文，他们提到他们能够使用前缀树在 O(1) 中找到单个最近邻居。我将描述一般问题，然后是经典解决方案，最后是本文中提出的解决方案：
问题：给定一个位向量列表 L（所有向量具有相同的长度）和查询位向量 q，我们想找到 q 的最近邻。距离度量是汉明距离（有多少位不同）。天真的方法是遍历列表并计算列表中每个向量与 q 之间的汉明距离，这将花费 O(N)。然而，鉴于我们将拥有数百万个非常昂贵的位向量，因此我们希望减少它。
经典解决方案：这个问题的经典解决方案是使用近似值来找到最近的邻居，从而达到 O(logN)。这样做的方法是首先按字典顺序对 L 进行排序，以便相似的位向量彼此接近。然后给定 q，我们在排序列表上应用二分搜索来获得 q 在排序列表中的位置，并在列表中获取它上面和下面的向量（因为它们是相似的排序原因）并计算它们之间的距离并选择具有最低汉明距离的那个。然而，仅仅简单地进行一次排序，我们仍然会错过许多相似的向量，因此为了尽可能多地覆盖相似的向量，我们使用了 P 个列表和 P 个混杂函数。每个混杂函数对应每个列表。然后我们将每个位向量插入到 P 中的每个列表中，然后将其位与相应的混杂函数混杂。所以我们最终得到 P 个列表，每个列表都有位向量，但位的顺序不同。我们再次按字典顺序对 P 中的每个列表进行排序。现在给定 q，我们对 P 中的每个列表应用相同的二分搜索，但这里我们之前根据我们正在访问的列表对 q 应用混杂函数。在这一步中，我们得到了与 q 最相似的向量的 P 个，因此我们最终得到了与 q 最相似的向量。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。我们再次按字典顺序对 P 中的每个列表进行排序。现在给定 q，我们对 P 中的每个列表应用相同的二分搜索，但这里我们之前根据我们正在访问的列表对 q 应用混杂函数。在这一步中，我们得到了与 q 最相似的向量的 P 个，因此我们最终得到了与 q 最相似的向量。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。我们再次按字典顺序对 P 中的每个列表进行排序。现在给定 q，我们对 P 中的每个列表应用相同的二分搜索，但这里我们之前根据我们正在访问的列表对 q 应用混杂函数。在这一步中，我们得到了与 q 最相似的向量的 P 个，因此我们最终得到了与 q 最相似的向量。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。这样我们就可以覆盖尽可能多的相似向量。通过忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。
建议的解决方案：论文中提出的这个解决方案（但没有任何解释）说我们可以使用前缀树在 O(1) 时间内获得最近的邻居。在论文中他们说他们使用了 P 个前缀树和 P 个混杂函数，其中每个混杂函数对应于每棵树。然后他们在将每个向量的比特与相应的混杂函数混杂之后，将比特向量插入到每棵树中。给定 q，我们将跳跃函数应用于与每棵树对应的 q，并从每棵树中检索与 q 最相似的向量。现在我们最终得到了从树中检索到的 P 位向量。在论文中，他们说从前缀树中获取与 q 最相似的向量是 O(1)。我真的不明白这一点，因为我知道搜索前缀树是 O(M) 其中 M 是位向量的长度。
这是我所指的论文（第 3.3.2 节）：实时 Web 上基于内容的人群检索
http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf
我也希望您能回答我与此相关的另一个问题：如何在前缀树中查找最相似的位向量以进行 NN 搜索？