给定d维空间中的n个点，有几种数据结构，如Kd树、四叉树等来索引这些点。在这些数据结构上，可以实现针对给定输入点附近的最近邻居查询的直接算法。有没有书、论文、调查。。。比较不同数据结构上最近邻居查询的理论运行时间（主要是预期的）？我正在查看的数据是由相当小的点云组成的，所以它们都可以在主内存中处理。为了简单起见，我假设数据是均匀分布的。也就是说，我对现实世界的性能不感兴趣，而是对理论结果
你让点的维度未定义，你只给出点数量的近似值。小是什么意思？一个人所说的小是相对的。
当然，你搜索的内容并不存在。你的问题大致是：
问题：
对于一个小数据集（无论小对你来说意味着什么），任何维度的数据都遵循均匀分布，使用什么样的最佳数据结构
答案：
没有这样的数据结构
对此有一个答案不是太奇怪了吗？一个错误的类比是，把大多数一年级本科生都有的"哪种是最佳编程语言？"问题作为这个问题的同义词。你的问题没有那么天真，但它走在同一条轨道上。
为什么没有这样的数据结构？
因为，数据集的维度是可变的。这意味着，你可能有一个二维数据集，但也可能意味着你有一个1000维的数据集，或者更好的是，有一个小于1000的内在维度的1000维数据集。想一想，有人能提出一个数据结构，对我提到的三个数据集表现同样好吗？我对此表示怀疑。
事实上，有些数据结构在低维中表现非常好（例如四叉树和KD树），而其他数据结构在高维中表现得更好（例如RKD树森林）。
此外，用于最近邻居搜索的算法和期望在很大程度上取决于数据集的维度（以及数据集的大小和查询的性质（例如，距离数据集太远或与数据集的点等距的查询可能会导致搜索性能变慢）。
在较低的维度中，将执行k近邻（k-NN）搜索。在更高的维度中，执行k-近似NN搜索将是更明智的。在这种情况下，我们遵循以下权衡：
速度与精度
结果是，我们通过牺牲结果的正确性来实现程序的更快执行。换句话说，我们的搜索例程将相对较快，但它可能（这种可能性取决于许多参数，例如问题的性质和您正在使用的库）不是返回真实的NN，而是精确NN的近似值。例如，它可能找不到确切的NN，但找到了查询点的第三个NN。您也可以检查近似的nn搜索wiki标记。
为什么不总是搜索确切的NN？由于维度诅咒，这导致在较低维度中提供的解决方案表现得与暴力一样好（为每个查询搜索数据集中的所有点）。
你看，我的答案已经很大了，所以我应该到此为止。我必须承认，你的问题太宽泛了，但很有趣
总之，使用哪种数据结构（和算法）将取决于您的问题。您正在处理的数据集的大小、点的维度和内在维度起着关键作用。查询的数量和性质也起着重要作用
对于潜在非均匀点数据的最近邻搜索，我认为kd树通常会给您带来最佳性能。就广泛的概述和理论成本分析而言，我认为维基百科是一个不错的起点，但请记住，它没有涵盖太多现实世界的优化：
http://en.wikipedia.org/wiki/Nearest_neighbor_search
http://en.wikipedia.org/wiki/Space_partitioning
理论上的表现是一回事，而现实世界的表现则完全是另一回事。真实世界的性能取决于数据结构实现的细节和数据结构的类型。例如，由于改进了缓存一致性和更快的数据分配，无指针（紧凑阵列）实现可以比基于指针的实现快很多倍。如果您利用SIMD同时测试多个分支，那么更宽的分支在理论上可能较慢，但在实践中可能较快。
此外，点数据的确切性质也会对性能产生重大影响。均匀分布要求较低，可以用更简单的数据结构快速处理。非均匀分布需要更多的注意。（Kd树适用于统一和非统一数据。）此外，如果您的数据太大，无法在核心中处理，那么与较小的数据集相比，您需要采取完全不同的方法。