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