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

-InformationScienceJuly20072007年7月基于Hilbert曲线层次分解的空间数据划分方法周艳,朱庆,张叶廷()武汉大学测绘遥感信息工程国家重点实验室,湖北武汉430079摘要:针对现有空间数据划分方法普遍存在的不考虑空间对象自身大小和相邻对象空间关系对数据划分的影响等问题,提出一种基于Hilbert空间填充曲线层次分解的空间数据划分方法。该方法使用Hilbert曲线保持划分后空间数据之间的邻近性,利用少数子网格的层次分解避免对整个空间范围的密集划分,减少空间对象的Hilbert编码计算和排序时间;通过计算划分区域平均数据量和子网格内空间对象大小,确定合适的层次分解参数,实现各划分区域内空间数据量均衡。实验表明,该方法提高了空间数据的划分效率,能够保持划分后空间数据之间的邻近性和各个分区数据量的平衡。关键词:空间数据划分;空间数据管理;Hilbert曲线;空间层次分解()文章编号:1672-0504200704-0013-05中图分类号:P208文献标识码:A[3]分,可以保证划分后每个子网格内的空间数据本0引言身有良好的空间相邻性,但无法保证划分到相同存储节点的多个子网格之间的空间邻近性。空间数据划分是空间数据分布存储管理的首要任务:在考虑单个存储节点容量有限的前提下,一个空间对象是变长的,不同几何对象存储在空间关键问题是如何将空间数据划分至N个存储节点,数据库中的记录大小并不固定,划分后的子数据集很可能出现对象数目相同而数据量不同的情况。将空间数据划分策略的优劣将直接影响各节点的存储负载和空间数据管理的整体性能。传统的数据划分这样的划分结果分配到不同的存储节点,则会导致数据存储和访问时负载不平衡现象,既而产生数据策略是根据数据某一个或几个划分属性,按照某种规则对属性的值域进行划分,得到一组子数据集,从倾斜。上述空间数据划分方法仅考虑了空间对象的局部位臵属性,而没有考虑空间对象本身大小对数而能够存储在不同节点。常用的方法有轮转法()()round-robin、散列划分hashpartition、范围划据划分产生的影响。因此,良好的空间数据划分策()(略应该同时考虑数据的空间位臵特性和变长特点,分rangepartition、混合划分hybrid-rangeparti2[1])tion和CMD方法等。然而,空间数据是多维的,划分后的空间数据应满足两个基本原则:每个分区()意味着同一个存储节点内部的空间数据保持良好并且任何一维都不存在一种排序可以完全反映数据()之间的空间邻近性,使用传统方法划分空间数据会的空间邻近性;各分区意味着不同存储节点之间能够保证大致均衡的数据存储量。割裂空间记录之间的内在联系,使空间上相邻的数据对象被划分到不同的存储空间上,给后续空间查保持空间数据的邻近性意味着相邻的空间实体对象其物理存储应当在一起,空间填充曲线是实现询和管理造成不必要的访问开销。这一目标的有效方法。德国数学家Hilbert于1891文献[2]讨论了目前已有的4种空间数据划分()年构造出Hilbert曲线图1,已被证明是能够最好方法,其基本思想是根据空间对象位臵将空间范围[4]划分成大小相等或不等的空间网格,分别采用4种保持空间点的局部邻接性的空间填充曲线。文献[5]提出一种基于Hilbert填充曲线的空间数据划分不同的规则将划分后的空间子网格内的数据分别存储到不同的节点上。大型空间数据库OracleSpatial方法,该方法有效保证了各存储节点之间的存储均衡;然而空间数据常含有数万甚至数十万个空间对的基于空间位臵的范围划分策略也采用了相似的思想,OracleSpatial提供了两种基本方法:基于X或象,当空间对象数目过多时,计算和存储每个对象的Hilbert编码将耗费大量的时间和空间。文献[6]提Y坐标值的范围划分、基于X和Y坐标值的范围划收稿日期:2007-03-28;修订日期:2007-06-04()()基金项目:国家自然科学基金项目40671158;新世纪优秀人才支持计划资助NCET-05-0626;测绘遥感信息工程国家重点实验室()开放基金资助项目05-0402()作者简介:周艳1976-,女,博士研究生,从事数码城市GIS以及分布式GIS理论、方法和应用研究。E-mail:Swallow_anne@出一种基于空间层次分解的Hilbert快速编码方法,Hilbert编码于同一存储节点的空间对象无需进行它充分利用Hilbert曲线自身的分形相似性特点,通排序,即可建立包含多个空间对象的低阶Hilbert粗过空间层次分解,显著提高了Hilbert曲线的编码速网格。然而,仅仅简单