基于Hilbert曲线层次分解的空间数据划分方法

针对现有空间数据划分方法普遍存在的不考虑空间对象自身大小和相邻对象空间关系对数据划分的影响等问题,提出一种基于Hilbert空间填充曲线层次分解的空间数据划分方法。该方法使用Hilbert曲线保持划分后空间数据之间的邻近性,利用少数子网格的层次分解避免对整个空间范围的密集划分,减少空间对象的Hilbert编码计算和排序时间;通过计算划分区域平均数据量和子网格内空间对象大小,确定合适的层次分解参数,实现各划分区域内空间数据量均衡。实验表明,该方法提高了空间数据的划分效率,能够保持划分后空间数据之间的邻近性和各个分区数据量的平衡。

A Spatial Data Partitioning Algorithm Based on Spatial Hierarchical Decomposition Method of Hilbert Space-Filling Curve

Spatial data partitioning strategy plays an important role in spatial data distributed storage,its key problem is how to partition spatial data to distributed storage nodes in network environment.This paper discusses the existing main spatial data partitioning methods and analyses their disadvantages,these partitioning methods have not taken into account spatial locality and unstructured variable length characteristics of spatial data,these methods simply partition spatial data based on attributes value that could result in storage capacity imbalance between distributed storage nodes.Aiming at these,this paper proposes a new spatial data partitioning strategy based on spatial hierarchical decomposition method of low order Hilbert space-filling curve,which could avoid excessively intensive space partitioning by hierarchically decomposing a handful of sub-grids.The paper summarizes the basic principles that spatial data partitioning should be meet to,describes the keystone of spatial data partitioning method based on Hilbert curve decomposition,and then gives its concrete algorithm process.Experimental results show that the presented spatial data partitioning algorithm not only achieves better storage load balance between distributed storage nodes,but also keeps well spatial locality of data objects after partitioning.