我有一个大约 100,000 个（X，Y）对的数据集，表示 2D 空间中的点。对于每个点，我想找到它的 k 最近邻。
所以，我的问题是——假设我想绝对最小化整体运行时间，什么样的数据结构/算法是合适的选择？
我不是在寻找代码 - 只是指向合适方法的指针。我对似乎相关的选择范围感到有点害怕——四叉树、R-树、kd-树等。
我认为最好的方法是构建一个数据结构，然后对每个点运行某种 k-最近邻搜索。但是，由于（a）我事先知道这些点，并且（b）我知道我必须对每个点只运行一次搜索，也许有更好的方法？
一些额外的细节：
如果 k 相对较小（<20 左右）并且您具有大致均匀的分布，请创建一个网格覆盖点所在的范围，选择该网格以使每个网格的平均点数高于 k（这样 a位于中心的点通常会在该网格点中获得其 k 个邻居）。然后创建一组其他网格，从第一个（重叠）沿每个轴设置一半。现在对于每个点，计算它落入哪个网格元素（因为网格是规则的，不需要搜索）并选择四个（或你拥有的许多重叠网格）中的一个，该点最靠近其中心。
在每个网格元素中，点应该在一个坐标中排序（比如说 x）。从您选择的元素开始（使用二分法找到它），沿着排序列表向外走，直到找到 k 个项目（同样，如果 k 很小，维护 k 个最佳匹配列表的最快方法是使用二进制插入排序，让最差的匹配在您插入时从最后消失；插入排序通常在现代硬件上击败其他所有内容，最多约 30 个项目）。继续前进，直到您最远的最近邻居比 x 中距离您的下一个点更靠近您（即不计算它们的 y 偏移量，因此可能没有新点比迄今为止发现的第 k 个最近点更接近） .
如果您还没有 k 个点，或者您有 k 个点，但网格元素的一个或多个墙比 k 个点中最远的点更靠近您的兴趣点，则将相关的相邻网格元素添加到搜索中。
这应该为您提供类似 的性能O(N*k^2)，具有相对较低的常数因子。如果 k 很大，那么这个策略太简单了，你应该选择一个在 k 中是线性或对数线性的算法，就像 kd-trees 一样。