基于MapReduce的多机并行DP算法与实验分析
Research on Multi-machine Parallel DP Algorithm Based on MapReduce
查看参考文献19篇
|
文摘
|
随着网络地图不断发展,个性化网络地图也得到快速发展。个性化网络地图需要以矢量数据为数据基础,以满足人们对地图色彩、符号等个性化要求,所以需要实时、快速进行大量数据化简。本文以经典Douglas-Peucker算法作为曲线化简算法,利用开源云计算平台Hadoop建立多机协作的曲线并行化简服务框架,设计和实现了多机并行Douglas-Peucker算法,并在集群上进行实验分析,验证算法的效率和适用性。算法核心是设计数据的逻辑分片,利用MapReduce计算原理,将分片分配到集群中,实现并行运算。实验分别分为两个方面:(1)比较在固定阈值不同数据量情况下,传统DP算法与多机并行DP算法效率;(2)比较在相同数据量不同阈值情况下,传统DP算法与多机并行DP算法效率。实验表明,在大数据量和高复杂度情况下,多机并行DP算法的效率更高。 |
|
其他语种文摘
|
Real time and rapid simplification of large-scale data, required by personalized WebGIS service which is based on vector data, becomes more and more important. The study was based on Douglas-Peucker, one of classical curve simplification algorithms, but in the view of its low performance, it can hardly simplify large-scale data in real time and rapidly. At the same time, the development of cloud-computing offers new storage technologies and computational methods for real time and rapid simplification of large-scale data. So this study made use of hadoop, one of the open source cloud computing platforms, to design and realize multi-machine parallel Douglas-Peucker algorithm. In the algorithm, we deigned the logic slices of data, and assigned the slices to the clusters by MapReduce computing model, achieved parallel simplification. In order to verify the efficiency of the algorithm, we designed the experiments and compared the efficiency of traditional DP algorithm and multi-machine parallel DP algorithm in tow aspects: 1) the same threshold and different amount of data; and 2) the fixed amount of data and different thresholds. The (result of the experiments showed: the multi-machine parallel DP algorithm was more efficient than tradition DP algorithm for large-scale data and high-complexity computing. In this case, the data processing time was much longer than the data allocated in the inter-cluster and the transmission time, and every node was involved in a certain operation, improved the efficiency of operations. But for small scale data and low-complexity computing, the advantage of multi-machine parallel DP algorithm was non-obvious. Mainly due to a part of the nodes didn't participate in the operation, the computing potential of the cluster was not full play, while the data processing required time was very short, so the data allocation and transmission time impacted obviously. And, in order to meet the real time and rapid simplification of large-scale data, the multi-machine parallel DP algorithm should choose the appropriate simplification method for different amount of data and complexity computing in future. |
|
来源
|
地球信息科学学报
,2013,15(1):55-60 【核心库】
|
|
关键词
|
多机并行DP算法
;
Douglas-Peucker算法
;
曲线化简
;
MapReduce
|
|
地址
|
1.
武汉大学卫星导航技术研究中心, 地理信息系统教育部重点实验室, 武汉, 430079
2.
武汉大学资源与环境科学学院, 地理信息系统教育部重点实验室, 武汉, 430079
3.
武汉大学卫星导航技术研究中心, 武汉, 430079
|
|
语种
|
中文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
1560-8999 |
|
学科
|
地球物理学 |
|
基金
|
国家自然科学基金
;
中央高校自主科研项目
;
中国博士后科学基金
|
|
文献收藏号
|
CSCD:4760551
|
参考文献 共
19
共1页
|
|
1.
蔡晓桦. 云计算及其在地理信息系统中的应用.
江西测绘,2012(1):39-41
|
CSCD被引
1
次
|
|
|
|
|
2.
郭庆胜. 线状要素图形综合的渐进方法研究.
武汉测绘科技大学学报,1998,23(1):52-56
|
CSCD被引
20
次
|
|
|
|
|
3.
Li Z L. 基于客观综合自然规律的线状要素自动综合的算法.
武测译文,1994(1):49-58
|
CSCD被引
10
次
|
|
|
|
|
4.
Buttenfield B P. Digital definitions of scale-dependent structure.
Auto-Carto,1986:497-506
|
CSCD被引
1
次
|
|
|
|
|
5.
艾廷华. 曲线弯曲深度层次结构的二叉树表达.
测绘学报,2001(4):343-348
|
CSCD被引
59
次
|
|
|
|
|
6.
应申. 基于约束点的曲线一致性化简.
武汉大学学报·信息科学版,2003(4):488-491
|
CSCD被引
14
次
|
|
|
|
|
7.
任海艳. 一种基于遗传算法的曲线化简方法.
测绘通报,2012(10):32-35
|
CSCD被引
2
次
|
|
|
|
|
8.
Douglas D H. Algorithms for the reduction of the number of points required to represent a digitized line or its character.
The Canadian Cartographer,1973,10(2):112-123
|
CSCD被引
306
次
|
|
|
|
|
9.
毋河海. 基于多叉树结构的曲线综合算法.
武汉大学学报·信息科学版,2004(6):479-483
|
CSCD被引
16
次
|
|
|
|
|
10.
张胜. Douglas-Peucker算法的改进及应用.
武汉理工大学学报·交通运输与工程版,2005(5):671-674
|
CSCD被引
12
次
|
|
|
|
|
11.
陈轶. 基于Douglas双侧多叉树的曲线综合算法研究.
测绘学报,2010(3):310-315
|
CSCD被引
11
次
|
|
|
|
|
12.
马劲松. 利用Douglas-Peucker并行算法在多核处理器上实时综合地图线要素.
武汉大学学报·信息科学版,2011(12):1423-1426
|
CSCD被引
8
次
|
|
|
|
|
13.
Lin C.
Principles of parallel programming,2008
|
CSCD被引
3
次
|
|
|
|
|
14.
Andrade D. Task-parallel versus data-parallel library-based programming in multicore systems.
Euromicro International Conference on Parallel,2009
|
CSCD被引
1
次
|
|
|
|
|
15.
White T.
Hadoop: The definitive huide (Second Edition),2011
|
CSCD被引
1
次
|
|
|
|
|
16.
Lam C.
Hadoop in action,2010
|
CSCD被引
8
次
|
|
|
|
|
17.
Dean J. MapReduce: Simplified data processing on large clusters.
OSDI,2004
|
CSCD被引
1
次
|
|
|
|
|
18.
王鹏.
走近云计算,2009
|
CSCD被引
5
次
|
|
|
|
|
19.
张传明. 保持拓扑一致性的等高线化简算法研究.
北京大学学报(自然科学版),2007(2):216-222
|
CSCD被引
10
次
|
|
|
|
|
了解气象卫星更多信息，请访问