一种改进的真三维R 树空间索引方法

第31卷第4期2006年4月武汉大学学报 信息科学版Geo matics and Informat ion Science of W uhan U niver sity V ol.31N o.4A pr.2006收稿日期:2006 01 12。

项目来源:国家973计划资助项目(2004CB318206);湖北省青年杰出人才基金资助项目(2004ABB018);数字志莲净苑木构佛寺演示系统资助项目。

文章编号:1671 8860(2006)04 0340 04文献标志码:A一种改进的真三维R 树空间索引方法朱 庆1龚 俊1,2(1 武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079)(2 江西师范大学地理与环境学院,南昌市紫阳大道99号,330022)摘 要:利用k 均值算法和覆盖体积与重叠体积之和作为分组的综合指标,改进了现有的三维空间聚簇分组和R 树插入算法。

实验证明,该算法显著减少了R 树兄弟节点之间的重叠现象,而且节点尺寸均匀,有利于海量三维空间数据的高效管理与实时可视化应用。

关键词:真三维空间索引;R 树;空间聚簇分组;多细节层次中图法分类号:P208;T P311.12由于现有的商业数据库还不支持三维空间索引,对三维城市模型数据的处理往往都是在二维空间索引的基础上通过简单的三维扩充来实现的,如在二维R 树索引结果的基础上再进行第三维空间上的检索,从而造成三维检索效率低下[1]。

另外,对现实世界的三维表示离不开多细节层次概念(LOD)[2,3]。

近年来,三维城市模型的发展更加促使学者们关注和研究三维空间索引方法[3 5]。

另外,由于八叉树原理简单,便于实现,一些应用也以它作为三维空间索引的数据结构,甚至以它为基础实现三维空间数据模型。

本文提出了一种真三维R 树空间索引方法,改进了现有的三维空间聚簇分组和R 树插入算法。

1 真三维空间索引方法多维空间索引的理论研究涉及最多的是四叉树和R 树的多维扩展,针对三维就是八叉树和3D R 树。

其设计思想均符合二次磁盘访问的目的,即空间索引可基于外存存储,根据查询操作的需要,提取相关的索引节点信息,再根据节点信息,从外存中提取(如果已在主存缓冲区中,则从缓冲区中提取)实际需要的空间对象信息,索引节点信息在外存上对应一个磁盘页面,以快速访问节点信息。

经典八叉树的缺点在于一个对象可能需要在多个节点中存储索引信息,因而导致维护代价较高,空间利用率下降。

最为关键的是,它是空间驱动的索引结构,数据库范围必须事先规划固定,而且不能根据实际的数据分布密度来动态地调整树形,从而导致在对象分布密度高的位置,树深度较高;在对象分布密度低的位置,树深度较低,并且相关算法中大量使用迭代操作,树深过高,导致程序无法优化,性能不稳定。

R 树是一维数据索引B 树的扩展树状结构,用以解决多维数据查询,它是深度平衡的索引数据结构,根节点到任何包含索引记录的叶节点的深度相同,从而保证合理地利用存储空间。

如果索引是基于外存存储的,节点的存储空间对应相同尺寸的磁盘数据页,空间查询只需访问相关的节点数据,无需将索引结构整体加载入内存。

R 树的定义和特性可参考文献[6]。

3D R T ree 索引结构继承了R 树的特性。

它是动态的索引结构,数据库范围随着对象的插入而调整,并且根据实际的对象分布合理地调整树形,保证存储对象索引元组信息的叶节点的深度一致,从而保证索引操作效率的稳定性,而且空间利用率保持在60%以上,优化相关参数甚至可以达到80%。

因此可以认为,R 树索引方法是最有前途的真三维空间索引方法之一。

