点集V图-K阶邻近并行搜索算法设计与实验

摘要

K阶邻近在空间层次聚类、空间邻近分析、DEM内插等方面有着广泛应用,然而传统的串行算法无法满足大规模数据集快速搜索K阶邻近的需求。该文在分析V图-K阶邻近串行搜索算法特点的基础上,提出了一种基于MPI的并行搜索算法——PVKN(Parallel Voronoi K-order Neighbors)算法,分别对V图构建和K阶邻近搜索进行并行化,并通过实验对算法进行测试。结果表明:当求解单源点目标的K阶邻近时,构建V图的时间远远大于搜索K阶邻近的用时,仅对构建V图过程进行并行化,即可获得良好的加速效果;当对多源点目标进行求解时,搜索K阶邻近的时间随着K阶数和源目标数的增加而增长,成为影响PVKN算法效率的主要因素,对K阶邻近搜索过程进行并行化,PVKN算法加速比可达5倍以上,能有效降低运行时间。