Tag: 最近邻居

使用O(1)中的前缀树查找单个最近邻居?

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