gpt4 book ai didi

algorithm - 二维快速k-最近邻搜索的数据结构和算法的合适选择

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:21:43 25 4
gpt4 key购买 nike

我有一个大约 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/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com