（计算机软件与理论专业论文）rknn搜索在空间数据库应用中的研究.pdf

山东大学硕士学位论文 摘要 随着i n t e r i l e t 以及w e b 的迅速发展，使得网络上的信息量无比丰富，如何从 海量的网络信息资源中及时、准确地找到所需的信息成为当今的一个研究热点。 而实际上，一方面用户不得不忍受在海量的信息中搜索自己想要的信息的痛苦， 而另一方面，信息发布者却希望对自己的信息感兴趣的用户能够迅速的接收到信 息。所以，一个有效的解决方法是信息发布者只把信息发布给那些有可能对这些 信息有兴趣的用户。 随着空间信息科学的发展，地理信息系统等方面的应用越来越广泛，作为空 间科学的重要分支之一，地理信息系统在很多应用中都需要求给定对象的r k n n ， 它在智能导航、现代通讯、交通控制、气象预报等各个领域都有着广泛的需求。 在现实生活中，大部分数据都具有空间属性，例如，地址、客户统计分布数 据或者资产分布数据等等。利用这些数据信息的空间属性进行数据分析，可以观 察发展趋势，帮助您掌握机遇。总而言之，能够迅速有效地管理空间数据，并根 据其空间属性进行分析，对于当今的企业来说，是势在必行的。尤其是在邮电通 信、城市规划、公安交通等领域，空间属性比普通数据扮演着更为重要的角色 n 5 。 空间数据库自身也有很多特殊性，首先，空间数据对象有着复杂的数据结构， 因为对于空间对象的描述除了有几何信息外，还有其它非空间的属性。因此，空 间数据库通常都非常巨大；其次，空间数据对象常常是动态变化的，对于它们的 插入、删除和更新交错进行，而且由于空间数据的次序难以有统一的标准，所以 对其动态的管理难度很大。 l i l 【n n 搜索在空间数据库中有十分重要的应用，如g i s 、生物基因研究等领域。 然而现有的r k n n 算法一般都是近似的解法或则仅仅适用于某种特定的情况，因 此在一定程度上存在以下的不足和缺陷：仅适用于二维空间数据的求解；对k 的值有限制：仅仅支持静态数据而不支持数据库的动态更新，尤其移动对象数据 库；仅能得到近似不能得到精确的结果。 而相对于r k n n 问题，k n n 问题不仅研究得较早，而且对于它们的商业应用 已经相当的广泛，所以相对于础n n 而言，k n n 问题的研究已经相当成熟，而且 山东大学硕士学位论文 存在较理想的算法。但遗憾的是，在一般情况下k n n 与r k n n 之间并不存在任何 直接的转换关系，即r n n s ( q ) 并不意味着r r n n s ( q ) 。不过通过研究我们发现， 在一定的条件的情况下，r n n ( q ) n n ( q ) 和r k n n ( q ) k n n ( q ) 。即我们可以把r k n n 求解问题转化为k n n 求解问题，通过相对来说成熟的k n n 算法，最终达到求解 r k n n 的目的。基于此，本文提出了一个利用已有的k n n 算法，在三维空间内能 够支持数据更新且适合任意k 值的r k n n 算法。 关键词： k 洲：r k 洲：r 。t r e e ；空间数据库：地理信息系统 l l 山东大学硕士学位论文 a b s t r a c t w i l l lt l l er 印i dd e v e i o p m 跚no fh l t e m e t 肌dl l l e 协，t h e r ei s 肌a b l 】i l d a n c eo f i i l f o m 培五o n p f o v i d e d i n 谢。璐w 锣s n h 镐b e c o m e a h o t s p o t h o w t o f 抽d t l l e i i l f o f i 】嘣t i a c c i l 翰l e l y 锄dp r o m p n yf b mm 雒s i v er e u r c e si nt l l en e t w o r k hf 缸t ， w i l i l eu s e r sa 化s 幽r i i l g 缸吼s e 幽gw h a tt l l e ) rn di n 辄c hm 嬲s i v ei i l l 晒咖撕o n ， p r o v i d 哪a 1 坝m t t h e i ri n f b 珊矗i i o nq l l i c l 【l yr e c e i v e db yt i l ei n t e r e s t e di i li t a n e f f 枷v em e m o di s 蕾0r e l e 嬲ei l l 】e b 嘣0 no n l yt ou s e 璐w h om i g h th a v ei n t e r e s ti i li t a s1 l l ed e v e l o p n 啪to fs p 撕a li n f b 瑚觚t e c l l l l o l o 拶，a p p l i c 撕o no f g e o g m p l l i c i i l 两m l a t i o n 科s t e m sh 嬲b e c o m ew i d e r 锄dw i d e r a so l l eo f t l i e 加o s ti r r 罐 o r t a m b r 蛆c h e so f 印a t i a ls c i e n c e c e n a i l lr k n ni s 根皿r e di np m c t i 阢r k n ni sp o p l l l a ri i l i l l t e l l i 窖即tn a 访g a 石o i l ，m o d e mc o m m l | 1 1 i c a d s ，订缅c 咀t r o l ，w e a 血e rf o r e c 枷n g a n do m e ra r e 嬲 h ip m c t i ，m o s td a t a ( o v e r8 5 ) h 嬲s p a l i a l 枷b l l t e s ，跚c h 髂a d d 陀s s 髂，协l e p h o n e n 啪b e 巧，c u s t o m e r d i s t r i b u d 帆o rd i s 住i b l i i i o no f a s 辩协，e t c s u c ha t 仃j b u t e sc a n b e u d t o o b s e r v e t l l e 仃锄d 觚d 协掣唧m e o p p o m m i l y h 幽o r t ，s 谢f t 肌de f f 硎v e m 缸a g e m to f s p 撕a ld a _ t a ，删b u t e 血e i rs p 勰髓a l y s i s i ti s 曲l u t e l yn e c 器鞠i y f o r t o d 帮s t e r p r i s t o 锄a l y 船t l l e a 删b u t 鼯o f s p a l i a ld a l a 锄d a r 瑚g e l l l e d a t a 鲥酬v e l y 锄dp m m l ) n y w h a r si n o r e ，辄c hs p a l i a la 土t 曲u 钯p l 掣al n o 豫i l i l p o n a n t r o l e1 h a nd a t ai t s e 屹唧e c i a l l yi i lf i e l d so f t e l o m m i | i l i c a d o ，u r b a np l a n l l i n 岛p u b i i c c o m m i l i c a t i o 哪，p 咖l e 哪g l o 影，锄d s p a t i a ld a t a b 船eh 罄i 拓。伽s p e c i f i c 时f i r s t l y ，t l l es n l 劬鹏o fd a t a 州e c t si s m p l i ti sb e c a u t l l a tm 豇ea mm a n yo t h 盯n o n - s p a l i a l 砌b u t e s i i lt l l e d e s c r i p t i o f m eo b j e c t 印a r t 丘o mt l l eg e o m e 仃i ci n f o n n a 吐0 n a sa s i l l t ，s p a 五a l 出i t a b a sa r el l s ；i l a l l yv e r yg r e 甜s e c o n d l y ，d a ：七ao b j e c t sa r eo 邱md y n a i l l i c ，w i t l l i l l s e 币，d e l e t i o n 锄di i p d 砒es t a g g e r e d s i n c ei ti sd i 衔c u n t of i n da 硼j f i e ds t 锄d a f d f o r t i i es e q 唧c eo f s p a t i a ld a t a ，d y l l a l i l i cm e m o 猡i sq l l i t ed i m c l | l t m 山东大学硕士学位论文 g f e a ti m p o r t a n c eh 嬲b e e na 士t h e d 幻r k n ns e a r d li nm i i l 在d i m 饥s i o n a ls p a d a l d a t a b a s e ，f o re x 锄p l e 洫g i s ，c a d ，m l l l t i m e d i ad a t a ，肌di i lg 朗o m er e s e a r c h h o w e v e r ，t h ee 菇s t i n gr k n na l g o r i t l l m sc a l lg e n e r a l l yg e ta p p r o ) 【i m a t er 髂i i l t s ，o ri s a p p l i e do i l l yi i lc e r t a i l ls p e c i f i e dd f c u m s t a i l c 嚣s oi i l i n ee ，【t 锄tt l l e r e 盯e d e f i c i 肌c i e s ：s o m ec 趾b ea p p l i e s0 1 1 l yt om e l l i t i o f 伽o - d i m e 戚o n a ls p a l i a ld a t a ， 、】v i l l lm ev a l u eo f kr e s t r i c t e d ；s o m es u p p o r t 伽崎s t a d cd a a b 勰豁b l l t 由n a l l l i c u p 幽n g ，p 枷c i l l a l l ym o 、，i n go b j e c 乜d a t a b 罄e ；w l l i l e m ea l g o r i l l i l 琊d o n tl e a d 切 c l l r a t eb u ta p p r o ) d m 砒er 嚣l l l t s c o i n p a r e d 埘t ht l l er 心ni s s s ，k n ni se 嬲i e rt oa c h i e v e ，n o to n l yb e c a u i t s s t i l d i e de a l l i e r ，b u ta l s 0b e c a l l s ei th 嬲f b 咖e dr e l a t i v em a t l l r et l l e o r ya i l da l g o r i t h l m u n d e rn o m a lc i r c u i i l s t a l l c 髂，t l l e r ei s d i r e c tr e l a d o n s h i p b e t w e e i lk n n 趾d 础n m t h a t i sr n n s ( q ) d o 嚣n o t m e a nr r n n s ( q ) b u t i t c 锄b e p r o v e d t l l a t i nc e r t a i n c o n d i d o n s ，i 心t n ( q ) n n ( q ) 卸d r k n n ( q ) k n n ( q ) n m e 锄s t l l a t w ec a i l p m al u ( n ns o l i n i o ni n t oak n n l u t i o l l ，o rs o l v ear k n n p r o b l 唧1 l l i o u g hr e l a t i v e l y m = t i l r ek n n a l g 嘶t h i i ls o l v i i l gr k n ni l l 石r r i a 士e l y l l i e v em ep u f p l o s e b 勰e d 1 l l i s ， 1 l l i s p a p e r p r e s t s a r 心a 1 9 0 r i d l l i l 戚n g o f t 量玲l d 蝌i i l h 锄d ，w h i c hc a l ls u p p o r t l l p 捌n go f t l l ed a t ai l l1 l l r e e - d i m e n s i o n a ls p a c e 觚di ss l | i t a b l ef o ra r l ykv a l u e k e y w o r d 8 ：k 洲：r k 洲：r l t r e e ：s p a t i a id a t a b a s e ：g i s 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责 任由本人承担。 论文作者签名：日期：丝z ! ：。 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校 保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文 和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：瑙蚰师签名 论文作者签名：掣碰i 篷持师签名 ，7 r 日 期： 64 f fo 山东大学硕士学位论文 1 1 研究背景 第1 章绪论 随着i n t e n l e t 以及w e b 的迅速发展，使得网络上的信息量无比丰富，如何从 海量的网络信息资源中及时、准确地找到所需的信息成为当今的一个研究热点。 而实际上，一方面用户不得不忍受在海量的信息中搜索自己想要的信息的痛苦， 而另一方面，信息发布者却希望对自己的信息感兴趣的用户能够迅速的接收到信 息。所以，一个有效的解决方法是信息发布者只把信息发布给那些有可能对这些 信息有兴趣的用户。 随着空间信息科学的发展，地理信息系统等方面的应用越来越广泛，作为空 间科学的重要分支之一，地理信息系统在很多应用中都需要求给定对象的r k 眦 它在智能导航、现代通讯、交通控制、气象预报等各个领域都有着广泛的需求。 在现实生活中，大部分数据都具有空间属性，例如，地址、客户统计分布数据或 者资产分布数据等等，利用这些数据信息的空间属性进行数据分析，可以观察发 展趋势，帮助您掌握机遇。总而言之，能够迅速有效的管理空间数据，并根据其 空间属性进行分析，对于当今的企业来说是势在必行的。而且在邮电通信、城市 规划、公安交通等领域，空间属性比普通数据扮演着更为重要的角色 1 5 。 而r k n n 搜索在空间数据库中有十分重要的应用，如地理信息系统、生物基因 研究等领域。然而，由于空间数据库自身有很多特殊性，所以对于空间数据库的 各种搜索还存在许多困难。首先，空间数据对象有着复杂的数据结构。因为对于 空间对象的描述除了有几何信息外，还有其它非空间的属性。因此，空间数据库 通常都非常巨大；其次，空间数据对象常常是动态变化的，对于它们的插入、删 除和更新交错进行，而且由于空间数据的次序难以有统一的标准，所以对其动态 的管理难度很大。所以目前对于空间数据库的各种搜索还存在许多困难，尤其是 r k n n 搜索，目前这一领域的研究仍在不断深入。 k n n 与r k n n 问题的解决方案都取决于距离量度的选择，本文采用的是n 维欧 拉空间以及欧拉距离。我们用d 来表示距离量度，即：对于任意两个点p 和q ， 它们之间的欧拉距离记为d ( p ，q ) 。 山东大学硕士学位论文 1 。2 研究现状 对于r k n n 的研究，尤其是对于三维空间内的r k n n ，到目前为止还没有有效 的解决方案可以用于商业应用，还处在理论研究阶段。现有的r k n n 算法一般都 是近似的解决方案或者仅仅适用于某种特定的情况，因此在一定程度上存在以下 的不足和缺陷：仅适用于二维空间数据的求解；对k 的值有限制；仅仅支持静态 数据而不支持数据库的动态更新，尤其移动对象数据库：得到的计算结果不够精 确，仅仅是近似的解决方案。 1 3 研究目标 由于n n ，k n n 问题不仅研究得较早，而且对于它们的商业应用已经相当的广 泛，所以相对于r k n n 而言，k n n 问题的研究已经相当成熟，而且存在较理想的 算法。但遗憾的是，在一般情况下k n n 与r k n n 之间并不存在任何直接的转换关 系，不过通过研究我们发现，在满足一定条件的情况下，我们可以把r k n n 求解 问题转化为k n n 求解问题。 空间数据一般都采用r _ t r e e 或者其变形进行索引，但是如果对三维空间数 据直接采用r - t r e e 进行索引，则r t r e e 结构将变得相当复杂，操作起来效率也 非常低下。由于r t r e e 在求解三维空间k n n 问题上的不足，本文提出了一个新 的空间索引技术r 6 - t r e e 。r - t r e e 索引在采用r - t r e e 用来索引二维数据的 基础上，外加一个线性表来存储第三维数据，最终达到索引三维空间数据的目的。 相比于直接对三维空间进行r t r e e 索引带来的插入、删除、更新的复杂性， r 4 _ t r e e 操作起来更加的简洁高效。 基于此，本文提出了一个基于k n n 算法的、采用r 一t r e e 索引的三维空间下 支持数据动态更新的并且适合任意k 值的r k n n 算法 1 4 论文结构 本文分为五章，各章节的主要内容安排如下： 第一章是绪论，主要介绍论文的研究背景、研究现状及本文的研究目标。 2 山东大学硕士学位论文 第二章是数学基础以及相关技术，主要介绍了地理信息系统、空间数据库以 及空间索引技术和n n ，k n n 搜索问题，探讨了r n n 问题的数学性质，并对其进行 数学证明。同时在r n n 基础上给出了r k n n 的数学定义。 第三章是k n n 搜索问题，主要介绍在空间数据库中的k n n 求解方法和当前空 间索引在求解三维空间k n n 问题上的不足。提出了一种新的空间索引r 。_ t r e e ， 并根据该索引提出求解三维空间k n n 问题的一种新的算法。 第四章是基于k n n 搜索算法的r k n n 解决方案，主要介绍在k n n 研究的基础 上的r k n n 问题的求解：提出了一个基于k n n 算法的、采用i 卜t r e e 索引的三维 空间下支持数据动态更新的并且适合任意k 值的r k n n 算法 第五章是总结和展望。对本文进行总结，并指出不足之处以及该领域将来的 研究方向。 3 山东大学硕士学位论文 第二章数学基础及相关技术 2 1 地理信息系统( g i s ) 2 1 1 地理信息系统概述 2 0 世纪5 0 年代由于计算技术的发展，测绘工作者和地理工作者逐渐利用计算 机来汇总各个来源的数据，并借助计算机处理和分析这些数据，最后通过计算机 输出一系列结果，作为决策过程的有用信息。1 9 5 6 年，奥地利测绘部门首先利用 电子计算机建立了地籍数据库，以后许多国家的土地测绘部门都相继发展了土地 信息系统 3 。2 0 世纪6 0 年代为了达到“要把地图变成数字形式的地图以便于计 算机处理分析”的目的，1 9 6 3 年加拿大测量学家r ft o 皿1 i n s o n 首先提出了地理 信息系统( g e o g r a p h i ci n f o m a t i o ns y s t e m ，简称g i s ) 这一术语。2 0 世纪6 0 年代 末，加拿大建立了世界上第一个地理信息系统加拿大地理信息系统( c g i s ) ( b u r r o u g h ，1 9 8 6 ) ，用于自然资源的管理和规划。后来的几十年中问，伴随着计 算机技术和网络技术的迅猛发展，g i s 的应用也日趋深化和广泛，在环境、资源、 石油、电力、土地、交通、公安、航空、市政管理、城市规划等领域成为常备的 工作系统。 地理信息系统是以地理空间数据为基础，在计算机硬件、软件环境支持下， 对空间相关数据进行采集、管理、操作、分析、模拟和显示，并利用地理模型分 析方法，适时提供多种空间和动态的地理信息，为地理研究、综合评价、管理、 定量分析和决策服务而建立的一类计算机应用系统。地理信息系统是图形处理技 术、可视技术及数据库等技术的有机结合，并以其混合数据结构和强大的地理空 间分析功能而独树一帜。 2 1 2 地理信息系统特点 地理信息系统作为计算机系统，具备一般计算机系统所具有的功能，如采集、 管理、分析和表达数据等功能。另外地理信息系统处理的数据都和地理信息有着 4 山东大学硕士学位论文 直接或间接的关系。地理信息是有关地理实体的性质、特、运动状态的表征和一 切有用的知识，而地理数据则是各种地理特征和现象间关系的符号化表示，包括 空间位置，属性特征以及时间特征。空间位置数据描述事物或现象所在位置；属 性数据有时又称非空间数据，是属于一定地物或现象、描述其特征的定性或定量 指标；时间特征是指地理数据采集或地理现象发生的时刻或时段。由此，地理信 息系统可以定义为用于采集、模拟、处理、检索、分析和表达地理空间数据的， 作为有关空间数据管理和空间信息分析的计算机系统。 地理信息系统综合运用了计算机、系统工程、经济管理等多学科知识，属于 跨学科技术系统。地理信息系统的外壳，表现为计算机硬件系统，其内涵却是有 计算机程序和地理数据组织而成的地理空间信息模型。当具有一定地学知识的用 户使用地理信息系统时，将客观世界抽象为模型化的空间数据，用户可以按照应 用的目的来观测这个现实世界模型的各个方面的内容，取得自然过程的分析和预 测的信息，用于管理和决策。一个逻辑缩小的，高度信息化的地理信息系统，从 视觉，计量和逻辑上对地理系统在功能方面进行模拟。信息的流动以及信息流的 结果，完全由计算机程序的运行和数据的变换来仿真，从而可以使得相关领域专 业人员在地理信息系统支持下提取地理系统各不同侧面，不同层次的空间和时间 特征，快速有效的模拟自然过程的演变或思维过程的结果，取得地理预测或“试 验”的结果，选择优化方案，用于管理与决策 1 7 】。 与一般的管理信息系统相比具有以下特征： 1 地理信息系统在分析处理问题中使用了空间数据与属性数据，并通过数 据库管理系统将两者联系在一起进行管理、分析和应用，从而提供了认 识地理现象的一种新的思维方法； 2 地理信息系统强调空间分析，是以空间数据库为基础，采用地理模型分 析方法，适时提供多种空间的和动态的地理信息，通过利用空间分析式 模型来分析空间数据。因此，地理信息系统的成功应用依赖于空间分析 模型的研究与设计。 山东大学硕士学位论文 2 2 空间数据与空间数据库 2 2 1 空间数据库 空间数据库是一个存储空间( 地理) 和非空间数据的数据库系统，在它的数 据模型和查询语言中能提供空间数据类型，可以进行空间索引，并且提供空间查 询和其他空间分析的方法。空间数据库是一种特殊的数据库，与一般数据库最大 的不同是它包含“空间”( 或几何) 概念。 任何事物都有其空间形式和基本特征。作为反映现实世界的数据库，空间属 性应当是数据的基本属性。虽然在某些应用中，空间属性往往是隐含的，没有显 示表现出来，但一般而言，数据也“本质”地表示事物的当前状态，事物的地点 总是在数据库所描述的范围内。因此，从根本上讲，一个数据应当既有非空间内 容，又有空间内容。例如，一个国家至少有一个非空间数据国家名和一个空 间数据国家的边界。 2 2 2 空间对象 现实世界中的对象存在于空间当中，在特定的空间信息系统应用环境中如地 理信息系统、全球定位系统的应用中，我们必须要考虑对象在空间中的位置。这 些将空间物体进行抽象得到的对象称为空间对象( s p a t i a l0 b j e c t s ) 。空间对象 由两方面数据共同构成：与空间无关的描述性数据，通常称为主题属性或属性数 据；对象在空间中的位置，称为空间属性或空间数据。 2 2 3 空间数据特征 空间数据具有下述几个基本特征 3 ： 1 、空间特征：每个空间对象都有空间坐标，即空间对象隐含了空间分布特 征。这意味着在空间数据组织方面，要考虑它的空间分布特征，所以除了通用性 数据库管理系统或文件系统关键字的索引以外，一般都需要建立空间索引。 2 、非结构化特征：在当前通用的关系数据库管理系统中，数据记录一般是 结构化的。即它满足关系数据模型的第一范式要求：每一条记录是定长的；数据 山东大学硕士学位论文 项表达的只能是原子数据；不允许嵌套记录。而空间数据则不能满足这种结构化 要求。若将每一条记录表达一个空间对象，它的数据项可能是变长的。 3 、空间关系特征：空间数据除了前面所述的空间坐标隐含空间关系外，空 间数据中记录的拓扑信息表达了多种空间关系。这种拓扑数据结构虽然一方面方 便了空间数据的查询和空间分析，但在另一方面也给空间数据的一致性和完整性 维护增加了复杂性。特别是有些几何对象，没有记录空间坐标的信息，如拓扑的 面状目标，仅记录组成它的弧段的标示，因而进行查找、显示和分析操作时都要 操纵和检索多个数据文件方能得以实现。 4 、分类编码特征：一般而言，每个空间对象都有一个分类编码，而这种分 类编码往往属于国家标准，或行业标准，或地区标准，每一种地物的类型在某个 地理信息系统中的属性项个数是相同的。因而在许多情况下，一种地物类型对应 于一个属性数据表文件。当然，如果几种地物类型的属性项相同，也可以多种地 物类型共用一个属性数据文件。 5 、海量数据特征：空间数据量是巨大的，通常称海量数据。之所以称为海 量数据，是指它的数据量比一般通用数据库要大得多。一个城市的地理信息系统 得数量可能达到几十个g ，如果考虑影响数据的存储，可能达到几百个g 。这样 的数据量在其他数据库中是很少见的。正因为空间数据量大，所以必须要建立合 理的空间索引以达到提高空间数据库的效率。 2 2 4 空间数据模型 空间数据模型与其它数据模型相比，一个突出的特点就是其模型的提出、引 入与相应的实际应用密切相关。 空间信息系统的一个重要应用领域就是地理信息系统，所以我们就以地理信 息系统为例来介绍空间数据模型。 在地理信息系统中，基本空间数据类型有下述空间对象组成： 1 点：例如城市。点只表示其空间位置，不表示其范围。 2 线：例如河流，街道，通信或者电力线路等。线不仅表示线上各点在空 间的位置，而且还有长度，即表示其在空间的延伸范围。 3 面：例如行政区域。面不但有位置，而且有面积，周长等参数，以表示 7 山东大学硕士学位论文 其覆盖范围。 2 2 5 空间数据库 空间数据库首先是一个数据库管理系统( d b 嬲) ；其次，在空间数据库的数 据模型和查询语言中支持空间数据类型和空间操作；第三，在空间数据库的实现 中支持空间数据类型，提供空间索引，支持空间选择和空间联接。 空间数据库是提供空间对象管理的复杂系统。在空间数据库中，空间对象的 主题属性一般用传统数据类型来表示，而空间数据的管理则需要增加新的空间数 据类型和空间操作。 空间数据库的核心问题是空间数据的表示和操作。空间可以是二维或多维 的。在地理信息系统的应用当中，二维和三维空间数据是最为常见的空间数据。 因此目前对空间数据库的研究也基本上集中于二维和三维空间数据的管理上。二 维空间数据通常包括点、线和面。三维空间数据还包括体。目前对空间对象主要 有两种不同的表示方法：栅格模型和矢量模型。 栅格模型实际中通常以一个栅格来表示个像素点，因此图像通常以栅格数 据的形式存在。栅格模型的优点是可直接利用遥感、数字摄影测量等图像数据， 数据结构比较简单，其方向、邻接及连通计算易实现，但栅格模型对设备的存储 空间要求过高( 一般以栅格图像方式存储) ，而且不存储空间坐标，这使得空间 实体的识别和标识比较困难，查询速度也相对较慢。栅格模型对于按实体组织数 据的数据库来说并不合适。 矢量模型以基本几何对象( 点、线、面，体等) 来表示空间数据。基本几何对 象以采样点的空间坐标表示。例如一个二维空间可以通过一个由区域的边界点构 成的多边形来表示，而三维空间可以通过一个由空间边界面构成的多面体来表 示。矢量模型存储了空间数据的边界坐标，可以方便地表达空间数据之间的空间 拓扑关系。而且在矢量模型中容易对单个目标进行定义和操作。其缺点是不能直 接处理图像数据，而且数据结构相对复杂。矢量模型是目前流行的空间数据表示 方法，在g i s 等应用中得到广泛的应用。 空间数据的操作包括空间拓扑操作、空间几何操作和空间属性操作。空间拓 山东大学硕士学位论文 扑操作即空间谓词，它判断两个空间数据之间的空间拓扑关系并返回t r u e 或 f a l s e 。典型的空间拓扑关系包括相邻、相离、相交、部分覆盖、完全覆盖和包 含等。空间几何操作是对空间数据执行的几何运算，如求空间数据的交、空间数 据的并等。空间几何操作一般将空间数据视作点集，并以集合操作的方式来实现。 空间属性操作计算空间数据本身的特性值，如求面积、周长等。 2 3 空间索引简介 2 3 1 空间索引概论 索引是一种有效的检索手段，其实质是通过比较运算逐步追踪到检索对象。 现有空间索引如r - t r e e 索引一般按点和最小边界矩形硒r 作为搜索对象。 与通常索引比较，空间索引具有以下特点： 1 索引对象的无序性：空间对象一般没有明确的次序，当确认了某个对象 在一个子空间内时，若要进一步搜索，就需要逐个进行比较。 2 索引对象的不规则性：空间对象一般是不规则物体，需要选取适当的规 则图形进行近似。 3 空间对象可以交叉，甚至重叠，一个对象可能属于多个子空间，需要进 行对路搜索。 随着空间数据库的广泛应用，用户对于数据查询速度的要求也在不断提高， 因此采用合理的数据索引模型显得尤为重要。特别是对于地理信息系统，地理数 据本质上十分复杂，而且数据量非常庞大，因此对于空间数据索引的研究一直是 地理信息系统研究的重点之一。 地理信息系统中空间数据库的空间索引结构提供了快速定位目标地理对象 的能力，通过空间索引提高了空间操作的速度和效率。空间索引技术的优劣直接 影响地理信息系统的整体性能，它是地理信息系统的一项关键技术。目前，地理 信息系统处理的大多数空间对象都是静态的空间对象，其空间索引结构一般是自 项向下、逐级划分空间的各种类型数据结构，就是将空间按照规定的网格或其它 分层结构进行分割。分割的方法也有多种，目前国内外研究得较多、常见的有网 格索引、四叉树索引 3 5 和r _ t r e e 系列的索引技术。 9 山东大学硕士学位论文 2 3 2r _ t r 索； r - t r e e 6 是大多数商用数据库( 如0 r a c l e ) 采用的空间索引模型，也是研究 得比较成熟的一种算法。r - t r e e 最早是由g u t t m a n 在1 9 8 4 年提出的，g u t t 唿n 参照 b _ t r e e 的定义形式，给出了r t r e e 的定义。其中设m 为r t r e e 中每个结点最多包 含的结构个数，m 为每个结点包含的最少结构个数，则有m m 2 。此外，r - t r e e 还具有以下特征： 1 每个根结点最少有两个孩子，除非它同时是叶子结点； 2 每个目录结点有m - m 个子结点，除非它为根； 3 每个叶子结点包含的单元个数介于m 与m 之间，除非它同时是根结点。； 4 所有的叶子结点在同一层上。 2 1 1 0 山东大学硕士学位论文 2 2 图2 1 为用r - t r e e 对空间进行划分后空间结构图，图2 _ 2 为对应r - t r e e 的数据 结构。r - t r e e 实际上就是b _ t r e e 的拓展，是一棵平衡的多路查找树，所有的叶结 点都在同一层。r - t r e e 中所有的索引记录都放在叶结点中，它的每个叶子结点由 一个皿r 组成。其中船r ( m i n i 眦1b o d i n gr e c t a i l g l e ，最小边界矩形) 为包含对 应的空间对象的n 维最小矩形。r - t r e e 可以直接对地理空间中占据一定范围的地 理要素进行索引，它按照船r 来索引二维或更高维数的地理对象。在构造船r 时， 应遵循以下原则：尽可能包含多的目标；使它们尽可能少的重叠。船r 还可以继 续细分，即可以再嵌套船r 以形成多级空间索引。r - t r e e 的叶结点存储单个对象 的6 忸r ，以及指向对象空间位置的指针，r 树的结点存储对象或对象集合的船r 。 同时，r - t r e e 索引也是一种动态的索引机制，插入和删除结点不需要完全重 建r - t r e e ，只需要进行局部调整和重构。一般而言数据库将r - t r e e 索引方法内置 于数据库内核并与外延数据类型协作来管理地理数据。 对于每个对象q 和每一个最小边界矩形n 都有三个对应的变量，分别是 m i n d i s t ( n ，q ) ，眦x d i s t ( n ，q ) ，m i 珊a x d i s t ( n ，q ) 。基于i h r e e 的k n n 算法就是基 于此三个变量以及最小边界矩形的性质来完成的。 与标准索引不同的是，r 树并不将整个空间分割成由非重叠相邻单元组成的 完全覆盖，而是使每个对象自动的被完全由空间形状所决定的“矩形”表示，因 此它并不需要覆盖整个空间。 此后，s e l l i s ( 1 9 8 7 ) ，g r e e n e ( 1 9 8 9 ) ，b e c l 【a n n ( 1 9 9 0 ) ，k 锄e l ( 1 9 9 4 ) 和 g a r c i a ( 1 9 9 8 ) 等人在其基础上不断地进行改进，提出了r t r e e 的多种变形，形 山东大学硕士学位论文 成了由r - t r e e 、r + 一t r e e 、r _ t r e e 、s r _ t r e e 、x t r e e 等r t r e e 的变形树组成的一 个r t r e e 类索引体系。 2 3 3r t r 变形 1 、r + - t r e e 2 2 在g u t t m n 的工作的基础上，许多r 树的变种被开发出来，s e l l i s 等提出了 一个r - t r e e 的重要变形树：r 。t r e e 。r + 。- t r e e 与r - t r e e 类似，主要区别在于r + 一t r e e 中兄弟结点对应的空间区域无重叠，这样划分空间消除了r - t r e e 由于允许结点间 的重叠而产生的“死区域”( 一个结点内不含本结点数据的空白区域) ，减少了 无效查询数，从而大大提高空间索引的效率，但对于插入、删除空间对象的操作， 则由于操作要保证空间区域无重叠而效率降低。同时r + 树对跨区域的空间物体的 数据的存储是有冗余的，而且随着数据库中数据的增多，冗余信息会不断增长。 2 、r i - t r e e 2 3 在1 9 9 0 年，b e c k m a n 和k r i e g e l 提出了最佳动态r 树的变种r l t r e e 。 r + _ t r e e 和r t r e e 一样允许矩形的重叠，但在构造算法r 乞t r e e 不仅考虑了索引空 间的“面积”，而且还考虑了索引空间的重叠。该方法对结点的插入、分裂算法 进行了改进，并采用“强制重新插入”的方法使树的结构得到优化。但r 匕- t r e e 树算法仍然不能有效地降低空间的重叠程度，尤其是在数据量较大、空问维数增 加时表现的更为明显。r i - t r e e 无法处理维数高于2 0 的情况。 3 、q r t r e e 2 4 q r _ t r e e 利用四叉树将空间划分成一些子空间，在各子空间内使用许多r 树索 引，从而改良索引空间的重叠。q r _ t r e e 结合了四叉树与r - t r e e 的优势，是二者 的综合应用。实验证明：与r - t r e e 相比，q r - t r e e 以略大( 有时甚至略小) 的空 间开销代价，换取了更高的性能，且索引目标数越多，q r - t r e e 的整体性能越好。 4 、s s _ t r e e 2 5 s s - t r e e 对r 乞- t r e e 进行了改进，通过以下措施提高了最邻近查询的性能：用 最小边界圆代替最小边界矩形表示区域的形状，增强了最邻近查询的性能，减少 将近一半存储空间。s s _ t r e e 改进了r l t r e e 的强制重插机制，当维数增加到5 是， 山东大学硕士学位论文 r - t r e e 及其变种中的边界矩形的重叠将达到9 0 ，因此在高维情况( 乏5 ) 下， 其性能将变的很差，甚至不如顺序扫描。 5 、x t r e e 2 6 x - t r e e 是线性数组和层状的r 树的杂合体，通过引入超级结点，大大地减少 了最小边界矩形之间的重叠，提高了查询效率。x - t r e e 用边界圆进行索引，边界 矩形的直径( 对角线) 比边界圆大，s s - t r e e 将点分到小直径区域。由于区域的 直径对最邻近查询性能的影响较大，因此s s t r e e 的最邻近查询性能优于 r 。_ t r e e ；边界矩形的平均容积比边界圆小，r + - t r e e 将点分到小容积区域；由于 大的容积会产生较多的覆盖，因此边界矩形在容积方面要优于边界圆。x - t r e e 既采用了最小边界圆( 皿s ) ，也采用了最小边界矩形( 船r ) ，相对于s s _ t r e e ， 减小了区域的面积，提高了区域之间的分离性，相对于r 。_ t r e e ，提高了邻近查 询的性能。 2 3 4 其它空间索g 由于r - t r e e 查找总是从根结点开始，即从整个索引空间开始，最坏的查找情 况是遍历整棵索引树( 退化为线性查找) ，最好的查找情况是查找只沿一条分枝进 行。r _ t r e e 有一个重要的特点就是兄弟结点对应的空间区域可以互相重叠，这样 的特性使r _ t r e e 比较容易进行删除和插入操作，但却使空间搜索的效率降低，因 为区域之问有重叠，可能要对多条路径进行搜查后才能得到最后的结果。所以在 移动环境下，大量移动对象不断产生的更新请求，r t r e e 不能够对这些移动对象 进行有效管理。 随着地理信息系统应用领域的拓展与深入研究，在移动应用环境下，地理信 息系统需要处理大量的不断移动的空间对象和并发查询检索任务，因为维护移动 空间对象经常需要执行大量的更新操作，现有空间数据库的索引技术不能很好的 工作。如何管理海量的移动空间数据，提供一个对移动空间对象高效索引机制是 目前迫切需要研究的一个关键问题。 就空间索引技术而言，国内外一些研究者最近提出来了一些新的能够处理移 动对象的索引结构，其中较好的一种是把时间当作为一维坐标来看待，这样移动 对象在d 维的空间转换成在d + 1 空间问题。例如，j e n s e n 和t h e o d o r i d i s 提出的 山东大学硕士学位论文 s t r t r e e 6 ( t r a j e c t o r yb u n d l et r e e ) 就是这类方法，这种索引结构能够在数 据查询方面比传统的空间索引技术性能要好一些。 2 4 最近邻居搜索问题 2 4 1 最近邻居( 洲) 最近邻居查询( n e a r e s tn e i g h b o rq u e r y ，简称n nq i l e r y ) 是一个非常著名 地问题，在很多领域内都有着广泛的需求。n n 问题描述如下：在n 维空间中给 定包含m 个对象的集合s ，我们可以有效的查询到所要给定对象的最近邻居。 现在我们给出一般的最近邻居搜索问题( n n ) 的定义：在n 维空间中，给定对 象集s ，和一个查询对象q ，则n n 搜索问题就是寻找s 的一个子集n n s ( q ) ，使得： n n s ( q ) = f p s lv r s ，d ( q ，p ) d ( q ，r ) ) 2 4 2 最近邻居( 洲) 应用领域 1 资源配置：从城市中各种公用设施、救灾减灾中物质的分配、全国范围 内能源保障、粮食供应等，到机构的在各地的配置都是资源配置问题， n n 在这类应用中的目标就是保证资源的最合理配置和发挥最大效益。 2 城市规划和管理：空间规划时地理信