Parallel Algorithm for Partitioning Massive Spatial Vector Data in Cloud Environment

YAO Xiaochuang; YANG Jianyu; LI Lin; YE Sijing; YUN Wenju; ZHU Dehai

doi:10.13203/j.whugis20160271

Volume 43 Issue 7

Jul. 2018

Turn off MathJax

Article Contents

Abstract

References

Geomatics and Information Science of Wuhan University > 2018 > 43(7): 1092-1097. > DOI: 10.13203/j.whugis20160271

YAO Xiaochuang, YANG Jianyu, LI Lin, YE Sijing, YUN Wenju, ZHU Dehai. Parallel Algorithm for Partitioning Massive Spatial Vector Data in Cloud Environment[J]. Geomatics and Information Science of Wuhan University, 2018, 43(7): 1092-1097. DOI: 10.13203/j.whugis20160271

Citation:

PDF (3435 KB)

Parallel Algorithm for Partitioning Massive Spatial Vector Data in Cloud Environment

YAO Xiaochuang^{1, 2, 3,},
YANG Jianyu^{1, 2},
LI Lin^{1, 2},
YE Sijing³,
YUN Wenju^{1, 2, 4},
ZHU Dehai^{1, 2, ,}

1.
College of Information and Electrical Engineering, China Agricultural University, Beijing 100083, China
2.
Key Laboratory for Agriculture Land Quality, Monitoring and Control of the Ministry of Land and Resources, Beijing 100035, China
3.
Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, Beijing 100094, China
4.
Land Consolidation and Rehabilitation Center, Ministry of Land and Resources, Beijing 100035, China

Funds:

The Special Fund for Scientific Research of Public Welfare Industry of Ministry of Land and Resources 201511010-06

More Information

Author Bio:
YAO Xiaochuang, PhD, specializes in spatial big data. E-mail:xcyao@cau.edu.cn
Corresponding author:
ZHU Dehai, PhD, professor. E-mail:dehaizhu@qq.com
Received Date: February 04, 2017
Published Date: July 04, 2018

Graphical Abstract

Abstract

Abstract

Spatial data partitioning plays an important role in the spatial index methods and the data storage strategy for spatial big data. In this paper, to make up the inherent shortcomings of spatial data partitioning and data storage in the Hadoop cloud computing platform, a parallel algorithm based on Hilbert space-filling curve is presented for partitioning the massive spatial vector data. In the spatial vector data partitioning phase, we take more influence factors, including the spatial location relationship between adjacent objects, the size of spatial vector object itself, the number of spatial objects in the same spatial coded block and others, into full consideration. Meanwhile, by following the partitioning principle of merging small coded blocks and sub-splitting large coded blocks, this paper implements the parallel algorithm for partitioning the massive spatial vector data in cloud environment. Experimental results show that the algorithm proposed in this paper can not only improve the efficiency of the spatial R-tree index for massive spatial vector data, but also give a good data balance in Hadoop distributed file system (HDFS).
- vector data,
- Hilbert code,
- spatial data partitioning,
- MapReduce,
- R-tree index,
- data skewness

FullText(HTML)

References (13)

References

