CHEN Chaoyin,CHEN Gongyan,LI Yanjun,et al.An Algorithmic Optimization Study of k-nearest Neighbor Space Interpolation[J].Journal of Chengdu University of Information Technology,2023,38(02):148-153.[doi:10.16836/j.cnki.jcuit.2023.02.004]
k近邻空间插值算法优化研究
- Title:
- An Algorithmic Optimization Study of k-nearest Neighbor Space Interpolation
- 文章编号:
- 2096-1618(2023)02-0148-06
- 分类号:
- TP301.6
- 文献标志码:
- A
- 摘要:
- 在k近邻空间插值中,如果能减少近邻点的搜索次数,可进一步提高空间插值的性能。引入k近邻距离阈值的概念和计算方法,并以该阈值为基础,发展了k+M优化算法。其算法核心是在空间插值过程中,获取初始栅格的k+M近邻点集,计算k+M近邻距离阈值。若从初始栅格向右移动至其他栅格的距离小于该阈值,则直接利用初始栅格的近邻点集进行空间插值。实验证明,该算法相对于每个栅格均搜索近邻点的算法,性能有明显的提升。
- Abstract:
- For the k-nearest-neighbor spatial interpolation algorithm, the performance of spatial interpolation can be further improved if the number of searches for nearest-neighbor points can be reduced. In this paper, the concept and calculation method of the k-nearest neighbor distance threshold is proposed first, and based on it the k+M optimization algorithm is developed. The key part of the k+M optimization algorithm is obtaining the k+M nearest neighbor points of the initial grid in the process of spatial interpolation, and calculating the k+M nearest neighbor distance threshold. If the moving distance of the initial grid is less than the set threshold, the spatial interpolation can be performed directly using the nearest neighbor points of the initial grid. Experimentally, compared with the algorithm of searching the nearest neighbor points for each raster,the performance of the algorithm used in this paper is significantly improved and its research results have certain theoretical significance and practical value.
参考文献/References:
[1] 王映辉.一种GIS自适应层次网格空间索引算法[J].计算机工程与应用,2003(9):58-60.
[2] 彭召军,王青山,熊伟,等.基于改进四叉树的地理实体快速查询算法[J].地理空间信息,2017,(1):32-35.
[3] Yang Y,Bai P,Ge N,et al.LAZY R-tree:The R-tree with lazy splitting algorithm[J].Journal of Information Science,2019,46(1).
[4] Jin P,Xie X,Wang N,et al.Optimizing R-tree for flash memory[J].Expert Systems with Applications,2015,42(10):4676-4686.
[5] Mumák,P Gurskí.R++-Tree:An Efficient Spatial Access Method for Highly Redundant Point Data[J].Advances in Intelligent Systems & Computing,2014,241:37-44.
[6] Qin-Yang W U.Improved R*-tree spatial index: Improved R*-tree spatial index[J].Journal of Computer Applications,2010,30(2):419-422.
[7] Stanoi I,Riedewald M,Agrawal D,et al.Discovery of Influence Sets in Frequently Updated Databases[J].Vldb,2001:99-108.
[8] Goodsell G.On finding p-th nearest neighbours of scattered points in two dimensions for small p[J].Computer Aided Geometric Design,2000,17(4):387-392.
[9] Dickerson M T,Drysdale R S,Sack J.SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS[J].International Journal of Computational Geometry & Applications,1992,2(3):9200014.
[10] 张涛,张定华,王凯,等.空间散乱点k近邻搜索的新策略[J].机械科学与技术,2008(10):1233-1235.
[11] 刘宇,朱仲英,施颂椒.空间k近邻查询的新策略[J].上海交通大学学报,2001(9):1298-1302.
[12] Abu-Aisheh Z,Raveaux R,Ramel J Y.Fast Nearest Neighbors Search in Graph Space Based on a Branch-and-Bound Strategy[J].Springer,Cham,2017.
[13] 廖巍,熊伟,王钧,等.可伸缩的增量连续k近邻查询处理[J].软件学报.2007(2):268-278.
[14] Cheema M A,Lin X,Zhang W,et al.Influence Zone:Efficiently Processing Reverse k Nearest Neighbors Queries[C].Data Engineering(ICDE),2011 IEEE 27th International Conference on.IEEE,2011.
[15] Wang H,Zhao W L,Zeng X.Large-Scale Approximate k-NN Graph Construction on GPU[J].2021.
[16] 田盼,华蓓,陆李.基于GPU的K-近邻算法实现[J].计算机工程,2015(2):189-192.
备注/Memo
收稿日期:2022-04-15
基金项目:西藏自治区自然科学基金资助项目(XZ202101ZR0042G)
通信作者:陈宫燕.E-mail:chengongyan_35@163.com