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

作者：江锦成; 吴立新; 孙文彬; 杨宜舟

来源：地理与地理信息科学, 2013, (04): 30-34.

• Voronoi
• K阶邻近
• 并行计算
• MPI
• PVKN算法 Voronoi
• K-order neighbors
• parallel computing
• MPI
• PVKN alg orithm

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

• 出版日期2013
• 单位中国矿业大学（北京）; 中国矿业大学; 东北大学; 北京师范大学