[1]	陆锋, 周成虎.一种基于空间层次分解的Hilbert码生成算法[J].中国图象图形学报, 2001, 6(5):465-469 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB200105009.htm Lu Feng, Zhou Chenghu. An Algorithm for Hilbert Ordering Code Based on Spatial Hierarchical Decomposition[J]. Journal of Image and Graphics, 2001, 6(5):465-469 http://www.cnki.com.cn/Article/CJFDTOTAL-ZGTB200105009.htm
[2]	郭晶, 刘广军, 董绪荣, 等.基于空间网格和Hilbert R-tree的二级R-tree空间索引[J].武汉大学学报·信息科学版, 2005, 30(12):1084-1088 http://ch.whu.edu.cn/CN/abstract/abstract2346.shtml Guo Jing, Liu Guangjun, Dong Xurong, et al. 2-Level R-tree Spatial Index Based on Spatial Grids and Hilbert R-tree[J]. Geomatics and Information Science of Wuhan University, 2005, 30(12):1084-1088 http://ch.whu.edu.cn/CN/abstract/abstract2346.shtml
[3]	戴晶, 吴明光, 郑培蓓, 等.基于Hilbert曲线的STR索引改进算法[J].武汉大学学报·信息科学版, 2014, 39(7):777-781 http://ch.whu.edu.cn/CN/abstract/abstract3019.shtml Dai Jing, Wu Mingguang, Zheng Peibei, et al. An Improved STR-tree Spatial Index Algorithm Based on Hilbert-curve[J]. Geomatics and Information Science of Wuhan University, 2014, 39(7):777-781 http://ch.whu.edu.cn/CN/abstract/abstract3019.shtml
[4]	赵春宇, 孟令奎, 林志勇.一种面向并行空间数据库的数据划分算法研究[J].武汉大学学报·信息科学版, 2006, 31(11):962-965 http://ch.whu.edu.cn/CN/abstract/abstract2590.shtml Zhao Chunyu, Meng Lingkui, Lin Zhiyong. Spatial Data Partitioning Towards Parallel Spatial Database System[J]. Geomatics and Information Science of Wuhan University, 2006, 31(11):962-965 http://ch.whu.edu.cn/CN/abstract/abstract2590.shtml
[5]	王永杰, 孟令奎, 赵春宇.基于Hilbert空间排列码的海量空间数据划分算法研究[J].武汉大学学报·信息科学版, 2007, 32(7):650-653 http://ch.whu.edu.cn/CN/abstract/abstract1940.shtml Wang Yongjie, Meng Lingkui, Zhao Chunyu. Spatial Partitioning of Massive Data Based on Hilbert Spatial Ordering Code[J]. Geomatics and Information Science of Wuhan University, 2007, 32(7):650-653 http://ch.whu.edu.cn/CN/abstract/abstract1940.shtml
[6]	周艳, 朱庆, 张叶廷.基于Hilbert曲线层次分解的空间数据划分方法[J].地理与地理信息科学, 2007, 23(4):13-17 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dlxygtyj200704004 Zhou Yan, Zhu Qing, Zhang Yeting. A Spatial Data Partitioning Algorithm Based on Spatial Hierarchical Decomposition Method of Hilbert Space-Filling Curve[J]. Geography and Geo-Information Science, 2007, 23(4):13-17 http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=dlxygtyj200704004
[7]	熊炼, 徐正全, 王涛, 等.云环境下的时空数据小文件存储策略[J].武汉大学学报·信息科学版, 2014, 39(10):1252-1256 http://ch.whu.edu.cn/CN/abstract/abstract3105.shtml Xiong Lian, Xu Zhengquan, Wang Tao, et al. On the Store Strategy of Small Spatio-Temporal Data Files in Cloud Environment[J]. Geomatics and Information Science of Wuhan University, 2014, 39(10):1252-1256 http://ch.whu.edu.cn/CN/abstract/abstract3105.shtml
[8]	张晓祥.大数据时代的空间分析[J].武汉大学学报·信息科学版, 2014, 39(6):655-659 http://ch.whu.edu.cn/CN/abstract/abstract3010.shtml Zhang Xiaoxiang. Spatial Analysis in the Era of Big Data[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6):655-659 http://ch.whu.edu.cn/CN/abstract/abstract3010.shtml
[9]	徐文, 邵俊, 喻文勇, 等.陆地观测卫星数据中心:大数据挑战及一种解决方案[J].武汉大学学报·信息科学版, 2017, 42(1):7-13 http://ch.whu.edu.cn/CN/abstract/abstract5648.shtml Xu Wen, Shao Jun, Yu Wenyong, et al. Land Observing Satellite Data Center:Big Data Challenges and a Potential Solution[J]. Geomatics and Information Science of Wuhan University, 2017, 42(1):7-13 http://ch.whu.edu.cn/CN/abstract/abstract5648.shtml
[10]	Eldawy A, Mokbel M F. Spatial Hadoop: A Map Reduce Framework for Spatial Data[C]. IEEE 31st International Conference on Data Engineering, Seoul, Korea, 2015
[11]	Eldawy A, Alarabi L, Mokbel M F. Spatial Partitioning Techniques in Spatial Hadoop[C]. The International Conference on Very Large Databases, VLDB 2015, Kohala Coast, Hawaii, 2015
[12]	李勋. 基于Hilbert划分的并行矢量数据索引算法研究[D]. 成都: 电子科技大学, 2013 Li Xun. Parallel Spatial Index Algorithm Based on Hilbert Partition[D]. Chengdu: University of Electronic Science and Technology of China, 2013
[13]	何小苑, 闵华清.基于聚类的Hilbert R-树空间索引算法[J].计算机工程, 2009, 35(9):40-42 http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y1692977 He Xiaoyuan, Min Huaqing. Hilbert R-tree Spatial Index Algorithm Based on Clustering[J]. Computer Engineering, 2009, 35(9):40-42 http://www.wanfangdata.com.cn/details/detail.do?_type=degree&id=Y1692977

