java - 使用前缀树在 O(1) 中查找单个最近邻居？

Question

我正在读一篇论文，其中提到他们能够使用前缀树在 O(1) 中找到单个最近邻居。我将描述一般问题，然后描述经典解决方案，最后描述论文中提出的解决方案:

问题:给定一个位 vector 列表 L(所有 vector 具有相同的长度)和查询位 vector q，我们希望找到 q 的最近邻。距离度量是汉明距离(有多少位不同)。最简单的方法是遍历列表并计算列表中每个 vector 与 q 之间的汉明距离，这将需要 O(N)。然而，考虑到我们将拥有数百万个位 vector ，这是非常昂贵的，因此我们希望减少它。

经典解决方案: 该问题的经典解决方案是使用近似值来查找最近邻，从而实现 O(logN)。做到这一点的方法是首先按字典顺序对 L 进行排序，以便相似的位 vector 将彼此接近。然后给定 q，我们对排序列表应用二分搜索来获取 q 在排序列表中的位置，并获取列表中位于其上方和下方的 vector (因为它们在排序方面是相似的)并计算之间的距离，并选择汉明距离最小的那个。然而，仅仅简单地进行一次排序，我们仍然会错过许多相似的 vector ，因此为了覆盖尽可能多的相似 vector ，我们使用 P 个列表和 P 个混杂函数。每个混杂函数对应于每个列表。然后，在使用相应的混杂函数对其位进行混杂后，我们将每个位 vector 插入到 P 中的每个列表中。所以我们最终得到 P 列表，每个列表都有位 vector ，但位的顺序不同。我们再次按字典顺序对 P 中的每个列表进行排序。现在给定 q，我们对 P 中的每个列表应用相同的二分搜索，但这里我们之前根据我们正在访问的列表将 jumbling 函数应用于 q。在这一步中，我们得到了 P 个与 q 最相似的 vector ，因此我们最终得到了与 q 最相似的一个。这样我们就可以覆盖尽可能多的相似 vector 。忽略排序所需的时间，找到最近邻居所需的时间为 O(log n)，即对每个列表进行二分查找的时间。

建议的解决方案: 论文中提出的解决方案(但没有任何解释)表示我们可以使用前缀树在 O(1) 时间内获得最近邻居。他们在论文中表示，他们使用 P 个前缀树和 P 个混杂函数，其中每个混杂函数对应于每棵树。然后，在使用相应的混杂函数对每个 vector 的位进行混杂后，将位 vector 插入到每棵树中。给定 q，我们将跳跃函数应用于每棵树对应的 q，并从每棵树中检索与 q 最相似的 vector 。现在我们最终得到从树中检索到的 P 位 vector 。他们在论文中表示，从前缀树中获取与 q 最相似的 vector 的时间复杂度为 O(1)。我真的完全不明白这一点，因为我知道搜索前缀树是 O(M)，其中 M 是位 vector 的长度。有人明白为什么是 O(1) 吗？

这是我引用的论文(第 3.3.2 节):实时网络上基于内容的人群检索

http://students.cse.tamu.edu/kykamath/papers/cikm2012/fp105-kamath.pdf

我也希望您能回答我与此相关的其他问题:How to lookup the most similar bit vector in an prefix tree for NN-search?

Answer 1

我认为论文中的论点是，如果它是 O(f(x)) 那么 x 必须是存储在树中的项目数，而不是维度数。正如您所指出的，对于前缀树，时间会增加为 O(M)，其中 M 是位 vector 的长度，但如果您认为 M 是固定的并且您感兴趣的是作为中的项目数的行为树的增加时间复杂度为 O(1)。

顺便说一句，Muja 和 Lowe 的论文“使用自动算法配置快速近似最近邻”也考虑了 LSH 的基于树的竞争对手。这里的想法似乎是随机化树的构造，创建多棵树，并对每棵树进行快速但粗略的搜索，选择在任何树中找到的最佳答案。