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