基于MapReduce的空间数据并行划分算法

doi:10.13474/j.cnki.11-2246.2017.0356

测绘通报 ›› 2017, Vol. 0 ›› Issue (11): 96-100.doi: 10.13474/j.cnki.11-2246.2017.0356

基于MapReduce的空间数据并行划分算法

付艳丽^1,2, 吴艳民³, 张金标⁴, 郑坤², 赵长虹³, 郑康^2,5, 方发林^2,5

1. 济南市勘察测绘研究院, 山东济南 250013;
2. 中国地质大学(武汉)信息工程学院, 湖北武汉 430074;
3. 北京创时空科技发展有限公司, 北京 100083;
4. 广东省气象探测数据中心, 广东广州 510610;
5. 武汉兆图科技有限公司, 湖北武汉 430070

收稿日期:2017-05-16 出版日期:2017-11-25 发布日期:2017-12-07
通讯作者: 张金标。E-mail:zhangjb@grmc.gov.cn E-mail:zhangjb@grmc.gov.cn
作者简介:付艳丽(1988-),女,硕士,工程师,主要从事GIS开发工作。E-mail:fuyli@126.com
基金资助:
国家重点研发计划（2016YFB0502603）；湖北省自然科学基金（ZRY2015001543）；中国地质大学（武汉）中央高校基本科研业务费资金（1610491B20）

Spatial Data Parallel Partitioning Algorithm Based on MapReduce

FU Yanli^1,2, WU Yanmin³, ZHANG Jinbiao⁴, ZHENG Kun², ZHAO Changhong³, ZHENG Kang^2,5, FANG Falin^2,5

1. Jinan Geotechnical Investigation and Surverying Institute, Jinan 250013, China;
2. School of Information Engineering, China University of Geosciences(Wuhan), Wuhan 430074, China;
3. Beijing Create Space-time Science and Technology Limited Company, Beijing 100083, China;
4. Guangdong Meteorological Observation Data Center, Guangzhou 510610, China;
5. Wuhan Trillion Map Technology Limited Company, Wuhan 430070, China

Received:2017-05-16 Online:2017-11-25 Published:2017-12-07

摘要/Abstract

摘要： 针对海量空间数据分布式存储中存在的不顾及空间邻近性、分布不均和数据倾斜的问题，基于MapReduce并行编程模型，对Hilbert空间曲线层次分解的思想和节点容量感知的方法进行了研究，提出了一种层次分解的空间数据并行划分策略，并通过临界值判定实现空间数据的均衡存储。最后通过实例分析说明该方法可以在保证空间数据邻近特性的同时，解决海量空间数据分布式存储不均和数据倾斜的问题。

关键词: MapReduce, Hilbert空间曲线, 空间数据并行划分

Abstract: Spatial data partitioning method plays an important role in spatial data distributed storage, and its key problem is how topartition spatial data to distributed storage nodes in network environment. This paper discusses massive spatial data partitioning strategies and analyses their disadvantages which these partitioning methods have not taken into account spatial object size and spatial proximity. Aiming at these questions,this paper proposes a new spatial data parallelpartitioning strategy based on MapReduce and capacity-aware method to improve load balance which could avoid unevenly distributed data storage and data skew. Experimental analysis shows that the presented spatial data parallel partitioning algorithm not only achieves better storage load balance in distributed storage system,but also keeps well spatial locality of data objects after partitioning.

Key words: MapReduce, Hilbert space filling curve, spatial data parallel partitioning

中图分类号:

P208

付艳丽, 吴艳民, 张金标, 郑坤, 赵长虹, 郑康, 方发林. 基于MapReduce的空间数据并行划分算法[J]. 测绘通报, 2017, 0(11): 96-100.

FU Yanli, WU Yanmin, ZHANG Jinbiao, ZHENG Kun, ZHAO Changhong, ZHENG Kang, FANG Falin. Spatial Data Parallel Partitioning Algorithm Based on MapReduce[J]. 测绘通报, 2017, 0(11): 96-100.

