由于kd树最大半径，在最近邻搜索中出现了意外的减速。

Question

由于kd树最大半径，在最近邻搜索中出现了意外的减速。

3

我正在使用kd-tree算法（在此处找到）来查找矩阵1中某个点相对于矩阵2中所有点的最近邻。上述算法非常快，能够在大约20秒内找到300万个最近邻。

nn2(SetA,SetB,k=1)

现在，我只想包括在彼此一定半径内的最近邻，所以我尝试使用以下代码：

nn2(SetA,SetB,k=1,searchtype='radius',radius=1000)

这种方法虽然有效，但会使计算速度变得极其缓慢，实际上可能会慢几个数量级（1000倍或更多）。我不明白为什么会出现这种情况，因为在我的理解中，最大半径实际上应该可以减少计算时间，因为不需要扫描整个空间。

有人能解释一下是怎么回事吗？或者为什么会出现这种情况？

以下是可重现此问题的示例代码：

library(data.table)
library(RANN)
N=50000
DT1=data.table(x=sample(0:300,N,replace=T),y=sample(301:600,N,replace=T))
DT2=data.table(x=sample(0:300,N,replace=T),y=sample(301:600,N,replace=T))

ptm=proc.time()
nnlistV1=nn2(DT1,DT2,k=1)
proc.time()-ptm

ptm=proc.time()
nnlistV2=nn2(DT1,DT2,k=1,searchtype="radius",radius=20)
proc.time()-ptm

- Michiel

听起来确实很奇怪。那么libnabo呢？ - greybeard

似乎是正在进行数据转换或nn2使用了一种低效的算法。我的建议是查看定义nn2的源文件rbind.R，并对复杂度进行分析。 - user2210287

制作一个类似于您真实数据集的代码将会很有帮助。 - ARobertson

@ARobertson 好观点，我刚刚添加了能够重现该行为的代码。 - Michiel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ARobertson · Accepted Answer

从ANN手册中可以看到，

因为它逐个访问搜索半径内的所有点，所以如果半径内点的数量很大，则搜索过程效率相对较低。

我没有查看所有代码，但annkSearch是您的第一个nn2最终调用的标准代码，而annkFRSearch（FR = Fixed Radius）是上面提到的慢速代码。半径版本不是标准的限制，它是完全不同的。

运行此代码显示在尝试找到k = 1时，“半径范围内的点数很大”。

nrow(DT1[DT1$x >= 130 & DT1$x <= 170, ])
[1] 6711

运行一个更适合于固定半径搜索的问题，采样范围更分散，k值大于1但略小于范围内可能找到的点数：

N=50000
DT1=data.table(x=sample(0:30000,N,replace=T),y=sample(301:60000,N,replace=T))
DT2=data.table(x=sample(0:30000,N,replace=T),y=sample(301:60000,N,replace=T))

nrow(DT1[DT1$x >= 130 & DT1$x <= 170, ])
# I got 70 on my random sample
ptm=proc.time()
nnlistV1=nn2(DT1,DT2,k=50)
proc.time()-ptm

ptm=proc.time()
nnlistV2=nn2(DT1,DT2,k=50,searchtype="radius",radius=400)
proc.time()-ptm

你的代码给了我0.11和1.81的时间。通过以上更改，我分别得到标准和半径为0.69和0.28的时间。