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

编号 zgly0001607422

文献类型 期刊论文

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

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

作者单位 北京师范大学民政部/教育部减灾与应急管理研究院  中国矿业大学物联网(感知矿山)国家地方联合工程实验室  东北大学测绘遥感与数字矿山研究所  中国矿业大学(北京)地球科学与测绘工程学院 

母体文献 地理与地理信息科学 

年卷期 2013年04期

年份 2013 

分类号 P208 

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

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