参考文献

[1] 赵春宇,孟令奎,林志勇. 一种面向并行空间数据库的数据划分算法研究[J]. 武汉大学学报(信息科学版), 2006, 31(11):962-965.
[2] ZHENG K, GU D, FANG F, et al. Data Storage Optimi-zation Strategy in Distributed Column-oriented Database by Considering Spatial Adjacency[J]. Cluster Computing, 2017:1-12.
[3] SHEKHAR S, CHAWL S. 空间数据库[M]. 北京:机械工业出版社,2004.
[4] 陆锋,周成虎. 一种基于空间层次分解的Hilbert码生成算法[J]. 中国图象图形学报,2001,6(5):465-469.
[5] 周艳, 朱庆, 张叶廷, 基于Hilbert曲线层次分解的空间数据划分方法[J]. 地理与地理信息科学, 2007,23(4):13-17.
[6] CARY A, SUN Zhengguo, HRISTIDIS V,et al.Experiences on Processing Spatial Data with MapReduce[C]//21st International Conference on Scientific and Statistical Database Management. Berlin:Springer, 2009.
[7] CARY A, YESHA Y, ADJOUADI M, et al. Leveraging Cloud Computing in Geodatabase Management[C]//2010 IEEE 16th International Conference on Parallel and Distributed Systems (ICPADS).[S.l.]:ICPADS, 2010:73-78.
[8] DEAN J,GHEMAWAT S. MapReduce:Simplified Data Processing on Large Clusters[J]. Conference on Symposium on Opearting System Design and Implementation, 2014, 51(1):10.
[9] ABDELBAKY M,KIM H,RODERO I,et al. Accelerating MapReduce Analytics UsingCometCloud[C]//2012 IEEE 5th International Conference on Cloud Computing.[S.l.]:IEEE, 2012:447-454.
[10] BENDAHMANE A,ESSAAIDI E, MOUSSAOUI A E, et al. A New Mechanism to Ensure Integrity for MapReduce in Cloud Computing[C]//2012 International Conference on Multimedia Computing and Systems (ICMCS).[S.l.]:ICMCS, 2012:785-790.
[11] LI F, OOI B C, WU S. Distributed Data Management Using MapReduce[J]. ACM Computing Surveys, 2014, 46(3):1-42.
[12] 王凯,曹建成,王乃生,等.Hadoop支持下的地理信息大数据处理技术初探[J].测绘通报,2015(10):114-117.
[13] 曹雪峰,万刚,张宗佩.紧致的Hilbert曲线Gray码索引算法[J]. 测绘学报, 2016, 45(S1):90-98.
[14] 付仲良,胡玉龙,翁宝凤,等. M-Quadtree索引:一种基于改进四叉树编码方法的云存储环境下空间索引方法[J]. 测绘学报, 2016,45(11):1342-1351.
[15] 周敬利,周正达.改进的云存储系统数据分布策略[J]. 计算机应用,2012, 32(2):309-312.
[16] 陈德军,高晓军,王义飞. 基于AHP的云存储负载均衡研究[J]. Computer Engineering and Applications, 2015, 51(7):56-60.
[17] ELDAWY A, MOKBEL M F. SpatialHadoop:A MapReduce Framework for Spatial Data[C]//2015 IEEE 31st International Conference on Data Engineering (ICDE).[S.l.]:IEEE, 2015:1352-1363.

基于MapReduce的空间数据并行划分算法

Spatial Data Parallel Partitioning Algorithm Based on MapReduce

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

本文评价

[1]	周琦, 杜晓, 张俊辉, 郑义, 林尚纬, 万咏涛. 并行处理技术在全球海量地理信息数据质量控制中的应用[J]. 测绘通报, 2020, 0(7): 29-33.
[2]	范建永龙明熊伟. 基于Hadoop的云GIS体系结构研究[J]. 测绘通报, 2013, 0(11): 93-97.