[1]	ZHAO Binbin, XIE Jianxiang, ZHANG Hongkui, WANG Liwei, WANG Qian. Geographic Line Extraction Algorithm Based on Morphing Transformation Techniques[J]. Geomatics and Information Science of Wuhan University, 2025, 50(1): 174-183. DOI: 10.13203/j.whugis20220493
[2]	WANG Pengxin, CHEN Chi, ZHANG Yue, ZHANG Shuyu, LIU Junming. Estimation of Winter Wheat Yield Using Assimilated Bi-variables and PCA-Copula Method[J]. Geomatics and Information Science of Wuhan University, 2022, 47(8): 1201-1212. DOI: 10.13203/j.whugis20220038
[3]	XIE Yanxin, WU Xiaocheng, HU Xiong. Using One-Dimensional Variational Assimilation Algorithm to Obtain Atmospheric Refractive Index from Ground-Based GPS Phase Delay[J]. Geomatics and Information Science of Wuhan University, 2018, 43(7): 1042-1047. DOI: 10.13203/j.whugis20160238
[4]	LI Jingzhong, ZHANG Jinming. A Morphing Method for Smooth Area Features Based on Fourier Transform[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1104-1109. DOI: 10.13203/j.whugis20150157
[5]	OU Ming, ZHEN Weimin, XU Jisheng, YU Xiao, LIU Yiwen, LIU Dun. Regional Ionospheric TEC Reconstruction by Data Assimilation Technique[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8): 1075-1081. DOI: 10.13203/j.whugis20150297
[6]	WANG Hongwei, HUANG Chunlin, HOU Jinliang, LI Xiaoying. Estimation of Snow Depth from Multi-source Data Fusion Based on Data Assimilation Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(6): 848-852. DOI: 10.13203/j.whugis20140568
[7]	SONG Fucheng, SHI Shuangshuang, FENG Jiandi. Construction of Ionospheric TEC Assimilation Model Based on Chapman Function[J]. Geomatics and Information Science of Wuhan University, 2016, 41(6): 784-790. DOI: 10.13203/j.whugis20150101
[8]	ZHANG Xianfeng, ZHAO Jiepeng. System for Soil Moisture Retrieval and Data Assimilation from Remotely Sensed Data in Arid Regions[J]. Geomatics and Information Science of Wuhan University, 2012, 37(7): 794-799.
[9]	WU Mingguang, LUE Guonian, CHEN Taisheng. Data Structure Assimilation of Marker Symbol[J]. Geomatics and Information Science of Wuhan University, 2011, 36(2): 239-243.
[10]	CHEN Rongyuan, LIU Guoying, WANG Leiguang, QIN Qianqing. Fusion Algorithm of Multispectral and Panchromatic Images Based on the Data Assimilation[J]. Geomatics and Information Science of Wuhan University, 2009, 34(8): 919-923.

Cited By

Cited by

Periodical cited type(13)

1.	杨忠荣. 低成本车载RTK高精度定位方法. 地理空间信息. 2025(03): 96-100 .
2.	程建华，陈思成，臧楠，程思翔，赵国晶，马子凡. 附加自适应短时高程变化率约束的PPP/INS紧组合增强模型. 测绘学报. 2024(09): 1761-1776 .
3.	王勋，崔先强，高天杭. 动力学模型自适应滤波算法研究. 武汉大学学报(信息科学版). 2023(05): 741-748 .
4.	张一，尹潇，宋海娜. 运动方向约束的自适应SRUKF目标跟踪算法. 导航定位学报. 2023(05): 53-59 .
5.	李清泉，吕世望，陈智鹏，殷煜，张德津. 冬奥会国家速滑馆超大地坪平整度快速测量. 武汉大学学报(信息科学版). 2022(03): 325-333 .
6.	辜声峰，戴春齐，何成鹏，方礼喆，王梓豪. 面向城市车载导航的多系统PPP-RTK/VIO半紧组合算法性能分析. 武汉大学学报(信息科学版). 2021(12): 1852-1861 .
7.	陶晓晓，卢小平，路泽忠，周雨石，余振宝. WiFi融合环境光定位方法研究. 测绘科学. 2020(06): 57-61+72 .
8.	张辰东，王兆瑞. 一种长隧道内高速列车实时高精度定位方法. 计算机仿真. 2020(09): 124-128+188 .
9.	尹潇，柴洪洲，向民志，杜祯强. 附加运动学约束的BDS抗差UKF导航算法. 测绘学报. 2020(11): 1399-1406 .
10.	王诒国，潘孝星. 基于马氏距离的抗差卡尔曼滤波算法在组合导航中的应用. 北京测绘. 2020(12): 1810-1814 .
11.	吕大千，曾芳玲，欧阳晓凤，于合理. 时频传递的改进整数相位钟方法. 测绘学报. 2019(07): 889-897 .
12.	邓中亮，尹露，唐诗浩，刘延旭，宋汶轩. 室内定位关键技术综述. 导航定位与授时. 2018(03): 14-23 .
13.	张迪，施昆，李照永. 移动测量系统的GNSS/INS组合定位方法的对比研究. 软件. 2018(08): 110-116 .

Other cited types(18)

Get Citation

PDF

XML

Article views (1342) PDF downloads (259) Cited by(31)

Parallel Algorithm for Partitioning Massive Spatial Vector Data in Cloud Environment

Abstract

References

Related Articles

Cited by

Periodical cited type(13)

Other cited types(18)

Catalog

Related

Parallel Algorithm for Partitioning Massive Spatial Vector Data in Cloud Environment

Abstract

References

Related Articles

Cited by

Periodical cited type(13)

Other cited types(18)

Catalog

Related

Export File

Citation

Format

Content