这是一个根据k-d树的维数和我写的蛮力的执行速度图。
指针集的数目固定为1 M（1000000），Query测量了执行1000次的速度。
K-D树的增长是巨大的，但蛮力不是。
我想知道为什么会有这些结果，以及如何改进这些结果。
最佳答案
一些想法：
性能在很大程度上取决于数据的特性例如，数据点是否均匀分布、聚集或以其他方式排列？
另外，您正在执行的查询类型是什么？一种解释是，您使用的窗口查询返回整个点集或其大部分。在这种情况下，暴力总是会更快。
kd树实现中是否存在缺陷？
一般来说，kd树在高维情况下不具有很好的伸缩性。因此，例如在机器学习中，维数通常被减少到10到20左右。但是，除非你在gpu上使用蛮力，否则kd-tree应该更快。
如果您正在寻找更适合高维度（插入/窗口查询）的结构，请查看R*Trees或PH-Tree（后者是自发布的，目前仅限于60个维度，但高维度版本将在本周发布）。对于k近邻搜索，请查看CoverTrees或BallTrees如果您使用的是Java，那么可以查看my repo中的实现我还实现了R*Tree here。