最终，朴素的蛮力 KNN 是算法，而 kd-tree 是，所以至少在理论上，kd-tree 最终会赢得足够大的。在实践中，GPU 实现的主要常数可能有很大的不同——我们可能正在比较与 ——所以在实际问题大小上可能确实是前者胜出。$O(n^2)$$O(n \log n)$$n$$0.0001n^2$$1000n\log n$

现在，前导常量差异的原因归结为可并行性和内存访问模式。Naive KNN 具有令人尴尬的可并行性，并且可以完全使用向量化的顺序内存访问来实现。相比之下，kd-tree 自然是串行的，需要大量的条件语句和随机内存访问。像前者这样的算法可以在 GPU 上获得巨大的加速，而像后者这样的算法在 GPU 上的运行速度通常比在 CPU 上慢。

除了@richard-zang 所说的之外，您通常可以使用一些改进，例如基于位置的散列或者如果您有固定的邻居距离半径，而不是“天真的蛮力”搜索，一种常见的方法是预网格/sort 搜索空间以限制对相邻单元格的查找（常用于分子模拟，称为链接单元格列表。

• $k$: 维数。
• $n$: 点数。

具有蛮力线性扫描的朴素 KNN 是$O(kn)$对于最坏情况和平均情况。在 GPU 上运行时，加速可以（大约）一千（$10^3$）。

kd-tree 的最坏情况是$O(n)$对于完全不平衡的树和$O(n^{1−1/k})$ 对于一般情况。它几乎不能并行化，并且不能很好地支持在线/增量更新（尽管摊销时间已经足够了）。

让我们以单线程的 kd-tree 的平均情况为例。什么时候$n=2^{20}$（约 100 万）和$k=100$,（这是基于文本的分类问题的一个很好的平均情况）然后 kd-tree 在平均情况下需要大约 100 万次操作，其中线性扫描需要 1 亿次操作。考虑到 GPU 加速，然后线性比 kd-tree 快 10 倍。

我们可以看到，只有当$k$kd-tree 可以击败线性扫描非常小，但这在现实世界的问题中非常罕见。这个问题被称为维度诅咒，它导致了针对实际实现的近似最近邻 (ANN) 搜索算法的研究：例如https://arxiv.org/pdf/1702.05911.pdf。