（计算机应用技术专业论文）空间数据库中基于r树的最近邻查询方法研究.pdf

， 产 一 、 j 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：梯廷 日期：z 。f o年弓月旷日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可酬芏授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：穰是 日期：7 。扣年，月f 厂日 导师( 签字 2 0 f 。年弓月心日 哈尔滨f t 程大学硕十学位论文 摘要 空间数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或 不能有效地发挥作用，需要研究新的查询处理技术。因此如何提供各种高效 的空间索引与空间对象查询处理技术是当前空间数据库领域的研究热点之 一。至今人们提出了利用多种不同类型的空间索引结构对空间数据库进行查 询，其中大多数都是基于r 树索引结构的，例如最近邻查询、反最近邻查询、 连续最近邻查询以及最近对查询等。 目前现有的最近邻查询方法多是集中在目标对象为实际对象而把查询对 象简化为一个空间点的情况下进行研究的，而在实际应用中，查询对象在很 多情况下也同样是空间中的一个实际对象，所以把查询目标简化为一个空间 点的方法存在着极大的局限性。在查询算法的实际执行过程中，由于选取的 剪枝策略不能适应实际情况，常常需要访问许多实际上并不包含最近邻的 m b r ，从而增加了空间数据库中读入对象的i o 耗费，以及计算两个实际空间 对象之间的距离耗费，增加了计算量，造成了算法的效率低下。 针对目前最近邻算法所存在的不足，本文主要在以下几方面做出改进。 首先，为了更加符合实际查询的需要，本文将查询对象的模型由一个空间点 扩展为空间中具体对象的二维边界，并针对两个具体空间对象的距离，给出 了其距离估计的上界和下界。其次，将等高线的思想引入到近邻查询中，提 出了等距离线的概念，从而为两个具体空间对象之间距离的下界提供了一个 更为精确的估计。再次，在等距离线的基础上，提出了一种剪枝策略，并给 出了具体的最近邻查询处理算法。最后，通过实验验证了算法的正确性和有 效性。 关键词：空间数据库；空间索引；近邻查询；等距离线；剪枝 哈尔滨t 程大学硕十学传论文 a b s t r a c t t h eg r e a t c a p a c i t ya n dc o m p l e x i t yo fs p a t i a l d a t am a k ec o n v e n t i o n a l d a t a b a s eq u e r yp r o c e s s i n gt e c h n i q u e sn ol o n g e rw e l ls u i t e d ，a n dr e q u i r ee x p l o i t i n g n e wq u e r yp r o c e s s i n ga p p r o a c h e s t h e r e f o r e ，h o wt op r o v i d ea l lk i n d so fe f f i c i e n t q u e r yp r o c e s s i n gt e c h n i q u e sf o rs p a t i a la n ds p a t i o t e m p o r a lo b j e c t si so n eo f r e s e a r c hh o t s p o t si nt h ea r e ao fs p a t i a ld a t a b a s e sc u r r e n t l y p e o p l eh a v ep r o p o s e d v a r i o u st y p e so fs p a t i a ld a t a b a s e q u e r yp r o c e s s i n gt e c h n i q u e sw i t hd i f f e r e n t s p a t i a li n d e xs t r u c t u r e ，a n dm o s to ft h e ma r eb a s e do nt h er t r e e ，s u c ha sn e a r e s t n e i g h b o rq u e r y 、r e v e r s en e a r e s tn e i g h b o rq u e r y 、c o n t i n u o u sn e a r e s tn e i g h b o r q u e r i e sa n dc l o s e s tp a i rq u e r y c u r r e n t l ya v a i l a b l en e a r e s tn e i g h b o rq u e r ym e t h o d sa r em o s t l yc o n c e n t r a t e d i nt h ec a s et h a tt h et a r g e to b j e c ti st h ea c t u a lo b j e c ta n dt h eq u e r yo b j e c ti sa p o i n t i nt h es p a c e ，a n di np r a c t i c a la p p l i c a t i o n ，i nm a n yc a s e st h eq u e r yo b j e c ti sa l s oa r e a l o b j e c ti nt h es p a c e ，s ot h e r ei sag r e a tl i m i t a t i o ni nt h e s em e t h o d s t h e p r a c t i c a li m p l e m e n t a t i o no ft h ea l g o r i t h mi nt h eq u e r yp r o c e s s ，d u et ot h es e l e c t e d p r u n i n gs t r a t e g yw a sn o ta d e q u a t e ，a n do f t e nn e e dt oa c c e s san u m b e ro fn o d e s t h a td on o ti n c l u d et h en e a r e s tn e i g h b o r sm b r ，t h e r e b yi n c r e a s i n gt h ef o c o s to f a c c e s s i n gt h eo b j e c ti nt h es p a t i a ld a t a b a s ea n dc o m p u t a t i o nc o s to fc a l c u l a t i n gt h e a c t u a ld i s t a n c eb e t w e e no ft h et w os p a t i a l o b j e c t s ，r e s u l t i n gi nl o we f f i c i e n c yo f t h ea l g o r i t h m t h i s p a p e rh a sm a d ei m p r o v e m e n t si nt h e f o l l o w i n g a r e a sf o r t h e s h o r t c o m i n g so fc u r r e n tn e a r e s tn e i g h b o ra l g o r i t h m f i r s to fa l l ，i no r d e rt ob e t t e r m e e tt h en e e d so ft h e a c t u a lq u e r y , t h i sp a p e rr e p l a c e st h eq u e r yo b j e c tm o d e l c o n s i s t so fas p a c e 。p o i n tw i t han e wq u e r yo b j e c tm o d e lc o n s i s t so fa s p e c i f i c o b j e c t ，a n di t sd i s t a n c eo ft h ee s t i m a t e du p p e rb o u n da n dl o w e rb o u n di sg i v e nf o r t h ed i s t a n c eb e t w e e nt w os p e c i f i cs p a t i a l o b j e c t s e c o n d l y , t h ei d e o l o g i c a lo f c o n t o u rl i n e si si n t r o d u c e di n t ot h en e a r e s tn e i g h b o rq u e r ya n dp u tf o r w a r dt h e c o n c e p to fd i s t a n c e i s o l i n e ，s oa st op r o v i d eam o r ea c c u r a t ee s t i m a t ef o rl o w e r 哈尔滨丁程大学硕士学位论文 j i i 宣昌暑；昌；昌i ；昌宣昌置宣宣宣i i ；i 暑i 暑暑；i i i 昌；i ；i i 暑；i 置i ；i i ；i i 宣昌昌暑暑暑昌；昌；昌；暑昌昌昌暑暑暑暑宣置宣宣蕾i i q 暑 b o u n do ft h ed i s t a n c eb e t w e e nt w os p e c i f i cs p a t i a lo b j e c t s f i n a l l y , t h ep a p e r p r o p o s e sap r u n i n gs t r a t e g yb a s e do nd i s t a n c e i s o l i n ea n dg i v e sas p e c i f i cn e a r e s t n e i g h b o rq u e r yp r o c e s s i n ga l g o r i t h m s f i n a l l y , t h ec o r r e c t n e s sa n dv a l i d i t yo ft h e a l g o r i t h mi sv e r i f i e db yt h ee x p e r i m e n t k e y w o r d s ：s p a t i a ld a t a b a s e ；s p a t i a li n d e x ；n e a r e s tn e i g h b o rq u e r y ； d i s t a n c e i s o l i n e ；p r u n i n g 哈尔滨f t 程大学硕士学位论文 目录 第1 章绪论”1 1 1 课题研究的背景和意义”1 1 2 国内外研究现状2 1 2 1 静态对象的最近邻查询2 1 2 2 移动对象的最近邻查询”4 1 3 论文的主要研究内容及结构6 第2 章空间数据索引技术及近邻查询方法概述7 2 1 空间数据及其表示7 2 2 空间索引技术及其分类8 2 3 典型的空间索引r 树“1 1 2 3 1 查找算法1 3 2 3 2 插入算法1 4 2 3 3 删除算法1 5 2 3 4 分裂算法1 6 2 4 空间k 近邻查询方法研究1 9 2 4 1b a b 算法1 9 2 4 2b f 算法2 0 2 4 3 移动对象的静态近邻查询算法2 3 2 5 本章小结2 5 第3 章基于等距离线的空间k 近邻查询方法2 6 3 1 问题的提出2 6 3 2 相关概念”2 7 3 2 1 距离定义2 7 3 2 2 等距离线3 2 3 3 基于等距离线的k n n 算法“3 3 3 3 1k 近邻搜索剪枝规则一3 4 3 3 2 算例3 6 哈尔滨1 ：程大学硕士学位论文 3 4 本章小结”4 0 第4 章仿真与分析”4 1 4 1 实验环境4 1 4 2 算法描述“4 1 4 3 结果分析4 2 4 4 本章小结4 5 结论”4 6 参考文献4 7 攻读硕士学位期间发表的论文和取得的科研成果5 3 致谢5 4 哈尔滨工程大学硕十学位论文 第1 章绪论 1 1 课题研究的背景和意义 空间数据库的研究始于2 0 世纪7 0 年代的地图制图与遥感图像处理领域， 其目的是为了有效地利用卫星遥感资源迅速绘制出各种经济专题地图。由于 传统的关系数据库在空间数据的表示、存储、管理、检索上存在许多缺陷， 从而形成了空间数据库这一数据库研究领域。随着地理信息系统( g e o g r a p h i c i n f o r m a t i o ns y s t e m ，g i s ) 、计算机辅助设计与制造( c a d c a m ) 、机器人、多 媒体系统、数字地球、移动通信及定位服务等应用领域的发展，对空间数据 库以及时空数据库的研究越来越受到人们的重视n 一，。 g i s b l 由许多部分所组成，空间数据库是其最为重要的组成部分之一。空 间数据库的研究内容十分广泛，主要涉及空间对象的表示、空间对象建模、 空间对象索引、空间对象查询、空间数据库体系结构等。由于空间数据库在 多媒体系统、g i s 、智能交通系统、车载导航系统、战场模拟等方面具有广 泛的应用前景，所以世界上的很多科研工作者以及有关厂商对其产生了浓厚 的兴趣，尤其是一些欧洲国家已经开始了许多相关内容的研究。例如，由欧 洲委员会赞助的c h o r o h r o n o s 项目，其主要研究内容为空间对象表示、 空间模型与语言、空间信息图形用户接口、空间查询处理、空间对象索引以 及空间数据库体系结构等n ，。许多知名的数据库厂商女a o r a c l e 、d b 2 、l n f o m i x 等为了支持空间应用也纷纷提供了可扩展的对象关系数据库技术。例如，在 o r a c l e9 i 数据库系统中o r a c l e 定位器和o r a c l e 空间对基于位置的查询提供了支 持晦1 ；d b 2 中的空间数据库操作阳，；i n f o r m i x 中的r 树索引结构的实现n ，；m a p i n f o s p a t i a l w a r e 扩展了一个i n f o r m i x 数据库系统以支持对点、线和多边形等空间数 据的处理1 国内方面，杨高明等人对g i s 中矢量数据的栅格化进行了误差估计 阳1 ，并且在g i s 中实现了b l o b 数据类型“。 地理信息系统自上世纪七十年代发展至今，已经逐渐的从实验室走入社 会。伴随着通过互联网为人们提供各种便利服务的w e b g i s 的发展以及“数字 地球”和“数字城市”的出现，地理信息系统已开始逐渐的进入到人们的日常生 1 哈尔滨工程大学硕士学位论文 活中。“数字地球”这一概念的提出，将使得地理信息系统这一重要支撑技术 面临着前所未见的海量数据。如美国国家航空航天局的地球观测数据库( e a a h o b s e r v a t i o ns y s t e md a t a b a s e ) q a 存储的数据量已经达到了1 0 1 0 m b 之多，而互联 网上瞬间的信息传送量更是不计其数，所以地理信息系统需要具有高效的数 据处理能力。 建立空间数据库系统是组织管理和高效存储这些海量的空间数据的最为 行之有效的方法。目前为止，空间数据引擎技术是最成熟的技术之一，利用 关系型数据库来存储和管理空间数据很好的实现了属性数据和空间数据的有 效结合。空间数据描述空间对象的位置、形状和分布特征等空间信息，属性 数据描述空间对象的名称、专题属性等非空间信息。空间数据库虽然解决了 海量的空间数据的存储问题，但是由于空间数据的特殊性及其复杂性，当面 临这些海量的空间数据时，空间数据库如何能够按照用户所提出的查询要求 快速、准确、有效的反馈出查询结果，解决此问题的方法之一就是空间索引 技术。 1 2 国内外研究现状 空间查询( s p a t i a lq u e r y ) 是指从空间数据库中找出满足某些特定条件的空 间对象的过程。空间查询又可以叫做空间查找或空间检索。目前比较常用的 空间查询类型主要包括以下几种：最近邻查询、空间连接查询、反最近邻查 询、最近对查询、s k y l i n e 查询、点查询、范围查询、区域查询等类型。 基于r 树及其变形树的最近邻查询问题一直是空间数据库研究的重要应 用领域。前人已经提出了许多最近邻查询算法，根据查询对象和被查询对象 的运动状态，即处于静止还是运动状态，最近邻查询可以分为：静态对象的 最近邻查询和移动对象的最近邻查询。 1 2 1 静态对象的最近邻查询 目前，国内外空间数据库领域的研究者们在静态对象的最近邻查询问题 方面已经取得了一定的成果，并且提出了许多基于静态对象的最近邻查询算 2 哈尔滨t 程大学硕十学位论文 法。其中，基于r 树的b a b ( b r a n c h a n d b o u n d ) 算法也称为分支界限算法是最 近邻查询的基本算法，而后所出现的深度优先遍历r 树的d f ( d e p t h f i r s t ) 算法 和宽度优先遍历r 树i 拘b f ( b r e a d t h f i r s t ) 算法都是在b a b 算法的基础上改进而 来的。d f 算法是由n r o u s s o p o u l u ss k e l l e y 和f v i n c e n t 于1 9 9 5 年所提出的n ”， 该方法通过查询点q 到r 树中叶子结点所包含目标对象的距离的最小值 m i n d i s t 和最大值m i n m a x d i s t 作为判断条件，在深度优先遍历r 树的过 程中进行剪枝从而减少了对象的访问数目以及计算量，提高了查询效率，并 且在文献【1 2 】中对算法性能进行了分析。2 0 0 2 年g r h j a l t a s o n 和h s a m e t 提出 了基于广度优先的b f 算法m ，在算法中截止到目前已经访问过的结点全部保 存到一个优先队列中，然后再结合所有未被访问的结点从中选取一个下次需 要处理的结点，从而在全局对算法的执行进行了很好的控制。前期， g r h j a l t a s o n 和h s a m e t “引是在一棵四叉树上实现了宽度优先搜索算法，并且 同样使用了一个优先队列。文献 1 5 1 证明了d f 算法在对r 树的遍历过程中存 在许多不必要的结点访问，所以该算法的i o 性能并不是十分的理想。之后， k o m “们等人提出了一个基于多步骤的最近邻查询算法，最后的查询结果是通 过对数据集进行多次的扫描而得来的。s e i d l 和k r i e g e l t ”，提出了一种较为优越 的基于多步骤的幻压邻查询处理算法，并且用实验证明了算法在c p u 执行时 间和f o 等主要性能方面较之前的最近邻查询算法有了很大改进。c h e u n g 和 f u “引证明了在删除了基于m i n m a x d i s t 的两个剪枝策略之后，算法的效率并 不受太大的影响。b e l u s s i “引等人提出了基于r + 树的查询处理方法。 在基于静态对象的移动最近邻查询方面，z h e n g 并l l l e e 首先对此类问题进 行了研究并且提出了基于v o m n o i 图的解决方法啪，。但该方法不能进行尉匠邻 的查询而只能对最近邻进行查询并且很难扩展到高维情况，所以具有很大的 局限性。s o n g 和r o u s s o p o u l o s 乜”通过引入了一个称为周期性采样技术的方法很 好的解决了该问题，但是此方法却存在着两个缺陷：首先，采样频率限制了 查询结果的精确度，其次，c p u 计算代价较高。之后，t a o 和p a p a d i a s t 2 引提出 了一种新的查询类型：时间参数化( t p ) 的查询。t p 查询不但能找到当前查询 对象的最近邻，而且还包含了当前查询结果的有效时间以及在有效时间之后 将会发生什么变化。 为t p 查询结果的形式，其中r 表示当前的查询结 果，t 表示r 的有效时间，c 表示在时刻t 将会影响查询结果的数据点的集合。 3 哈尔滨 二程大学硕士学位论文 为了求出在某一时间段内的t p 查询结果，需要对邛查询结果重复计算m 次， m 为分裂点的个数。很明显，大量的重复性计算将会导致高昂的c p u 和i o 代 价。为了降低处理代价，t a o 等人协，提出了一种新的查询处理方法，并且通过 大量的实验证明了方法的有效性。李松等人于2 0 0 8 年提出了提出了基于 v o r o n o i 图的反最近邻查询m ，接着又提出了移动对象的动态反向最近邻查询 技术1 4 7 1 ：王宝宗等提出了二维空间中基于约束关系的r n n 查询算法m ，；张婧 提出了空间对象的最佳近邻和可视反近邻查询研究m ，。国外许多学者在此方 面也做了许多相关研究5 “。 1 2 2 移动对象的最近邻查询 在基于移动对象的最近邻查询方面，无论是国内还是国外都还处在刚刚 起步的阶段。完成此类查询首先需要一个可以存储动态对象的索引结构。虽 然国内外已经有人提出了一些索引结构，但这些索引结构各自都存在着一些 问题，不能很好的适应未来的发展需要。p m r q u a d t r e e 、 r 树是国外提出 的可以索引动态对象的目前来说相对较好的空间数据索引结构。只有合适的 索引结构结合高效的最近邻查询算法才能很好的解决移动对象的最近邻查询 问题。 g k o l l i o s 和d g u n n o p u l o u s 心引等人在2 0 0 5 年提出了基于动态对象的最近邻 查询算法，此算法采用了对偶变换的方法，也就是将空间中的一个运动点的 运动轨迹转化为空间中的一个实际点，然后在此基础上通过运用b + 树等索引 结构对空间对象进行索引来给出最终的查询结果。但是该方法只能返回在某 一个时间间隔的近邻查询结果而不能给出某一个具体时刻的查询结果，具有 一定的局限性。 r b e n e t i s 、c j e n s e n 和g k a r c i a u s k a s 2 5 1 在2 0 0 5 年提出了基于t p r 树的最 近邻查询以及反最近邻查询算法，而算法不仅可应用于二维空间的移动对象 的最近邻查询，而且还可以进行扩展并应用于多维空间的移动对象的最近邻 查询。然而，此算法的查询结果每次只能提供一个最近邻，并且该近邻处于 未来的某一个时间段之中，不能进行连续的最近邻查询，从而限制了算法的 应用范围。在文献【2 6 】中r b e n e t i s 对前面的算法进行了改进，使其一次能够 4 哈尔滨1 = 程大学硕士学位论文 找到距离查询对象最近的酚目标对象，从而支持逝邻的查询。在连续移动 对象的连续k 近邻查询方面1 w e r k s t 州等人进行了相关探索。r a p t o p o u l o u 嘲1 等人 对基于移动对象数据库中的移动最近邻查询问题进行了探讨。目前，一些空 间数据库领域的专家学者对基于分布式环境下的连续最近邻问题进行了研究 并且取得了一定的研究成果例2 9 。 目前，除了上面已经介绍的一些传统的最近邻查询之外，一些随着人们 实际需求产生的新的查询类型也已经提出并且正在被研究中，比如空间网络 数据库中的k 近邻查询以及连续的k 近邻查询问题汹“，。 f e r h a t o s m a n o g l u 等人m 1 提出了受限制的最近邻查询( c o n s t r a i n e dn e a r e s t n e i g h b o rq u e r y ) l 6 题。该种查询问题的定义为：“给定一个查询对象q 和一个 查询区域d ，一个受限最近邻查询的目的是找出一个落在区域d 内的距离查询 对象q 最近的邻居”。其一般常见形式为受到限制的k 近邻查询，定义为：“给 定一个查询对象q 和一个查询区域d ，一个受限制的l ( j 丘邻查询的目的是找出 一个落在区域d 内的距离查询对象q 最近的阶邻居”。例如，查找距离火车站 西南方向最近的6 个宾馆。 近些年来，国内的专家学者在基于时空数据库的最近邻查询处理方面也 取得了较大的成果。于忠诚等人m 1 探讨了在移动环境下的连续最近邻的查询 问题。卢炎生等人，提出了一种基于广度优先( b 聊的最近邻查询的改进算法。 刘云生等人m ，提出了一种称为最小距离聚集查询的距离查询形式，该查询可 以计算几个对象集合中的对象到某一个中心对象集合中的对象的距离和，并 且能够返回距离查询对象最小的k 个目标对象距离之和。廖巍等人m ，提出了一 种可伸缩的增量连续k 近邻处理方法。 国内外数据库研究领域的专家学者虽然在空间数据的查询处理方面已经 取得了许多丰硕喜人的成果，但同时也存在着许许多多的不足之处，而人们 对空间数据的查询需要也正在不断的发展变化，复杂性越来越高，为了满足 人们日益增长的、复杂多变的查询需求，需要数据库研究者们不断创新，积 极进取，开拓新的查询类型，并给出完善的行之有效的查询处理方法。 5 哈尔滨工程大学硕士学位论文 1 3 论文的主要研究内容及结构 本论文的主要研究内容有以下几点： ( 1 ) 对空间数据库中的空间索引技术进行研究，重点研究了r 树的结构 及其动态特性。 ( 2 ) 对各种近邻查询算法进行了深入的研究，重点分析了现有的基于 r 树的近邻查询算法。 ( 3 ) 针对现有算法中查询对象模型不符合实际以及执行过程中访问数据 库次数较多的问题，给出基于等距离线的k 近邻查询算法以及理论依据及其 实现步骤。该算法在对空间数据进行检索时，能减少对数据库的访问次数， 提高查询效率。 ( 4 ) 用标准数据集进行实验，并分析实验结果。 本文共分为四章，各章节的内容编排如下： 第1 章分析空间数据库产生的背景及意义，国内外研究现状及发展趋势， 相关文献综述，并介绍课题研究的主要内容。 第2 章首先介绍了常用的空间索引技术，之后详细分析了r 树及其主要操 作算法，最后介绍了目前常用的一些近邻查询方法。 第3 章针对现有算法中查询对象模型不符合实际以及执行过程中访问数 据库次数较多的问题，给出了连续最近邻查询方法的问题描述和问题特征， 并详细说明了相关的概念及其定义，最后给出了算法的执行过程，并且针对 算法做出了相应的解释。 第4 章通过实验对所提出的算法进行性能分析，性能评价表明和现有的最 近邻查询方法相比本文所提出的算法在c p u 执行时间和i 0 代价方面有一定 提高。最后总结本文完成的主要工作，并对下一步将要进行研究的工作进行 展望。 6 哈尔滨t 程大学硕十学位论文 第2 章空间数据索引技术及近邻查询方法概述 数据库系统的一项基本任务就是对信息进行查询检索，空间数据库也不 例外，能否快速有效的根据用户需要进行信息检索是评价空间数据库性能的 一个重要指标，而对信息的高效检索是离不开空间数据索引的。本章首先介 绍了空间数据的特点以及空间索引技术，然后对典型的空间索引结构r 树以 及常见的空间近邻查询算法进行了详细的分析。 2 1 空间数据及其表示 空间对象由空间数据和属性数据所组成，空间对象包括点、线、面或者 更高维的包含时间的数据。空间对象的含义相当广泛，如城市、河流、道路、 乡村、国家、农田、山脉等等。空间数据描述空间对象的位置、形状等空间 信息。属性数据描述空间对象的名称及其特性，如城市人口数量、河流深度、 山脉的海拔等等啪，。空间对象分为两大类：离散对象和连续对象。光栅法和 矢量法是地理信息系统中两种常用的存储空间数据的方法。 栅格数据类型本质上就是网格中所代表的数字图像的类型。任何熟悉数 字图像的人都知道像素是图像中最小的独立单位。这些像素的集合可以组成 一幅图像，这种图像与通常所用的基于矢量模型的可伸缩图像是不同的。一 幅数字图像是实体外形的真实表现，而栅格数据类型是实体内在的抽象表示。 航空图像之所以使用栅格数据类型，主要是为了获取高分辨率的地图照片。 其他的栅格数据集还可以包含海拔、某一陆地卫星反射光的波长等信息。 栅格数据由许多单元格所组成，每个单元格存储一个单一值。栅格数据 可以是每个像素都包含颜色值的图像。每个单元记录的附加值可能是离散的 ( 如土地使用) 或连续的( 如温度) ，如果没有可用数据也可以是空值。虽 然栅格单元只存储一个值，但每一个单元格可以通过对光栅带的扩展使其表 示红绿蓝三种颜色、颜色映射图或一个可扩展的属性表。栅格数据集的分辨 率为它在地面单元的网格宽度。 栅格数据可以不同的形式进行存储，如标准的基于文件结构的t i f 、j p e g 7 哈尔滨t 程大学硕十学位论文 格式等，二进制大对象( b l o b ) 数据在关系数据库管理系统( r d b m s ) 的存储形 式与其他以矢量为基础的分类相似。数据库在适当的索引下通常可以更快的 对栅格数据进行检索，但要求其具有大的容量以存储数以百万计的记录。 在地理信息系统中，空间对象的地理特征就是其几何形状，地理特征通 常用矢量表示。不同的地理特征由不同的几何图形来表示： ( 1 ) 点：零维的点通常用来表示最简单的地理特征，如水井的位置、海 拔最高点、道路的起点等等。点类型文件所能传达的信息是最少的。当在小 比例尺下显示某一个区域时该区域可以用点来表示，例如在世界地图上用点 而非多边形来表示一个城市。点是没有尺寸无法进行测量的。 ( 2 ) 线或折线：一维线或折线用于表示线性特性，如河流、道路、铁路、 地形线。与点相似，在小比例尺的情况下某一个区域也可以用线来表示。可 以测量线的距离。 ( 3 ) 多边形：二维多边形用来表示覆盖地球表面的某一个特定区域，如 湖泊，公园范围，建筑，城市边界，或土地使用。多边形类型的文件所传达 的信息量是最大的。可以测量多边形的周长和面积。 每一个几何图形都与数据库中描述其属性的一条记录相对应。一条描述 湖泊的记录可能包含湖泊的深度，水质，污染水平等信息。这些信息可以用 来制作地图来描述数据集的特定属性，例如可以根据不同的污染程度来对湖 泊着色。不同的几何形状也可以进行比较，例如通过地理信息系统可以找出 距离某高度污染的湖泊1 英里的所有水井。 矢量特性可以通过应用多边形不能重叠等拓扑规则来保证空间的完整 性。矢量数据也可以用来代表连续变化的现象。等高线和三角不规则网络( t i n ) 用来表示海拔或其他不断变化的值。在某些特殊位置，t i n 的记录形成了一 个不规则的三角形网格，三角形的面则代表了地形表面。 2 2 空间索引技术及其分类 空间索引就是指在存储空间数据时依据空间对象的位置和形状或空间对 象之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间对 象的概要信息如对象的标识、外接矩形及指向空间对象实体的指针。高效的 8 哈尔溟t 程大学硕十学位论文 空间索引必须满足以下要求n 训： ( 1 ) 动态性。因为空间数据可以任意给定顺序在空间数据库中进行插入 或删除操作，所以索引需要记录下数据库的变化。 ( 2 ) 二级三级存储管理。尽管主存容量不断增大，但是仍不能把一个 空间数据库加载入主存。因此索引需要实现二级和三级存储的高效结合。 ( 3 ) 支持多空间操作。空间索引不能为了支持某一操作( 如恢复) 而牺 牲其他的操作( 如删除) 。 ( 4 ) 输入数据和插入顺序的独立。即使在插入顺序变化或输入数据高度 倾斜的情况下，空间索引仍然需要保证其效率。这点对于沿不同维分布的数 据尤其重要。 ( 5 ) 简单性。复杂的空间索引在多数情况下容易出错，在大规模的应用 程序中表现的不够健壮。 ( 6 ) 可伸缩性。空间索引应该能够很好的适应空间数据库的发展变化。 ( 7 ) 时间效率。一维b 树的设计目的就是为了满足这个性能特点：首先， 无论插入顺序以及空间数据的分布，空间索引在最坏情况下的搜索性能应该 保持在某一个水平之上。其次，这种最坏情况对于任意d 个属性的组合都是有 效的。 ( 8 ) 空间效率。空间索引应该比其索引的数据要小，因此需要保证一定 的存储效率。 ( 9 ) 并发性和可恢复性。在现代数据库中多个用户经常同时更新、检索 和插入数据，因此空间索引应该提供强大的事务管理技术以保证数据库的效 率。 ( 1 0 ) 最小影响。将空间索引集成入数据库系统中时对系统其他部分的 影响应当尽可能的小。 传统的空间数据库索引技术有b 树、b + 树、二叉树、i s a m 索引、哈希索 引等，这些技术都是针对一维属性数据的主关键字索引而设计的，并不能直 接应用于空间数据库的索引。因此，设计高效的针对空间目标位置信息的索 引结构与检索方法，就成为提高空间数据库性能的关键所在，。图2 1 给出了 常见的索引结构。 9 哈尔滨t 程大学硕十学位论文 i 了j 二# ：j 二# 二# 嗣叵# 辜j ：t 呐 “矗- 封g 憎母晕o h a 圊皿丑e 棚玉 ： ：f ， w 一 + 一书? # 巴书一，牛卜 斗。 勰恤 t 讥 m m b 一七i m 协置呻上 0 洲哪d 酗 ： ，一f 一一 _ 一 7 ： ，一，一一 一 ! 2 5 1 9 咖 l ：d e 1 - 3 r - m m f卿 ! 遗i 髓t d h i 月， 八趸t 胁磕i l 瑶，一7 n 、- 、 u r 琢吨- - 、 鞋墨柏 t 爱t h ! 翟；刚i j- _ _ 1 j 臻，督 、 f i 1 窘0 恤 ， i 卜r 晋攀 - i 翼 潦 陕l 唏id q l 幽 躲恤 ! ( h 瞄m q “h q 蛔 岫 龄 簧+ z 气， ：胬黼& 8 0 - - 8 9钟9 1昵粥舛舛9 7弼野0 1睨叮 图2 1 常见的索引结构 目前为止已经提出了许多空间索引结构用于支持空间数据的检索，主要 分为三大类： ( 1 ) 空间填充曲线结构。参照一定的线性顺序通过对多维空间中的点进 行排序将多维空间数据映射为一维空间数据，如z 排序曲线结构和希尔伯特 曲线结构。然后检索是通过典型的检索结构完成的，女h b + - 树。 ( 2 ) 基于哈希的网格文件。网格文件适合于处理静态同步分布数据，如 空间影像地图。事实上，由于网格文件会产生许多冗余内容从而浪费许多的 内存和缓存，所以网格文件不适合于高维空间数据的检索。 ( 3 ) 基于树形结构的空间索引结构。在对复杂的空间对象进行索引时通 常使用最小边界矩形( m b r ) 来对对象进行近似的表示，所以一个空间对象只 需占用很少的存储空间。m b r 保留了空间对象的拓扑关系和位置信息从而提 高了基于空间关系查询的检索效率，但它会导致一些空间物体形状信息的丢 失。最早的基于树形结构的空间索引是g u t t m a n 于1 9 8 4 年提出的r 树索引， r 树和t p r 树也是比较常用的索引结构。 1 0 哈尔滨t 程大学硕十学何论文 2 3 典型的空间索引r 树 在多维空间中空间数据因为总是覆盖某一片区域因而不能用点坐标来表 示，比如像国家、普查区域等地图对象往往包括一块很大的二维空间区域。 搜索某一区域内的的所有空间对象是一个对空间数据的常用操作，比如搜索 某学校1 0 英里范围内的所有宾馆。这种类型的空间查询在计算机辅助设计 ( c a d ) 和地理信息系统( g i s ) q b 是尤其常用的，因此如何根据空间位置来快速 有效的得出查询结果是极其重要的。 传统的一维的数据库索引结构并不能e , 很z 好的适应多维的空间数据查询。 像哈希表这种基于精确值匹配的索引结构对空间搜索并不见效是因为空间数 据搜索经常需要在某一个范围之内进行查询。而b 树和i s a m 等基于对一维 关键值进行排序的索引结构同样不适用，这是因为空间数据的搜索空间通常 都是多维的。 目前许多用来处理多维数据的索引结构已经被提出，但是大多数索引结 构都存在着很大的不足。比如，c e l l 方法并不能很好的用于动态的索引结构， 因为c e l l 边界是必须要提前确定的，在动态的索引结构中显然这是非常困难 的。o u a d 树和k d 树没有考虑n - - 级存储的分页问题。k - d b 树是基于分页 存储设计的只适用于点数据。索引区间方法不适用与多维空间。c o m e r s t i t c h i n g 是一种基于二维空间搜索的索引结构适合于检索小型的数据对象， 但该方法在海量数据集上的随机检索效果并不明显。在高维空间中g r i df i l e s 通过将每一个空间对象与一个点进行匹配来处理非点数据。l k d 树可以减少 空间对象的重复存储以及空间映射，该索引通过空间对象的中心点来对空间 对象集进行二分索引，但同样对于非点数据的处理效果并不十分理想。下面 就来就介绍一种称为r 树的可变动态索引结构，该索引利用对象在多维上的 区间来表示空间对象，具有很好的表示效果。 g u t t m a n 于1 9 8 4 年提出了r 树索引m ，r 树与b 树相似都是一颗高度平 衡的树，其叶子结点中的索引项包含了指向实际空间对象的指针。如果索引 是基于分页机制的那么每一个结点对应一个磁盘页面，通过r 树进行空间查 询的时候并不需要遍历所有结点而只需访问其中的部分结点。该索引结构是 哈尔滨t 程大学硕士学位论文 完全动态的，插入操作和删除操作可以和查询操作结合在一起，而不需要定 期的对整个索引结构进行维护。 一个空间数据库由代表实际空间对象的元组集合所组成，每一个元组都 有唯一的标识符用来标识该元组。r 树中叶子结点所包含的索引项形式为( i ， t u p l e i d e n t i f i e r ) ，t u p l e i d e n t i f i e r 用来标识数据库中的元组，i 为包含空间对象 的n 维外包矩形( m b r ) ，i - ( i o ，1 1 ，i n 1 ) 。1 1 表示空间的维数，i i 表示m b r 在 第i 维方向上的长度，取值范围为【a ，b 】，a 和b 都取无穷大表示m b r 在第i 维 方向上无限延伸。非叶子结点的索引项形式为( i ，c h i l d p o i n t e r ) 。c h i l d p o i n t e r 指向其子树的根节点，i 是包含其孩子结点指针所指向的所有下层结点的 m b r 。 假设m 为一个结点所能存储的最大记录数，而m ( m = m 2 ) 为一个结点所 能存储的最小记录数。r 树满足如下特性： ( 1 ) 每个叶子结点包含1 1 1 至m 条索引记录，除非其为根节点。 ( 2 ) 对于每一个索引记录( i ，t u p l e i d e n t i f i e r ) ，i 为t u p l e i d e n t i f i e r 所标识 的1