第31卷第4期朱 庆等:一种改进的真三维R 树空间索引方法2 真三维R 树空间索引的特性2.1 加速真三维空间查询三维R 树构造算法充分考虑了三维空间的邻近性原则,三维空间相邻的对象聚集于R 树相同的节点或者邻近兄弟节点中,并且其固有的树状层次结构具备从全局空间迅速锁定局部空间的能力,从而加速真三维空间查询,只需极少数的计算量就能从三维空间中获取满足指定空间条件的对象集合。

图1为从父节点全局空间快速下溯至子节点局部空间的过程。

图1 三维R 树空间索引示意图F ig.1 Idea of 3D R tr ee Spatial Index2.2 便于和LOD 结合R 树从树根到树叶自下而上形成金字塔形的树状层次结构,LOD 技术可以利用R 树索引的层次特性实现不同细节层次模型间的自然过渡。

子节点模型表示较精细的层次模型,父节点模型是对其所有子节点模型的简化表达,表示较粗糙的层次模型,从树叶到树根,LOD 模型的精度逐渐降低。

图1直观地反映了这种细节之间的过渡,箭头从上层节点的粗糙模型指向下层节点的精细模型,模型表达更加真实准确。

2.3 便于实现三维模型渐进传输和动态性能调整R 树的层次特性易于实现不同细节层次间的模型过渡,这个特性为实现三维模型的渐进传输和动态性能调整提供了有力的支持。

当三维场景数据复杂或者是远程网络应用时,精细模型数据无法实时加载,则首先装载上层节点所对应的粗略模型,快速给出粗略结果,随着精细模型加载到客户端,逐渐提供高精度结果,直至达到所需的最高精度要求。

同时,由于三维图形的数据量往往超出当前硬件的处理能力,为维持可交互绘制的稳定帧率,精确的负载平衡通过控制和调整每帧处理的模型精度来实现。

当系统所需处理的数据量超过其处理能力时,则R 树自动上溯到节点,采用上层节点所对应的低精度模型予以表达和分析计算,即使绘制质量受到一定影响,但是动画流畅仍然满足视觉感观。

当绘制帧率过快时,自动下溯节点,启用高精细程度的模型予以表达,从而实现动态性能调整。

2.4 真三维R 树空间索引存在的问题R 树构筑的树形理论上具备空间聚簇特性,即同层兄弟节点空间范围尺寸均匀,其间没有或者很少有重叠,空间邻近的对象包含在相同或相邻的节点中。

然而,随着空间维数从二维扩展到三维,R 树出现大量兄弟节点重叠的现象,甚至兄弟节点相互包含,而且大量节点呈现不规则形状,如长条状或者方薄饼状,这些造成空间查询的低效和应用失败。

而且,由于同层兄弟节点尺寸不均匀而相差过大,不能将同层兄弟节点看作一个细节层次的模型。

因此,R 树树形的空间聚簇特性的好坏与否,是真三维空间索引的应用瓶颈,需要研究合理的三维空间聚簇分组算法和相应的3D R 树算法,保证兄弟节点间的重叠体积最小,兄弟节点的形状合理和尺寸均匀。

3 三维空间聚簇分组算法和3D R树算法3.1 三维空间聚簇分组算法在R 树算法中,三维空间聚簇分组算法用于节点分裂操作和节点间优化重组操作。

经典的R 树采用面积准则实现空间聚簇,忽视重叠等重要因素。

R *树综合考虑了覆盖面积和重叠面积以及外围周长等因素,实现了较为合理的空间聚簇,但是对于覆盖面积和重叠面积的判据有待实验印证[7]。

H ilbert R 树试图通过H ilbert 曲线将多维空间的对象映射到一维空间中,但是由于从多维到一维的映射本身存在歧义,不可能在任何情况下都有最佳的表现[8]。

造成大量节点空间重叠的原因在于,现有的算法仅仅考虑了两个节点的优化问题,如节点分裂是将一个上溢节点分为两个节点,实际上应当考虑多个节点间的优化问题,如节点可以分裂为两个以上的节点。

