（计算机应用技术专业论文）基于均值和标准差的空间索引方法研究.pdf

刍 c l a s s i f i e di n d e x ： i u d c ： h 一 ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho n s p a t i a li n d e x m e t h o db a s e do n m e a na n ds t a n d a r dd i v i a t i o n c a n d i d a t e ：l ur u i q i a n g s u p e r v i s o r ：p r o f y a n gj i n g a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：d e c e m b e r2 8 ，2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：m a r c h1 2 ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：、胺0 昂刍 日期：m 卜年弓月，2 ，日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ： 晦啮弓导师( 签字) ；撇 日期：y o 年弓月乞日o h io 年弓月i7 日 哈尔滨t 程大学硕士学位论文 摘要 随着地理信息系统( g i s ) 、图像识别、计算机辅助设计与制造 ( 删洲) 、通信等行业的发展，空间数据库技术的应用也越来越广泛。 空间索引介于空间对象和空间操作之间，是一种辅助性的空间数据结构，通 过它的筛选，能够排除大量与特定空间操作不相关的空间对象，减少运算代 价，提高空间数据库的整体性能，所以它在整个空间数据库中都占有非常重 要的地位。 本文在深入分析研究空间索引的方法和相关技术的基础上，重点分析了 目前应用最多的四叉树和r 树两类主流技术。然后针对基于四叉树和r 树建 立的混合型索引结构q r 树在空间对象更新较频繁的环境中性能下降的不 足，从索引建立和结点分裂两个方面对q r 树进行了改进，给出一种新的索 引方法m v q r 树。 首先，在索引的建立阶段，q r 树是基于数据的当前值建立的，每当数 据变化的时候，都要相应的对索引结构做出调整，势必带来沉重的索引更新 代价。而m v q r 树用( 均值，标准差) 的坐标形式表示空间数据项的每维 数据，只有当前值发生变化的程度超过一定的限度时才对索引结构做出相应 修改，这样就能明显减少索引更新的次数，从而使索引更新代价得到明显的 降低。其次，q r 树中结点的分裂采用的是传统的基于“面积增量最小 的 搜索式二路分裂方法，在形成的索引空间中产生大量的空白区域和重叠区域。 m v q r 树引入k m e a n s 聚类算法对分裂结点进行多路分割，增加了同组对象 的相似度，提高了查询过程中的剪枝速度，改善了索引的查询性能。最后， 进行了仿真实验，实验结果表明，m v q r 树在空间对象更新频繁的环境中具 有较优的整体性能。 关键词：空间索引；q r 树；均值；标准差；k m e a n s 算法 一 j 、 哈尔滨t 程大学硕十学位论文 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fg e o g r a p h i ci n f o r m a t i o ns y s t e m s ( g i s ) ， i m a g er e c o g n i t i o n ，c o m p u t e r - a i d e dd e s i g na n dm a n u f a c t u r i n g ( c a d c a m ) ， c o m m u n i c a t i o n si n d u s t r y , t h ea p p l i c a t i o n so f s p a t i a ld a t a b a s et e c h n o l o g y f i e m o r ee x t e n s i v e s p a t i a li n d e xw h i c hr a n g e db e t w e e ns p a t i a lo b j e c t sa n ds p a t i a l o p e r a t i o n s ，i sas u p p l e m e n t a r ys p a t i a ld a t as t r u c t u r e t h r o u g hi t ss c r e e n i n g , al a r g e n u m b e ro fs p a t i a lo b j e c t sw h i c hi sn o tr e l a t e dt os p e c i f i cs p a t i a lo p e r a t i o n sa r c r u l e do u t ，i tc a l lr e d u c eo p e r a t i o n a lc o s t sa n di m p r o v et h eo v e r a l lp e r f o r m a n c eo f o p e r a t i o n a lc o s t sa n di m p r o v et h eo v e r a l lp e r f o r m a n c e t h e r e f o r e ，s p a t i a li n d e x o c c u p i e sav e r yi m p o r t a n tp o s i t i o ni nt h ef i e l do fs p a t i a ld a t a b a s e i nt h i sp a p e r , a f t e rt h ei n - d e p t hs t u d yo fs p a t i a li n d e x st h e o r ya n dr e l a t e d t e c h n o l o g i e s ，w ef o c u so nt w ot y p e so fm a i n s t r e a mt e c h n o l o g i e sw h i c ha r e q u a d - t r e ef a m i l ya n dr t r e ef a m i l y q r - t r e ei sah y b r i ds p a t i a li n d e xw h i c hi s b a s e do nq u a d t r e ea n dr t r e e c o n s i d e r i n gt h ei n a d e q u a t eo fq r - t r e es u c ha s p e r f o r m a n c ed e g r a d a t i o n i nt h e f r e q u e n t l yu p d a t e de n v i r o n m e n t ，i n d e x e s t a b l i s h i n ga l g o r i t h ma n dn o d es p l i t t i n ga l g o r i t h ma r ei m p r o v e di nt h en e wi n d e x w h i c hi sc a l l e dm v q r t r e ei nt h i st h e s i s f i r s t l y , i nt h ei n d e xb u i l d i n gp h a s e ，q r t r e eb a s e do nt h ec u r r e n tv a l u ew i l l r e s u l ti nt h ei n d e xu p d a t ee v e r yt i m ead a t av a l u ec h a n g e s ，s oi ti sa f f e c t e db y h u g eu p d a t eo v e r h e a d b u ti nt h em v q r t r e e ，e v e r yd i m e n s i o no fs p a t i a ld a t a i t e r n si sr e p r e s e n t e db y ( m e a n ，v a r i a n c e ) c o o r d i n a t e t h em v q r t r e ec a nr e d u c e t h en u m b e ro fi n d e xu p d a t el a r g e l ya n dr e d u c eu p d a t eo v e r h e a ds i g n i f i c a n t l y s i n c et h ei n d e xi sa d j u s t e do n l yw h e nt h ed a t am o v e so u ti t si n t e r v a l t h eq r t r e e b a s e dt h et r a d i t i o n a lh i e r a r c h i c a lm e t h o d s ( m i n i m i z a t i o no fa r e ae n l a r g e m e n t ) t o s p l i tan o d ew h i c ho v e r f l o w si n t ot w on e wo n e sb r i n g sl o t so fi n v a l i dr e g i o na n d o v e r l a p p i n gr e g i o n i nt h ei n d e x s p a c e m v q r t r e ei n t r o d u c i n gk m e a n s c l u s t e r i n ga l g o r i t h mt os p l i tt h en o d eb ym u l t i p a t hs e g m e n t a t i o nc a ni n c r e a s e d ， 哈尔滨t 程大学硕士学位论文 t h ed e g r e eo fs i m i l a r i t yw i t ht h eg r o u po fo b j e c t s ，i m p r o v et h eq u e r ys p e e do ft h e p r o c e s so fp r u n i n ga n dg e ta b e r e rq u e r yp e r f o r m a n c e i nt h ee n d ，s i m u l a t i o n e x p e r i m e n t sa l ec a r r i e do u t t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h em v q r - t r e e h a sab e t t e ro v e r a l lp e r f o r m a n c ei nt h ee n v i r o n m e n to fs p a t i a lo b j e c t sw i t h 矗e q u e n tu p d a t e s k e y w o r d s ：s p a t i a li n d e x ；q r - t r e e ；m e a n ；s t a n d a r dd i v i a t i o n ；k - m e a n sa l g o r i t h m 哈尔滨t 程大学硕十学位论文 目录 第1 章绪论1 1 1 研究背景及意义”1 1 2 国内外研究现状2 1 3 论文的研究内容”4 1 4 论文的组织结构4 第2 章空间数据索引技术的研究与分析6 2 1 空间数据索引技术的理论基础“6 2 1 1 空间数据的概念及特点6 2 1 2 空间对象近似表示技术7 2 1 3 空间检索处理的过程9 2 1 4 空间索引设计相关问题研究- 1 0 2 2 常用空间索引结构的研究1 1 2 2 1 点四叉树1 1 2 2 2 网格四叉树1 3 2 2 3r 树1 4 2 2 4r 宰树”1 7 2 2 5o r 树1 9 2 3 本章小结2 2 第3 章一种基于均值和标准差的空间索引方法2 3 3 1 问题的提出2 3 3 2 改进方法的基本思想2 4 3 3m v q r 树索引结构的建立2 4 3 3 1m v q r 树的结构”2 5 3 3 2 确定均值和标准差2 7 3 3 3 动态调整均值和标准差”2 8 3 4m v q r 树索引结构结点的分裂”2 9 哈尔滨t 程大学硕+ 学位论文 3 4 1 优化k 值的几个相关概念”2 9 3 4 2 利用k m e a n s 算法进行多路分裂3 0 3 5m v q r 树索引结构数据更新过程3 2 3 6m v q r 树索引结构数据查询过程3 5 3 7 本章小结“3 6 第4 章实验结果与分析3 7 4 1 仿真模型3 7 4 2 实验环境”3 8 4 3 仿真实验及结果分析3 8 4 3 1 更新性能的对比3 9 4 3 2 查询性能和总体性能的对比4 0 4 3 3 更新频率对索引性能的影响”4 1 4 3 4 标准差扩展因子对索引性能的影响4 3 4 4 本章小结4 5 结论”4 6 参考文献4 7 攻读硕士学位期间发表的论文和取得的科研成果5 2 致谢一5 3 哈尔滨t 程大学硕十学位论文 ii i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 宣i i i i i i i i i i i 宣i i i i i i i i i i i i i i 第1 章绪论 1 1 研究背景及意义 在当今信息变革的时代，信息技术也在不断的发展，人们所获得的信息 量正在呈现出飞速的增长，为了从这些复杂而巨大的数据集合中来获得最大 的价值，用户就需要借助一种技术来简化这些数据信息的组织，存储和检索 工作，以实现对海量数据的有效地组织，快速地存取，便捷地更新。否则， 数据就失去了存储的意义变成了一种负担，从数据本身挖掘出来的有用价值 将远远超过读取和管理它们的代价。目前的主流方式就是采用数据库管理系 统来管理数据文件以实现对数据信息高效的存储，处理，检索和更新l t l 。 空间数据库系统是描述与特定空间位置有关的真实空间对象的数据集 合，它不仅实现了在d b m s 中存储空间数据的目的，而且能够支持空间数据 的结构化查询和分析，可以高效的把这些空间信息在软件的工作空间中复原 出来。目前，空间数据库的应用已经非常的广泛，如机器人、计算机视觉、 图像识别、环境保护和地理信息处理等多个应用领域都较多的设计到了空间 数据库。随着数字城市，数字地球等概念的提出和应用，空间数据库，尤其 是海量数据的空间数据库，必将具有更广阔的应用市场1 2 1 。 由于空间对象极其复杂，空间数据本身的数据量极大，针对于空间对象 的各种运算代价昂贵，然而现实生活中计算空间关系的处理要求却越来越多。 在空间检索处理的过程中会涉及到复杂的数据类型，它比在传统数据库中单 纯的属性数据的查询要复杂很多，空间数据检索的效率是目前空间数据库性 能的瓶颈。如果能够在各种检索操作之前加入空间索引将待检索的空间对象 进行过滤，则就能大大减少检索操作所涉及的空间对象的数量，避免了大量 复杂的操作，提高空间数据库的性能【，l 。 虽然传统的数据库索引技术已经相当成熟也获得了巨大的成功，但是它 们都是针对一维数据的某个( 些) 属性值设计的，对依赖相互之间的拓扑关 系进行存储的多维空间数据则显得无能为力。这样就使得空间索引机制与传 哈尔滨下程大学硕十学位论文 i i i i i i i i i i i i i i i i i i i i 宣i i a l |wi i 统索引机制不同，业内专业人士普遍认为，许多的对传统数据有效的索引方 法不能高效的应用在空间数据之上。因此，为海量、复杂的空间数据建立索 引显得尤为重要i q 。 1 2 国内外研究现状 空间数据库的研究方向包括空间多维索引、空间数据模型、空间查询优 化、空间拓扑分析、空间查询语言和空间数据的可视化查询等。空间多维索 引是空间查询优化和空间拓扑分析等操作的基础，也是提高这些操作效率的 关键。由于在整个空间数据库中占有重要地位，空间索引一直是空间数据库 研究的重点。尤其是近几十年来，在信息压缩技术、数据挖掘技术和数据仓 库技术的推动下，针对空间数据本身的特点以及空间数据查询的特点，国内 外出现了高维空间索引的研究热潮，相继地提出了多种空间索引结构与索引 方法1 5 1 。 表1 1 大致描述了空间索引技术几十年来的发展和演变过程，揭示了空 间数据库索引技术发展史上著名的研究成果和目前的发展趋势。本文重点研 究了基于四叉树和b 树的两类空间索引技术。 表1 1空间数据库索引技术的发展演化 研究年代研究成果 基于二叉树 基于b 树 基于哈希基于目标排序 1 9 8 4 年以前k d 树，m k d r 树g r i d 文件基于位置链四 树叉树 1 9 8 6 年至 s k d 树r + 树 b a n g 一文件 z 排序 1 9 8 7 年 m u l t i l y a e rg f 1 9 8 8 年至 l s d 树c e u 树 p l o p 一哈希 1 9 8 9 焦 h b 一树 1 9 9 0 年 g b d 树r 。树r 文件 g r e e n s 树 1 9 9 2 年至t v 树f i l t e r - 树 1 9 9 6 焦 k - 树 2 哈尔滨t 程大学硕十学位论文 b 树是一种比较成熟的索引技术，在传统的基于属性建立的数据库中应 用非常多，也表现出较高的索引性能。但是b 树及其许多的变体对于复杂的 空间数据并不适用，不能起到很好的索引效果【q 。于是g u t t m a n 在1 9 8 4 年对 b 树进行了扩展，提出了可应用于空间数据的r 树索引结构。r 树采用空间 对象的近似描述对它们进行存储和建立索引，减少了大量的几何运算，提高 了存储利用率：且该索引结构有一定的聚类能力，将空间中距离较近或相似 度较高的对象划分到一个分枝上，节省了i o s 消耗【7 】。b e c k m a n 等人又于1 9 9 0 年基于r 树设计了r 木树，它在r 。树机制中加入了强制重插策略，减少了树 中结点的分裂次数，提高了索引的查询性能i 田。1 9 9 4 年k a m e l 和f a l o u t s o s 提 出的h i l b e r tr 树利用h i l b e n 曲线将空间数据在一维上进行排序，并改进了 分裂算法，减少了空间对象的存储空间唧。h u a n g 等人在2 0 0 1 年提出的c o m p a t r 树，采用了更加特殊的结点分裂方法，将空间利用率几乎达到1 0 0 t 1 0 l 。 四叉树也是在国内外应用较多一类空间索引技术。1 9 7 4 年f i n k e l 等人提 出了点四叉树索引结构，它主要用于空间中点状对象的表达和存储，这种索引 结构建立过程简单，查询效率高，但是当进行删除操作时效率非常差1 1 1 i 。m x 四叉树和p r 四叉树都是区域四叉树，只适用于多维空间中的点状对象，采用 线性存储，存储利用率较高，但是建立过程较复杂1 1 2 】。c i f 四叉树是针对索引 空间中的小矩形体和其他形体提出的，并且它不需加入空间映射和目标近似技 术，有较高的查询效率，但是数据量较大时会带来沉重的i o 代价1 1 3 】。超图公 司开发的s u p e r m a p 2 0 0 0 软件采用的索引结构是一种可排序线性四叉树，它利 用独特的编码方式使得索引更利于用s o l 语句进行查询，但是当树结构发生 变化的时候，需要对所有结点重新编码，缺少了一定的灵活性1 1 4 1 。深圳雅都公 司开发的g r o w 平台中部分索引结构也是四叉树，在这种四叉树结构中用二进 制进行索引编码，一定程度上提高了空间对象的检索效率1 1 5 1 。 在实际的应用中，很多索引技术将多种策略进行有效结合，采用的是一 种混合型结构。如x 树加入了超结点的概念，兼顾了r 树层次结构与线性组 织结构的优点，减少了索引空间中重叠区域的面积，提高了查询效率1 1 6 1 。而 c e u 门树将四叉树加入了线性链表的二级索引机制，提高了索引的存储效率 1 1 7 1 。虽然这种采用多种理论基础建立起来的混合索引在一定程度上能提高空 间索引的性能和效率，但是它在综合不同方式优势的同时，也会把每种方法 3 哈尔滨下程大学硕十学位论文 的缺点引进进来。所以在进行混合型索引结构的设计时，定要特别注意对 各种不利因素加以避射t 8 】。 1 3 论文的研究内容 目前s q l 等查询语言面临着海量空间数据的处理，为了对空间检索和拓 扑分析这类涉及到频繁磁盘存取及大量复杂运算的操作进行有效的处理，为 空间数据设计有效的索引机制是非常必要的。经过国内外专家几十年的共同 努力，在空间数据库领域，已经有许多行之有效的索引技术被相继提出，并 且得到了一定的应用。但是经过分析后可知，各类索引技术都有它们自己的 适用范围和优缺点，没有一种索引结构在任何情况下都占据绝对优势，必须 根据实际的应用需求，选择适合的索引方法。同时，应该看到，空间数据索 引技术还处于在不断的发展和完善阶段。目前对于空间数据索引技术及居于 它之上的空间数据查询还存在很多问题有待进一步解决，如动态索引结构的 建立；查询操作中几何过滤方法；复杂空间查询方法的优化；高效索引树算 法的改进等。 针对现有空间索引结构中存在的不足，本文在深入研究各种已有索引技 术的基础上，给出了一种新的索引算法。该算法在索引的建立和结点的分裂 两个方面对原有的q r 树索引结构进行了改进，试图获得更优的索引更新性 能和查询性能。 1 4 论文的组织结构 本论文内容组织如下： 第1 章阐述课题的研究目的和意义、国内外研究现状，最后给出了本文 的主要研究内容和组织结构。 第2 章介绍了空间数据索引技术的理论基础和几种常见的空间索引结 构。在理论基础部分概括了空间数据的特点，对象的近似描述技术，空间检 索的处理过程以及设计空间索引时应注意的问题；在常用空间索引部分主要 介绍了四叉树和r 树两类主流的索引技术，最后还分析了一种混合型索引结 构q r 树，为下一章基于它的改进做好准备。 第3 章是鉴于q r 树的不足之处在索引建立和结点分裂两个方面做出改 4 哈尔滨t 程大学硕十学1 1 i 7 ：论文 进，并提出了一种新的索引结构m v q r 树。其中详细阐述了新索引结构的 建立和结点分裂过程，最后给出m v q r 树的更新和查询算法。 第4 章对前一章给出的m v q r 树索引结构应用i b m 公司的城市模拟器 2 0 版进行性能测试。通过与r 树，q r 树的对比分析，来显示新索引结构在 更新性能，查询性能和总体性能方面的优劣性，最后通过实验论证了更新频 率和标准差扩展因子对索引性能的影响，得出了新索引结构较适用的范围。 结论部分对全文进行总结并对未来工作进行展望。 5 哈尔滨t 程大学硕+ 学位论文 第2 章空间数据索引技术的研究与分析 空间索引方法是空间数据库的一项关键性技术，是快速高效的查询，检 索和显示空间数据的重要指标，空间索引的采纳与否以及它的性能优劣都会 直接影响到空间数据库整体性能嗍。因此，空间索引方法的研究引起了业内 人士的足够重视，各国都投入相当大的资金和力量去开发高效的空间数据索 引，带动了当今世界空间索引研究的热潮。 2 1 空间数据索引技术的理论基础 空间数据库是针对于处理空间数据而提出的，它的数据量极大，有时可 达到吉字节甚至太字节数据量级。对空间数据进行合理的组织和管理是提高 空间数据处理效率的重要途径之一，这已成为空间数据库管理人员，研发人 员和各种终端使用者的共识。空间数据索引技术以及建立在索引之上的空间 检索及其优化算法更是提高空间数据处理效率的重要手段，是空间数据库的 重要组成部分1 2 1 1 。 2 1 1 空间数据的概念及特点 空间数据主要用来描述某个空间事物，一般来说，它是指把地球表面空 间位置作为参照标准，用于描述空间对象的位置、大小、形状和分布特征等 多方面信息的数据。空间数据通常是带有空间坐标的，它不仅能表示对象本 身的空间位置及特征，而且还包含了空间对象之间的拓扑关系等信麒2 2 1 。 空间数据被视为一种特殊的数据，与空间对象的空间位置有关，其最主 要的特征是它的空间性。此外，空间数据还具有以下几个特点： ( 1 ) 结构复杂。一个空间对象可以由个点甚至几千个不规则图形组成， 并且在空间中的分布位置是没有规律的。用一个关系表，以定长的元组存储 这类对象的集合通常是不太可能的。总之，空间操作( 如：合并，相交等) 比传统的关系数据库操作要复杂得多，关系数据库中固定长度的元组并不适 合存储空间数据。 6 哈尔滨t 程大学硕十学位论文 ( 2 ) 动态性。插入和删除操作是以更新交叉存储的。该特点要求有健壮 的数据结构能适应频繁地插入、删除以及更新对象。 ( 3 ) 海量化。电子地图或者g i s 往往需要数千兆字节的存储空间。如 果想对如此大的数据集合进行空间操作，二级和三级存储集成有时是必需的。 ( 4 ) 多维性。即在一个坐标位置上具有多个属性和专题信息。该特点使 得传统数据库索引方法相对于空间数据不再适用。 ( 5 ) 空间算法不标准。目前为止没有标准的针对空间数据的算法，各种 算子严重依赖于应用程序，无标准化的基础算子集合。 ( 6 ) 空间运算符不闭合。进行操作的空间对象集可能是点集，线集也可 能是面集。 ( 7 ) 代价昂贵。虽然空间数据的计算代价会随着应用环境的不同而不同， 但是通常要比传统的关系元素的运算代价昂贵很多。 由此可见，传统的关系数据库技术不适用于空间数据，必须从空间数据 的这些自身特点出发来管理它们。目前为止还没有将空间对象从多维到一维 的直接映射技术，在过去一段时间内，研究人员致力于发展一种多维数据的 存储方法，以便建立高效快捷的空间索引。 2 1 2 空间对象近似表示技术 现实应用中，大量的空间对象形状比较复杂，它们可以是点，曲线甚至 是不规则图形，而且随着组成它们点的个数的增多，形状会变得更加的复杂。 空间数据库中就存储着大量这种形状非常复杂空间对象的数据信息，在进行 检索的过程中如果只进行一次过滤就能从所有数据中挑选出满足查询条件的 查询结果，那么可能需要很长的时间去等待计算机的处理过程，这是各种终 端用户不能忍受的1 2 4 l 。为了有效降低检索过程中的计算量，通常的空间数据 库加入了空间目标近似技术，用一个简单的最小外包形体去近似的表达空间 对象，这些简单形体可以是圆，矩形或者多边形。查询的时候，先对这些近 似描述做相关的操作，排除掉不可能满足查询条件的对象，然后对余下的对 象提取具体几何信息进行详细计算查看它是否满足条件。这样可以大大减少 查询过程中复杂的空间操作带来的计算量，提高了查询性能。 7 哈尔滨 ：程大学硕十学何论文 日前，常用的目标近似技术有以下几种1 2 6 1 ： ( 1 ) 最小边界矩形，即m b r m b b ( m i n i m u mb o u n d i n gr e c t a n g l e b o x ) ： 它使用能够对目标空间对象进行完全包含的面积最小矩形( 矩形的边要与坐 标轴平行) 来近似表达该空间对象，如图2 1 ( a ) 。 ( 2 ) 最小边界圆，即m b s m b c ( m i n i m u mb o u n d i n gs p h e r e c i r c l e ) ：它 使用能够对目标空间对象进行完全包含的面积最小圆来近似表达该空间对象 如图2 1 ( b ) 。 ( 3 ) 最小边界m 边形，即m b m ( m i n i m u mb o u n d i n gm c o m e r ) ：它使用 能够对目标空间对象进行完全包含的面积最小m 边形( 一般为凸多边形) 来 近似表达该空间对象，如图2 1 ( c ) 。 定义中提到的“矩形”，“圆”，“m 边形 可在多维空间中进行扩展成为 “超矩形 ，“超球 和“空间多面体”。 冈盐 图2 1 二维空间中的e l 标近似 从图2 1 可以看出，如果只考虑近似精度，用最小边界m 边形近似表示 的方法最精确，而且随着m 值的增大，空白区域越少，粒度也越细，近似表 示越精确。但是付出的代价就是，存储开销也会变大。因为对于最小边界矩 形，只需存储近似矩形对角线的两个点坐标，对于最小边界圆，只需存储近 似圆的半径和圆心坐标，而对于最小边界m 边形要存储相似多边形的m 个 点坐标，所以在只考虑存储空间的需求量时，最小边界m 边形是最不利的。 此外，m 边形的构造过程也是非常复杂的。最小边界圆方法只在特殊情况下 近似效果最好，对一般形状的空间对象和查询类型并无任何优势。目前大多 数的空间索引技术采用的是最小边界矩形近似策略1 2 7 1 。 8 哈尔滨丁程大学硕十学位论文 2 1 3 空间检索处理的过程 由于空间对象数据量大且极其复杂的特性使得针对空间对象的操作非常 昂贵，但是空间关系的查询和处理是空间数据库中应用最多的操作。空间检 索处理的过程中会涉及到大量的复杂数据类型，传统数据库所用的针对单纯 的属性数据查询优化技术不能够完全适用于空间数据。尽可能的减少复杂的 几何运算是查询优化技术的出发点，如何进行查询优化从而提高检索效率是 当前空间数据库的一个重要研究内容。 如图2 2 所示，空间查询处理的过程一般分为过滤和求精两个步骤。从 图2 2 中可以看出在过滤阶段，空间索引起到非常重要的作用，查询处理器 首先对它进行访问。空间索引是根据空间对象的近似描述建立的，通过相关 操作可排除掉那些不可能满足条件的对象，余下的可能满足查询条件的空间 对象构成了候选集，这就是过滤阶段所做的工作。这一阶段过滤掉的对象集 的大小与近似技术的精度有关，近似精度越高，就能越多的过滤掉非结果目 标，从而减少后面的不必要的复杂空间操作。下一阶段的求精步骤首先加载 候选集中空间对象的精确几何信息，然后利用复杂的计算几何算法测试它们 是否满足查询条件，最后把符合要求的结果集输出嗍。 过滤求精 图2 2 空间检索的处理过程 9 哈尔滨t 程大学硕十学位论文 2 1 4 空间索引设计相关问题研究 空间索引就是指在空间数据的存储过程中依据空间实体的形状和位置信 息或者它们之间存在的空间关系，按照一定的顺序进行排列形成的一种数据 结构，当中包括空间实体的简要信息( 如最小边界矩形，实体的标识等) 和 对空间实体进行定位的指针1 2 9 1 。空间索引作为介于空间对象和空间操作算法 之间的一种辅助性空间数据结构，可筛选排除掉大量与特定空间操作不符合 的空间对象，减少很多的运算代价，提高了空间定位的准确性和空间查询的 效率。 鉴于空间数据的众多特点，一个效率较高的空间索引结构应满足基本要 求如下1 3 0 l ： ( 1 ) 可扩展性：即索引机制的索引效率不应随着数据量的增大而降低， 更重要的是不应该受到空间数据维数的严重影响。目前存在的许多索引在这 方面都存在不足，它们的索引性能会随着空间数据维数的增加而大大降低。 ( 2 ) 时间高效性：执行空间检索的时间复杂度要低于线性复杂度。 ( 3 ) 空间高效性：索引所占的存储空间不易过大，应该小于空间数据本 身所占的存储空间。 ( 4 ) 操作顺序无关性：索引的效率应该与数据的分布状态，以及插入索 引的顺序无关，尤其是各维的数据分布不同时，这种特性则显得尤为重要。 空间索引是空间数据库的关键技术之一，它的优劣直接影响到空间数据 库的整体性能。进行高效空间索引的设计时，还应注意以下几个基本问题1 3 1 】： ( 1 ) 描述空间对象时采用的何种近似技术。现实世界中的空间对象形态 多种多样，大小不定，分布区域也是不均匀的，为了降低各种操作的计算量， 在建立索引之前应该采用一种可将空间对象近似表示为简单几何图形的近似 技术。采用什么样的近似技术是设计者应该考虑的首要问题。 ( 2 ) 是否将空间对象进行转化。建立索引时对空间对象的处理主要有两 种方法：一种是不做转化，直接为空间对象建立索引；另一种是使用转化法， 把多维空间的对象经过合理的转化变为低维或更高维的对象再建索引。 ( 3 ) 对空间对象还是对它占据的空间进行分割。由于这两种分割方法都 有各自的优缺点，所以在设计空间索引时应该慎重考虑。 1 0 哈尔滨t 程大学硕士学位论文 ( 4 ) 是否考虑辅存。早期空间索引结构( 如k - d 树等二叉树) 不支持 辅存，所以它们对海量存储的空间数据库并不适合。后来的索引结构在继承 这些索引基本思想的基础上演变成支持辅存的多元树。支持辅存的索引虽然 对硬件的要求较高但是它能使逻辑上相邻的空间实体在物理存储上依然相 邻，提高了索引的查询性能。 ( 5 ) 动态还是静态。在上一节中提到空间索引具有动态构造的特征，该 特征要求支持动态的更新以使得索引和数据库保持一致。但是在更新操作增多 的过程中，索引的动态更新可能会引起总体性能下降，甚至到达人们无法容忍 的地步。有的空间数据库更新操作较少，可不采用动态索引对数据逐个插入， 而是利用静态的方法对成批数据建立预处理然后一次性完成索引的构建。 基于以上所提出的问题，再综合考虑空间数据本身的特点以及现实生活 中的不同应用环境之后，国内外学者开发了许多高效的空间索引技术。目前 空间数据索引技术还在不断的发展和完善阶段，随着人们研究的不断全面和 深入，针对某些特定应用环境的高效索引技术正在受到不同程度的关注，此 类高效的索引结构也在相继被提出。 2 2 常用空间索引结构的研究 迄今为止人们提出了众多的索引技术，包括k - d 树、k - d b 树、r 树及 其变形树、四叉树及其变形树、网格等1 3 2 - ：b i 。目前比较主流而且在国内外空间 数据库中应用最多的是r 一树系列和四叉树系列。如i n f o r m i x 和o r a c l e9 i 数据 库中用的是r 树索引技术，s m a u w o r l dg i s 和o r a c l e8 i 中采用的是四叉树索 引技术，而o r a c l es p a t i a l 和g e o b e a n s 则同时采用这两类索引方法。 2 2 1 点四叉树 点四叉树于1 9 7 4 年由f i n k e l 和b e n t l e y 提出，它与k - d 树类似是一种针 对空间点的索引结构，两者的区别在于点四叉树将空间划分为分别对应于 s w ，n w ，s e ，n e 象限的4 个矩形。当索引空间为k 维时，以新插入的点 为中心将对应索引空间划分为2 k 个子空间，这些子空间要两两不相交且依次 与2 k 个孩子结点相对应，如果某一子空间有点对象，则将对应的子树分配给 它。点四叉树中的每个结点除了存储对应空间点的信息之外还要存储2 k 个孩 1 1 哈尔滨_ t 程大学硕士学位论文 子结点的指针。图2 3 是二维空间的一棵点四叉树的例子。 ( o ，1 0 0 )( 1 0 0 ，1 0 0 ) c ( 舳，8 5 ) b ( 1 0 , 7 0 ) a 5 5 ，5 5 ) f ( 2 0 ，4 0 e ( 9 0 , 3 0 j i x 4 0 , 2 0 ) ( o o ) ( 1 0 0 , 0 ) ( a ) 平面图 ( b ) 结构图 图2 3 点四叉树示意图 以图2 3 为例，点四叉树的构造过程如下所示： ( 1 ) 输入第一个空间点a ，因为此时四叉树为空，所以可把它作为对应 整个索引空间的根节点。再以a 为中心，将整个索引空间划分为分别与它的 4 个孩子结点对应的s w ，n w ，s e ，n e4 个象限。 ( 2 ) 输入空间点b ，可判断出b 落入a 的n w 象限并且此时a 的n w 象限内无空间点，所以b 作为n w 孩子结点，同理可得，d 作为a 的s w 孩 子结点。 ( 3 ) 输入空间点f ，因为f 落入到a 的s w 象限，但是此时的s w 象 限已经有空间点d ，需要继续往下查找，判断出f 落入了d 的n w 象限且它 的n w 象限此时没有空间点，所以最终d 可作为b 的n w 孩子结点。 ( 4 ) 按照前面的方法得出：c 成为a 的n e 孩子结点，e 成为a 的s e 孩子结点。 点四又树的优点是：构造过程比较简单，查询效率较高。缺点是：结点 删除时操作复杂，索引结构没有良好的动态性；平衡性不高，树的结构与点 对象的插入顺序有关：当空间对象为非点状时，要加入空间映射和目标近似 技术，性能更差；区域检索效率不高。 1 2 哈尔滨t 程大学硕十学位论文 2 2 2 网格四叉树 基于固定网格划分的四叉树是一种满四叉树索引结构。以二维空间为例， 该索引结构把整个索引空间的长和宽以x 轴和y 轴方向为基准进行等分， 形成由2 n x 2 n 个网格构成的棋盘状矩形。这种四叉树索引就是以这些网格为 基础进行构建的。在这种索引结构中，空间对象的标识i d 记录在它所覆盖的 每个叶子结点中，但是同一个父亲结点的四个孩子都对某一空间对象的标识 i d 做记录时，只需将i d 记录在父亲结点上即可。并按照这种规则一层一层 进行推进。如图2 4 所示，它是n = 2 时的一个基于固定网格划分的四叉树示 意图。 结点0 图2 4n = 2 时基于固定网格划分的四叉树示意图 在图2 4 中空间对象r 1 的最小边界矩形同时覆盖了兄弟结点5 、6 、7 、 8 所对应的子空间，按照前面提到的规则，只需要在它们的父亲结点即1 号 结点的索引结点表中记录r 1 的i d 标识；空间对象r 2 的i d 标识在结点1 0 和1 2 的索引结点表都要做记录；同r 1 类似，空间对象r 3 的i d 标识记录在 结点1 7 、1 8 、1 9 、2 0 的父亲结点( 结点4 ) 的索引结点表中；图中唯一的点 空间对象p 1 的i