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

作     者：江锦成 吴立新 孙文彬 杨宜舟 JIANG Jin-cheng;WU Li-xin;SUN Wen-bin;YANG Yi-zhou

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

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

出 版 物：《地理与地理信息科学》 (Geography and Geo-Information Science)

年 卷 期：2013年第29卷第4期

页      码：30-34页

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

主 题 词：Voronoi K阶邻近 并行计算 MPI PVKN算法 

学科分类：081603[081603] 081802[081802] 07[理学] 08[工学] 070503[070503] 0818[工学-交通运输类] 0705[理学-地理科学类] 0816[工学-纺织类] 

核心收录：

D　O　I：10.7702/dlydlxxkx20130407

馆 藏 号：203294102...