如图2所示,线框立方体表示待分裂的节点,立方实体表示子对象,显然,将子对象分为三组比分为两组更为合理。

本文提出的三维空间聚簇分组的算法借用了数据挖掘中k 均值算法划分k 个空间簇的能力,较好地顾及了对象的三维空间分布,予以分组。

图2中,节点的尺寸为x 、y 、z ,根据高斯定理:x y z ,当且仅当x =y =z 时,等号341武汉大学学报 信息科学版2006年4月成立,则称x +y +z 33为高斯值。

一般认为,高斯值越小,尺寸越均匀。

由于要求分组后的空间覆盖体积、高斯值和重叠体积尽可能小,为此,本文将空间覆盖体积、重叠体积之和W 作为分组的综合指标。

空间聚簇分组算法描述如下。

图2 空间聚簇分组Fig.2 Spat ial Cluster Gro uping算法入口:三维空间对象集合S ={P 1,P 2, ,P n }。

算法出口:对象集合S 分组为数个小对象集合S i ,i =1, ,k 。

1)计算最大分组数目k max ,即保证n/k max m,m 为节点必须包含子对象的最小数目。

2)从k =2开始,到k max 个分组数目下,分别调用下面的分组算法计算最小的分组综合指标W ,选择最小的分组综合指标时的分组策略作为最后的分组结果。

分组算法描述如下。

1)从S 中选择k 个对象分别赋给k 个S i 的小集合,作为这k 个集合的种子对象,将k 个对象间的距离之和最大作为种子选择的原则,将k 个对象的中心作为k 个集合的中心;2)将k 均值法作为剩余对象选择所属分组的原则,即将对象加入到距离集合中心最近的集合中,加入后更新所在集合的中心;3)重复步骤2),直至剩余对象完全分配到k 个集合中。

3.2 3D R 树插入算法插入操作是R 树生成的关键步骤,将新的元组对象插入R 树中,形成合理的R 树树形,保证最佳的查询性能。

其中包含两个重要的子算法:节点选择和节点分裂。

节点选择的实现目的在于,当元组从根节点进入R 树时,迭代判断选择其所应进入的子树,直至到达叶节点。

节点分裂的实现目的在于,当元组对象插入叶节点,导致节点上溢时,将大节点分为数个小节点,如果下层节点分裂导致上层节点上溢,则继续向上进行分裂操作,直至分裂根节点,产生新的根节点。

两个子算法吸收了空间聚簇分组的思想,使得空间相邻的对象存储于相同或相邻的节点中,保证树形的合理性。

经典R 树中,如果两个元组落于两个节点内,则不论空间对象的分布情况,均不能将两个元组调整于一个节点内。

R *树强行将不合理的元组对象予以重新插入,使得树形在频繁的调整中达到最优,较大程度地调整树形。

然而重新插入存在盲目性,导致不必要的多余计算,而实际调整效果也不尽理想。

本文提出一种新的动态插入算法,根据节点选择算法选择合理的叶子节点,以插入元组对象。

插入操作可能导致从树叶到树根的路径上的节点范围发生改变,造成R 树各层不合理的节点分布。

本算法通过搜索不合理的节点并进行优化调整,实现R 树的大范围动态优化。

该算法描述如下:①通过节点选择算法,找到元组所应插入的叶子节点;②插入元组对象,如果导致节点溢出,调用节点分裂算法,实现最优的三维空间聚簇分组;③如果插入操作导致叶子节点范围发生变化,则以插入元组的叶节点为N 1,其父节点为F;④搜索F 中与N 1的重叠面积最大的子节点N 2,根据三维空间聚簇分组算法对N 1和N 2中的子对象重新优化分组;⑤如果N 1和N 2的原始分组已经最优,则退出算法;如果二者的子对象发生调整,则令节点F 为N 1,节点F 的父节点为F ,循环执行步骤④,直至达到根节点。