-
空间数据划分的目的是将空间大数据分割为相对较小的、独立的多数据块进行存储，能够很大程度上提高空间数据的分布式存储和并行化处理能力。在众多传统的空间数据划分算法中，由于Hilbert空间填充曲线具有良好的空间集聚特征[1-3]，因此被广泛应用于空间数据划分领域。文献[4]提出了一种基于Hilbert空间填充曲线的矢量数据划分算法，该算法按照Hilbert编码排序，通过遍历所有要素，依次写入N个数据桶中，并映射到N个存储节点上。文献[5]通过K-均值聚类算法得到Hilbert编码对应的质心，再根据数据量大小进行空间划分并存储在K个节点上。文献[6]提出了基于Hilbert曲线层次分解的空间数据划分方法，对大数据块进行多级分解, 然而当数据块过大时，势必会导致层次分解过多，从而降低数据划分效率。传统的空间数据划分方法尽管能够很好地保证数据划分结果的空间分布聚集特征，但当数据量过大时，单节点的数据划分算法很容易成为限制瓶颈；同时，在存储节点上，数据仍然以整体数据块存在，随着数据量的增加，同样会影响数据的检索效率。
云计算技术的出现为大数据的存储与管理提供了理想的解决方案[7-9]。其中，Hadoop平台具有易扩展、高容错、可靠、高效、经济等特点，近几年在科学计算、人工智能等多个领域都得到了广泛的应用。然而在空间大数据处理方面，由于空间数据独有的空间特征，使得Hadoop平台并不能充分发挥自己的优势[10]。基于Hadoop默认的Hash划分方法，尽管能够很好地保证数据块之间的均衡，但往往会导致同一空间要素或相邻空间要素存储在不同的数据块中，这样会大大降低空间数据的索引效率以及空间操作的执行性能。
为了弥补Hadoop平台中数据划分及其存储的不足，文献[11-12]通过抽取随机样本，建立了相应的空间数据划分策略，实现了格网、四叉树、Hilbert等7种不同的空间数据划分并行化算法。但由于样本的随机性，对于空间索引而言，一方面无法保证其空间索引结果的一致性；另一方面也会丢失数据的空间分布特征，从而导致空间数据的划分结果并不理想，影响空间索引效率。对于Hadoop平台而言，由于空间数据的分布不均，很容易造成个别Reduce任务负载“过热”，使得整个任务执行效率降低，其结果也将直接导致Hadoop分布式文件系统(Hadoop distributed file system, HDFS)中的数据块分布严重倾斜。
本文针对以上技术的不足，提出了一种云环境下的海量空间矢量数据并行划分算法，详细介绍了算法的实现过程，并从R-tree空间索引效率和HDFS存储数据倾斜度两个方面比较了本文算法的优越性。
-
Hilbert曲线是经典的Peano空间填充曲线族中的一种，由德国数学家希尔伯特于1981年构造出该曲线空间填充的几何过程[13]。Hilbert曲线定义为N维空间R(N)与一维空间R之间的一一映射。如图 1所示，分别为1阶和2阶Hilbert空间填充曲线及其对应的空间编码。
图 1 1阶和2阶Hilbert编码
Figure 1. 1st and 2nd-orders Hilbert Codes
常见的空间填充曲线还有Z曲线、Gray曲线等，但由于Hilbert空间填充曲线在生成过程中没有出现空间上的大幅度跳跃，使得编码在空间分布上具有良好的聚集性，即相邻Hilbert空间编码的编码块在空间分布上一定是相邻的。因此，本文算法在数据划分过程中，充分利用Hilbert曲线这一优点，使得该算法能够在很大程度上保证空间数据的分布特征，从而提高空间索引效率。
-
本文算法主要针对空间矢量数据，即点、线、面数据要素。其中，对于点要素，直接用坐标点来表示空间位置信息；对于线和面要素，用其对应的中心点坐标来代替。假设Hilbert空间填充曲线的阶数为N，则整个数据集D的空间范围将被划分为2N×2N个格网。每一个格网具有唯一的Hilbert编码标识，将该格网称之为编码块。
在该算法中，Hilbert编码阶数的初始值设定为N0：
$$ {N_0} = \left\lceil {{{\log }_2}\frac{V}{{V'}}} \right\rceil $$ (1) 式中, V为数据量总体大小; V′为HDFS上默认的数据块存储大小; $\left\lceil \cdot \right\rceil $表示向上取整。具体算法描述为：
1) Hilbert空间编码。通过遍历要素集，获取每一个空间要素在N阶格网下对应的Hilbert空间编码、中心点坐标和数据量大小。
2) 空间信息统计。统计具有相同编码(Hcode)的要素对应的信息集S，即每一个编码块对应的数据量大小(Hsize)和数据量个数(Hcount)。如果该编码块数据量大小(Hsize)大于HDFS数据块存储大小(V′×ρmax)，则记录该编码块对应的二级划分样本集合s；否则，s={0}。其中ρmax为HDFS存储数据块的最大阈值百分比。
3) 生成空间划分矩阵T。根据步骤2)中得到的空间数据样本信息集S，基于“合并小编码块，分解大编码块”的划分思想，利用Hilbert空间填充曲线的聚集特性，将相邻的小编码块进行合并; 同时，根据二级划分集合s，将大编码块进行再划分，最终可以计算得出每一个编码块(Hcode)对应的HDFS数据块存储编号(i)，从而生成该数据集对应的空间数据划分矩阵T :
$$ \mathit{\boldsymbol{T = }}\left[{\begin{array}{*{20}{c}} {{H_{{\rm{cod}}{{\rm{e}}_{\rm{0}}}}}}&{{i_0}}&{{s_0}}\\ {{H_{{\rm{cod}}{{\rm{e}}_1}}}}&{{i_1}}&{{s_1}}\\ \vdots&\vdots&\vdots \\ {{H_{{\rm{cod}}{{\rm{e}}_n}}}}&{{i_n}}&{{s_n}} \end{array}} \right] $$ (2) 4) 空间数据划分。根据空间数据划分矩阵T，通过再次遍历空间要素集，获取其对应的Hilbert空间编码和矩阵T匹配对应的HDFS数据块存储编号，并将该要素写入到该数据块中，至此完成所有空间要素的划分工作。
为了使得基于该划分方法的空间索引效率更优，在步骤2)中，如图 2所示，通过单向计算其对应的二级划分集合s。如果宽度大于长度，计算X方向集合{x0, x1, x2…xt}；否则，计算Y方向的集合{y0, y1, y2…yt}。利用式(3)获取元素间隔大小：
$$ L = \frac{{V'}}{V} $$ (3) 
图 2 二级划分集合s的获取
Figure 2. Acquisition of the Sub-split Set s
式中, L代表间隔大小; V代表该编码块要素的平均大小。
通过该方法进行大编码块的再次分解，与文献[6]相比，大编码块有且只有一次被执行再处理，有效降低了算法的复杂度。同时对于分割后的碎片数据依旧判断是否与相邻数据块进行合并。
在步骤3)中，依据Hilbert曲线空间聚集特性，将相邻的小编码块进行合并，在空间划分矩阵T中，它们会对应相同的HDFS数据块存储编号，同时在步骤4)中会被写入到同一个数据块中。
-
本文算法在具体实现过程中通过两个MapReduce任务来完成，如图 3所示，包括空间信息统计阶段和空间数据划分阶段。
图 3 算法并行化实现
Figure 3. Implementation of the Parallel Algorithm
-
Map阶段：在Map过程中，读入的值是单个空间要素，通过Map函数，实现空间要素的键值化。其中键为Hilbert空间编码(Hcode)，值为空间要素字节大小(Esize)和中心点坐标(Cpoint), 则Map输出的一条记录可表述为 < Hcode, Esize; Cpoint>。
Reduce阶段：在Reduce过程中, 读入的键为编码块对应的Hilbert空间编码(Hcode)，而值为该编码块对应的所有要素信息集合，即 < Hcode, (Esize; Cpoint)(Esize; Cpoint)…(Esize; Cpoint)>。通过Reduce函数，首先利用式(3)计算该编码块大小(Hsize)；然后与HDFS中默认的存储数据块大小(V′×ρmax)进行比较，判断是否进行二级划分，并记录其二级划分集合s。Reduce输出结果的键保持不变，值为 < Hsize; s>，每一条记录的键值对为 < Hcode, Hsize; s>。二级划分集合s的计算方法见图 2。Hsize的计算方法为：
$$ {H_{{\rm{size}}}} = \sum\limits_{i = 0}^t {{E_{{\rm{size}}}}\left( i \right)} $$ (4) 至此，空间信息统计阶段结束，那么由该阶段生成的空间信息集S为所有记录的集合，S可表述为：
$$ \begin{array}{l} S = \{ < {H_{{\rm{cod}}{{\rm{e}}_0}}}, \;{H_{{\rm{size}}}};{\rm{ }}s >, {H_{{\rm{cod}}{{\rm{e}}_{\rm{1}}}}}, \;{H_{{\rm{size}}}};\\ s > \cdots {H_{{\rm{cod}}{{\rm{e}}_i}}}, \;{H_{{\rm{size}}}};\;s > \cdots < {H_{{\rm{cod}}{{\rm{e}}_t}}}, \;{H_{{\rm{size}}}};\\ \;\;\;\;\;\;\;\;\;\;\;{\rm{ }}s > \} \left( {i \in \left[{0,t} \right]} \right) \end{array} $$ 一般情况下，空间矢量要素分布是不均匀的，所以t小于Hilbert曲线在N阶下编码块的总个数22N。
-
Map阶段：在§2的步骤3)中，针对空间信息集S，生成空间数据划分矩阵T。在Map阶段，通过比较编码块大小(Hsize)与HDFS存储数据块大小(V′×ρmax)，合并或分解编码块，并计算当前编码块在HDFS上的存储数据块编号(i)。
Reduce阶段：主要实现空间数据的具体划分和数据块的分发工作。通过获取当前空间要素对应的Hcode，与空间数据划分矩阵T进行匹配，如果二级划分样本集合s ={0}，则直接写入到对应的编号为i的数据块中；否则，计算其x值或者y值在集合s中的排序位置i′，将其写入到编号为(i+ i′)的数据块中。通过遍历所有空间要素集，完成空间数据在HDFS上的数据库划分工作。
-
试验环境采用Hadoop集群，节点个数为4，操作系统为CentOS 6，Hadoop版本为Hadoop-1.2.1，HDFS存储数据块默认大小为64 MB。其中每个节点的内存大小为16 GB，磁盘容量为1 TB。
实验数据分别采用全球县级行政区划数据(D0)、全球湖泊分布数据(D1)和全球矢量数据集(D2)。数据基本信息如表 1所示。
表 1 实验数据集信息
Table 1. Information of Experimental Datasets
数据名称 数据大小/GB 要素个数/MB 平均大小/kB D0 2.9 0.255 11.9 D1 9.1 8.4 1.14 D2 92.5 263 0.369 试验采用两种方案，一种为文献[11]基于随机抽样的Hilbert数据划分方法，另一种为本文所提出的划分方法。在随机抽样中，设定抽样率为1%[11]。本文方法中，Hilbert的阶数N设定为10。
-
本文通过两个方面对试验结果进行分析，分别为R-tree空间索引性能和HDFS存储数据倾斜度。
在R-tree空间索引性能方面，通过对两种划分方法分别建立对应的R-tree空间索引[10]，对比R-tree索引的性能指标Area(T)和Overlap(T)。其中Area(T)为R-tree索引树中闲置区域的覆盖总面积，闲置区域越少，则R树索引性能越好；Overlap(T)为R-tree索引树中重叠区域的覆盖总面积，重叠区域越少，其索引性能越好。标准化后的结果分别见图 4、图 5。
图 4 不同数据集的性能指标Area(T)对比
Figure 4. Comparison of Performance Index Area(T) for Different Datasets
图 5 不同数据集的性能指标Overlap(T)对比
Figure 5. Comparison of Performance Index Overlap(T) for Different Datasets
从图 4和图 5中可以看出，本文提出的方法在Area(T)和Overlap(T)两方面都表现优越。基于文献[11]中的方法，由于样本的随机性而丢失了数据划分的空间特征。本文方法充分利用了Hilbert空间填充曲线的空间相邻特征，基于Hilbert编码进行数据划分，很大程度上保证了矢量数据的空间分布特征，因而能够很好地提高空间数据的索引效率。
在HDFS存储数据倾斜度方面，计算两种划分方法对应的所有数据块大小的标准差, 如图 6所示。标准差越小, 表明数据倾斜度越小，数据在HDFS上的分布就越均匀。由图 6可知，本文方法在HDFS数据倾斜方面表现较优。由于本文充分考虑了空间数据对象的自身大小和空间编码块的个数，并通过与HDFS默认的存储数据块进行对比，采用“合并小编码块，分解大编码块”的思想，在不丢失空间分布特征的前提下，很好地保证了HDFS数据的负载均衡。
图 6 不同数据集的HDFS数据倾斜对比
Figure 6. Comparison of Data Skewness in HDFS for Different Datasets
-
本文提出了一种基于Hadoop平台的海量空间矢量数据并行划分算法。一方面，将Hilbert空间填充曲线引入到数据划分规则中，使得同一存储数据块中的要素在空间上保持相邻，提高了空间索引效率；另一方面，将空间对象的自身大小、相同编码块的空间对象个数、HDFS的存储块大小等影响因素设为参考，很好地解决了空间矢量数据在HDFS中分布不均的问题。试验表明，该方法在空间索引效率和HDFS存储数据倾斜度方面均具有优越性，能够为空间矢量大数据的分析与处理提供更好的数据服务。
Parallel Algorithm for Partitioning Massive Spatial Vector Data in Cloud Environment
-
摘要: 空间数据划分是空间大数据索引方法及其数据存储的重要组成部分。针对Hadoop云计算平台在空间数据划分及其存储方面的不足，提出了基于Hilbert空间填充曲线的海量空间矢量数据并行划分算法。在数据划分阶段，充分考虑空间数据相邻对象的空间位置关系、空间对象的自身大小以及相同编码块的空间对象个数等影响因素；通过“合并小编码块，分解大编码块”的划分原则，实现了云环境下海量空间矢量数据的并行划分算法。试验表明，该算法不仅能够提高海量空间矢量数据的索引效率，同时也能够很好地解决空间矢量数据在Hadoop分布式文件系统（Hadoop distributed file system，HDFS）上的数据倾斜问题。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).
-
Key words:
- vector data /
- Hilbert code /
- spatial data partitioning /
- MapReduce /
- R-tree index /
- data skewness
-
图 4 不同数据集的性能指标Area(T)对比
Figure 4. Comparison of Performance Index Area(T) for Different Datasets
图 5 不同数据集的性能指标Overlap(T)对比
Figure 5. Comparison of Performance Index Overlap(T) for Different Datasets
图 6 不同数据集的HDFS数据倾斜对比
Figure 6. Comparison of Data Skewness in HDFS for Different Datasets
表 1 实验数据集信息
Table 1. Information of Experimental Datasets
数据名称 数据大小/GB 要素个数/MB 平均大小/kB D0 2.9 0.255 11.9 D1 9.1 8.4 1.14 D2 92.5 263 0.369 
下载: 导出CSV
-
[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 -
点击查看大图
图(6) / 表(1)
计量
- 文章访问数: 1012
- HTML全文浏览量: 98
- PDF下载量: 248
- 被引次数: 0
