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

Parallel Search Algorithm for Voronoi K-order Neighbors of Points

作　　者：江锦成[1] 吴立新[1,2,3] 孙文彬[4] 杨宜舟[3] 

机构地区：[1]北京师范大学民政部/教育部减灾与应急管理研究院,北京100875 [2]中国矿业大学物联网(感知矿山)国家地方联合工程实验室,江苏徐州221008 [3]东北大学测绘遥感与数字矿山研究所,辽宁沈阳110819 [4]中国矿业大学(北京)地球科学与测绘工程学院,北京100083

出　　处：《地理与地理信息科学》2013年第4期30-34,共5页Geography and Geo-Information Science

基　　金：国家863计划项目(2011AA120302)

摘　　要：K阶邻近在空间层次聚类、空间邻近分析、DEM内插等方面有着广泛应用,然而传统的串行算法无法满足大规模数据集快速搜索K阶邻近的需求。该文在分析V图-K阶邻近串行搜索算法特点的基础上,提出了一种基于MPI的并行搜索算法——PVKN(Parallel Voronoi K-order Neighbors)算法,分别对V图构建和K阶邻近搜索进行并行化,并通过实验对算法进行测试。结果表明:当求解单源点目标的K阶邻近时,构建V图的时间远远大于搜索K阶邻近的用时,仅对构建V图过程进行并行化,即可获得良好的加速效果;当对多源点目标进行求解时,搜索K阶邻近的时间随着K阶数和源目标数的增加而增长,成为影响PVKN算法效率的主要因素,对K阶邻近搜索过程进行并行化,PVKN算法加速比可达5倍以上,能有效降低运行时间。K-order neighbor relation has been applied to many fields, such as space hierarchical clustering, spatial neighbor analysis,DEM interpolation, etc. The traditional serial algorithms cannot meet the demand of searching K-order neighbors quickly for big quantity of spatial data. In this paper, the present situation of K-order neighbors search algorithms is reviewed and then a parallel algorithm-PVKN （Parallel Voronoi K-order Neighbor） algorithm is presented, which parallelizes the main steps, including constructing Voronoi diagrams and searching K-order neighbors. PVKN algorithm in parallel computing environment is tested, and the experimental results demonstrate that it takes most of the time to construct Voronoi diagrams when searching the neighbors of single source point;but with increasing of the number of source points and K-order, the procedure of searching Voronoi-based K-order neighbors takes longer time. This paper shows that PVKN algorithm can get obvious accelerating effect after computing the above two procedures in parallel.

关 键 词：VORONOI K阶邻近 并行计算 MPI PVKN算法 

分 类 号：P208[天文地球—地图制图学与地理信息工程]