基于MapReduce的多机并行DP算法与实验分析

摘要：

随着网络地图不断发展,个性化网络地图也得到快速发展.个性化网络地图需要以矢量数据为数据基础,以满足人们对地图色彩、符号等个性化要求,所以需要实时、快速进行大量数据化简.本文以经典Douglas-Peucker算法作为曲线化简算法,利用开源云计算平台Hadoop建立多机协作的曲线并行化简服务框架,设计和实现了多机并行Douglas-Peucker算法,并在集群上进行实验分析,验证算法的效率和适用性.算法核心是设计数据的逻辑分片,利用MapReduce计算原理,将分片分配到集群中,实现并行运算.实验分别分为两个方面:(1)比较在固定阈值不同数据量情况下,传统DP算法与多机并行DP算法效率;(2)比较在相同数据量不同阈值情况下,传统DP算法与多机并行DP算法效率.实验表明,在大数据量和高复杂度情况下,多机并行DP算法的效率更高.

关键词：多机并行DP算法、Douglas-Peucker算法、曲线化简、MapReduce

所属期刊栏目：15

资助基金：国家自然科学基金项目41101448,51008138;中央高校自主科研项目274737;中国博士后科学基金项目2011M501230

在线出版日期：2013-12-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：55-60