使用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搜索的前缀树中查找最相似的位向量？
我认为论文中的论点是，如果它是O（f（x））那么x必须是树中存储的项目数，而不是维数。 正如你所指出的，对于前缀树，时间上升为O（M），其中M是位向量的长度，但如果你认为M是固定的，你感兴趣的是行为作为项目的数量树增加你有O（1）。
顺便说一句，Muja和Lowe的论文“快速近似最近邻居和自动算法配置”也将基于树的竞争者视为LSH。 这里的想法似乎是随机化树构造，创建多个树，并对每棵树进行快速但粗略的搜索，选择在任何树中找到的最佳答案。
这只是一个非常松散定义的O(1) 。 事实上，我会在这种情况下挑战他们的用法。
从他们的论文来看，为了确定用户的最近邻居， u 。
- “我们首先计算它的签名，
u”：可以是O(1)取决于“签名” - “然后对于
P每个前缀树 ”：哦，哦，听起来不是O(1)，O(P)会更正确。 - 迭代部分来自2.“…我们在前缀树中找到最近的签名， 通过一次迭代树一层… ”：最好的情况
O(d)其中d是树的深度或长度这个词。 （这很慷慨，因为找到前缀树中最近的点可能比这更多） - “这样做之后……我们最终选择了
|P|签名…其中选择了最小的汉明距离”：所以另一个P计算乘以单词的长度。O(Pd)。
更准确地说，总运行时间是O(1) + O(P)+ O(Pd) + O(Pd) = O(Pd)
我相信@mcdowella在他们如何尝试制作这个O(1)分析中是正确的，但是根据我所读到的，他们并没有说服我。
我假设它们在树中引用了P的节点，并且可以导航到O（1）摊销时间中的下一个或上一个条目。 即技巧是访问底层节点。