（计算机软件与理论专业论文）道路网络中连续k近邻查询的研究.pdf

哈尔滨理t 大学t 学硕十学位论文 道路网络中连续k 近邻查询的研究 摘要 随着无线网络通讯和全球定位技术的发展，出现了很多相关的新应用，如 基于位置的服务。空间数据库( s d b ) 中支持基于位置服务的一种重要的查询就 是连续k 近邻查询。给定相关的空间数据点集和一个移动查询点g ，道路网络 中的连续k 近令g ( c k n n ) 查询计算距离一个给定查询点q 最近的k 个数据点。 大多数关于空间数据库的研究只考虑欧氏空间。因此，大多数基于位置的 查询，如k 近邻查询，利用物体之间的欧氏距离。然而，在某些应用中，物体 的位置和运动被限制于网络中，例如道路、航空、铁路等。在这些情况下，距 离的度量是网络距离。为了存储这些网络中的空间数据，空间网络数据库 ( s n d b ) 出现了。每种传统的空间查询类型( 如最近邻查询、范围查询、连接查 询等) 在空间网络数据库中都有相似的应用。 对移动应用来说，支持道路网络中移动对象连续查询的能力是至关重要 的。论文研究的连续k 近邻查询处理三种类型的对象：道路、移动对象和静态 对象。其中移动对象( 如车辆或人) 在道路网络上运动，静态对象( 如加油站或旅 馆) 位于道路网络上；移动对象为查询点，静态对象为数据点。 论文主要做了以下研究工作：首先，改进了道路网络模型并将道路网络模 型转换为与其对应的图。其次，在该图的基础上结合d i j k s t r a 单源最短路径算 法实现了初始k 近邻查询计算，并在移动对象运动过程中持续更新数据库与查 询结果，将新的查询结果发送到客户端，实现了连续k 近邻查询。最后，用实 验证明了算法的正确性与有效性。 关键词空间数据库；道路网络；连续k 近邻；r 一树 哈尔滨理1 二大学t 学硕七学位论文 r e s e a r c ho nc o n t i n u o u sk - n e a r e s tn e i g h b o u rq u e r i e s i nr o a dn e t w o r k a b s t r a c t w i t ht h e d e v e l o p m e n t o fw i r e l e s sn e t w o r kc o m m u n i c a t i o n sa n dg l o b a l p o s i t i o n i n gt e c h n o l o g i e s ，t h e r er a i s e sm a n yk i n d so fr e l a t e dn e wa p p l i c a t i o n s ，e g 1 0 c a t i o n b a s e ds e r v i c e s o n eo ft h em o s ti m p o r t a n tk i n d so fq u e r i e si ns p a t i a l d a t a b a s e st os u p p o r tl o c a t i o n b a s e ds e r v i c e si st h ec o n t i n u o u skn e i g h b o u r ( c k n n ) q u e r y g i v e nas p a t i a ld a t as e to fp o i n t so fi n t e r e s ta n d am o v i n gq u e r yp o i n tq ，a c k n nq u e r yi nr o a dn e t w o r kc o m p u t e st h ekd a t ap o i n t st h a tl i ec l o s e s tt oag i v e n q u e r yp o i n tq m o s to ft h er e s e a r c hi ns p a t i a ld a t a b a s e s ( s d b ) c o n s i d e r so n l yt h ee u c l i d e a n s p a c e c o n s e q u e n t l y , d i s t a n c e - b a s e dq u e r i e s ，l i k et h ekn e a r e s tn e i g h b o u rq u e r y , u s e t h ee u c l i d e a nd i s t a n c eb e t w e e no b j e c t h o w e v e r , i ns o m ea p p l i c a t i o n s ，t h eo b j e c t s p o s i t i o na n dm o v e m e n ta r ec o n s t r a i n e dt on e t w o r k ，f o re x a m p l er o a d s ，h i g h w a y s ， r a i l w a y se t c i nt h e s ea p p l i c a t i o n s ，t h ei m p o r t a n td i s t a n c em e a s u r ei s t h en e t w o r k d i s t a n c e f o rt h e s en e t w o r kc o n s t r a i n e ds p a t i a ld a t a ，s p a t i a ln e t w o r kd a t a b a s e s ( s n d b ) a r ep r o v i d e d e v e r yc o n v e n t i o n a ls p a t i a lq u e r yt y p e ( e g n e a r e s tn e i g h b o u r q u e r y , r a n g eq u e r y ，j o i nq u e r y ) h a sac o u n t e r p a r ti ns n d b t h ea b i l i t yt os u p p o r tc o n t i n u o u sq u e r i e sf r o mm o v i n go b j e c t so nr o a dn e t w o r ki s e s s e n t i a lf o rac l a s so fm o b i l ea p p l i c a t i o n s t h ep a p e rc o n s i d e r sac k n nq u e r yw h i c h h a n d l e st h r e et y p e so fo b j e c t s ：r o a d s ，m o v i n go b j e c t s ，a n ds t a t i co b j e c t s i nw h i c h m o v i n go b j e c t s ( e g c a r so rp e o p l e ) r u no nr o a dn e t w o r k ，s t a t i co b j e c t s ( e g g a s s t a t i o n so rr e s t a u r a n t s ) a r el o c a t e do nr o a dn e t w o r k m o v i n go b j e c t sa r eq u e r yp o i n t s ， s t a t i co b j e c t sa r ed a t ap o i n t s t h ep a p e rh a sm a i n l yf i n i s h e dt h ef o l l o w i n gr e s e a r c hw o r k ：f i r s t ，h a v i n g i r e p r o v e dt h er o a dn e t w o r km o d e la n dt r a n s f o r m e di ti n t ot h er e l a t e dc h a r t s e c o n d l y , h a v i n gf i n i s h e dt h ec o n t i n u o u skn e a r e s tn e i g h b o u rq u e r i e sb a s e d o nt h ec h a r ta n d d i j k s t r as i m p l es o u r c es h o r t e s tp a t ha l g o r i t h m ，a n dr e n e w e d t h ed a t a b a s ea n dt h e i i 哈尔滨理t 大学丁学硕1 ：学位论文 q u e r yr e s u l tw i t ht h em o v e m e n to ft h em o v i n go b j e c t s t h en e wq u e r yr e s u l tw i l lb e s e n d e dt ot h ec l i e n ts i d e st or e a l i z et h ec o n t i n u o u skn e a r e s tn e i g h b o rq u e r y f i n a l l y , h a v i n gp r o v e dt h ea c c u r a c ya n dv a l i d i t yo ft h ea l g o r i t h m sw i t he x p e r i m e n t s k e y w o r d ss p a t i a ld a t a b a s e s ，r o a dn e t w o r k ，c o n t i n u o u sk n e a r e s tn e i g h b o u r ， r t r e e - i i i - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文道路网络中连续k 近邻查询 的研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期i 丑j 独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己 发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文 中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：李崛相 同期： 砌口g 年弓月 ，。同 哈尔滨理工大学硕士学位论文使用授权书 道路网络中连续k 近邻查询的研究系本人在哈尔滨理工大学攻读硕士 学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工 大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔 滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交 论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用 影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密厂 ，在年解密后适用授权书。 不保密r 。 ( 请在以上相应方框内打) 作者签名： 莲晓f 诵 r 期：刎8 年今月，。r 导师签名： 囱玄j 武 同期：易年7 月i r 哈尔滨理丁大学工学硕j 二学位论文 第1 章绪论 1 1 课题来源及研究的目的和意义 1 1 1 课题来源 本课题来源于黑龙江省自然科学基金资助项目( f 2 0 0 6 0 1 ) 一高维时空数据库 中移动对象的查询技术研究。 1 1 2 研究的目的和意义 最近邻( n e a r e s tn e i g h b o r s ，n n ) 查询是计算机科学中一个传统的问题。最近 邻查询问题是由k n u t h 在1 9 7 3 年提出来的，即邮局问题。可以简单描述为： 给定维空间内的n 个点所组成的集合s ，将这n 个点存储在一种数据结构 中，使得对于空间内的任何查询点g ，都可以有效地找到它的最近邻，即在s 中找到一个点p ，使其到口的距离最近。最近邻的数目可以是一个，也可以是 多个即k 近邻。例如，某一用户可能在屏幕上点击一个特定的位置或者一个目 标，要求系统查找并返回数据库中5 个距离它最近的对象。由于空间数据量庞 大，数据结构复杂，操作代价昂贵，因此空间查询的优化是人们所关心的问 题，其中最近邻查询也成为空间查询研究中的难点和热点。这种查询类型通常 应用于内容的相似性检索、模式识别、地理信息系统( g e o g r a p h i ci n f o r m a t i o n s y s t e m ，g i s ) 等。 地理信息系统是能够收集、管理、查询、分析、操作以及表现与地理相关 的数据信息的计算机信息系统，能够为分析、决策提供重要的支持平台乜1 。它 广泛地应用于地学、资源管理、土地规划、环境监视、防灾减灾、电力行业、 交通管理、城市规划、科研、教育和国防等领域，在国民经济建设中发挥着越 来越重要的作用。 空间数据库( s p a t i a ld a t a b a s e s ，s d b ) 是g i s 的重要组成部分，空间数据的 查询是空间数据库的基本操作。随着移动通信、数据库技术以及定位技术， 如：全球定位系统( g l o b a lp o s i t i o ns y s t e m ，g p s ) 的发展，定位服务( l o c a t i o n b a s e ds e r v i c e s ，l b s ) 的重要性正在增加，多种创新型的移动计算应用正在出 哈尔滨理工大学工学硕士学位论文 现，有能力支持一个网络移动用户端的n n 查询是必要的。但空间数据库中的 大部分研究仅考虑了欧氏空间。与之相应，以距离为基础的查询如查 询，采用对象之间的欧氏距离一1 来度量。然而在空间网络中，对象的位置和 运动被约束在网络上，如道路、高速公路、铁路等。在这些应用中，距离度量 采用网络距离。为了有效的处理这些空间数据，空间网络数据库( s p a t i a l n e t w o r kd a t a b a s e s ，s n d b ) 应运而生。每种传统的空间查询类型( 如最近邻、范 围搜索和空间连接) 在s n d b 中都有对应项1 。 欧氏空间的k 近邻查询通常假定距离函数很容易计算。这一假定对网络距 离显然是不成立的。简单地将对欧氏距离调用变更为对网络距离的调用很明显 不是有效的方式。因此有必要对s n d b 中的c k n n 查询问题进行深入的研究。 1 2 空间查询及其分类 空间查询又称空间查找、空间检索。空间查询( s p a t i a lq u e r y ) 是指从空间数 据库中查找出满足某一条件的空间目标的过程( 查找条件与空间位置有关) 。如 查找与某一区域相交的所有空间目标或被区域完全包含的空间目标，找出与空 间目标尸具有某一空间关系( 如相交、穿越、邻接等) 的所有空间实体等等。在 很多应用领域，如g i s 中，空间查询操作无处不在，空间查询的性能是这些应 用系统成功的关键所在。 作为与数据库交互的主要手段，查询语言是数据库管理系统的一个核心要 素。作为关系数据库管理系统的一种常见的商业查询语言，s q l 在一定程度上 基于形式化查询语言关系代数( r a ) 。虽然r a 和s q l 都是功能强大的查 询处理语言，但它们在高效处理空间数据方面还是存在一定的局限性。关系模 型比较适合处理简单的数据类型，如整型、日期型、字符串型等。而在空间数 据库中，必须处理象点、线、多边形这样的复杂的数据类型，因此，需要扩展 s q l 以支持对空间数据库的操作。 由于空间数据没有标准的空间代数，也没有标准的空间查询语言，加上空 间算子非常依赖于应用程序范围，目前的空间操作，大多数采用扩展的s q l 语言。扩展的s q l 采用更贴近人们对空间理解的概念，为空间数据提供更高 层次的抽象。扩展的s q l 允许使用抽象数据类型( a d t ) 表达空间对象以及对象 的联合运算。查询的结果通常是满足查询要求的空间数据对象集合。按照查找 条件的不同，几种常见的查询包括： 1 点查询( p o i n tq u e r y ) 给定一空间点，查找所有包含该点的空间目表 哈尔滨理工人学工学硕j j 学位论文 标。 2 区域查询( r e g i o nq u e r y ) 给定一查询区域， 少一个公共点的空间目标。区域查询又可细分为： 相交查询( i n t e r s e c t i o nq u e r y ) ：给定一查询区域， 的空间目标。 找出所有与查询区域有至 查询所有与之相交的( 重叠) 包含查询( e n c l o s eq u e r y ) ：给定一查询区域，查询所有包含它的空间目标。 被包含查询( c o n t a i n m e n tq u e r y ) ：给定一查询区域，查询所有被该区域包含 的空间目标。 相邻查询( a d j a c e n c yq u e r y ) ：给定一查询区域，查询所有与之相邻的空间目 标。所谓相邻，是指两个空间目标有共同的边界并且没有相互包含。 3 范围查询( d i s t a n c eq u e r y ) 查询与给定对象间距离小于某个给定值的 所有对象。 4 最近邻查询( n e a r e s tn e i g h b o u rq u e r y ) 查询离给定对象最近的对象。 通常以两者最近点间的距离作为空间对象间的距离。最常用的点距离函数是欧 式距离。 1 3k 近邻查询的研究现状 k 近邻查询是指在押维空间罩，给定一个点集合s ，查询点口和一个正数 k ，k 个近邻搜索问题就是发现一个集合s 的子集k n n s ( q ) = p l ，p 2 ，p k ，使得 对于任意p 熨忘7 、w 义g ) 和r e k n n s ( q ) 都有d ( q ，力d ( g ，p ) 。d ，g ) 表示任何两 个点p 和g 之间的距离。在基于路网的条件下，d ，g ) 是连接移动对象和要查询 的点之间的所有边的权值之和，而移动对象所处的空间是二维路网空间。由于 近邻问题有着重要的理论研究价值和实际应用，一直是相关领域专家们的研究 重点。目前，已经有很多有效的算法被提出。下面，我们将详细介绍目前的研 究成果。、 传统空间数据库k 近邻查询已经得到了广泛研究并提出了多种算法m 。1 引。 其中大多数算法针对欧式空间对象，物体之间的距离采用欧几里德几何距离来 计算，不能适应空间网络数据库的发展需求。因此，近年来空间网络数据库的 k 近邻查询问题逐渐成为研究的焦点。 空间网络的k 近邻可以分为两种类型：增量扫描网络直到第k 个最近邻被 检索的k 近邻计算方法；应用一些形式的“预计算”和通过查询“预计算 数 据结构中的数据计算k 近邻的方法。两种类型的方法都假定空间网络以类图数 哈尔滨理t 大学t 学硕士学位论文 据结构表示。第一种方法如“在线计算”获得网络的动态性质如刚出现或消失 的兴趣点，并且进行网络扩展搜索。与“在线计算”相比，第二种方法称为 “预计算”，一般具有较好的查询性能，但是在网络和兴趣点的更新上比较困 难。 s h a h a b i 等人提出了一种嵌入技术，把网络转换到一个高维空间，从而利 用简单的距离度量进行计算n9 。这一方法的主要缺点是只能提供真实距离的近 似结果。 j e n s e n 等人提出了空间网络数据库的n n 查询所需要的数据模型和抽象的 功能性定义心。1 。他们使用与d i j k s t r a 算法相似的方式来在线计算从查询点到对 象之间的最短距离。s h e k h a r 等人提出了四种技术来检索在给定路径上运动对 象的一个最近邻幢。 在2 0 0 3 年的v l d b ( v e r yl a r g ed a t ab a s e s ) 会议上，p a p a d i a s 等人提出了两 种方法，即增量欧几里德约束( i n c r e m e n t a le u c l i d e a nr e s t r i c t i o n ，i e r ) 并n 增量网 络扩展( i n c r e m e n t a ln e t w o r ke x p a n s i o n ，r n e ) 心引，其中，i n e 显著的优于i e r 。 i n e 方式以与d i j k s t r a 算法类似的方式扩展网络边。i n e 算法的主要缺点是节 点的扩展方式，当一个节点扩展的时候，它无法只返回在每个毗邻边上的下个 最近点，而是在点的r 树上执行搜索返回每个毗邻边上所有的点，而且如果边 未包含兴趣点，在点的r 树上的查询仍被执行。并且这一算法对稀疏的网络是 不适用的，即使在密集网络情况下，许多工作仍被浪费。 k o l a h d o u z a n 和s h a h a b i 针对当对象分布在稀疏的网络中时i n e 方法执行 效率低的缺点，提出了基于v o r o n o i 图的v n 3 方法心3 。，它试图把一个大的网络 分割为较小的v o r o n o i 区域，预计算区域内部和穿过这一区域的距离。实验显 示v n 3 方法优于i n e 。然而对于k 值增加的情况，由于许多路径在v o r o n o i 区 域之间穿过，它的计算代价很高。对于稀疏的数据集，网络v o r o n o i 分割 ( n e t w o r kv o r o n o ip a r t i t i o n s ，n v p s ) 的数目很少，相应的它的多边形却很复杂， 导致边界点数目很多，这使得精炼步骤的计算更为复杂。另一方面，如果数据 集是稠密的，n v p s 的数目很大，则候选集也很大，这意味着精炼步骤需要从 多个可能中来判定。 h u a n g 等人提出了一种称之为“岛屿 ( i s l a n d s ) 的方法心4 1 ，它预计算并存 储与兴趣点不超过一定距离( 即岛屿的半径) 的节点。这种方式结合了预计算方 式高效率和网络扩展方法的优点。 在2 0 0 5 年的v l d b 会议上，c h o 和c h u n g 提出了一种同i s l a n d s 非常相似 的方法心5 | ，但是它不是预计算兴趣点的最近节点，而是预计算网络中一些节点 哈尔滨理t 大学t 学硕士学位论文 ( 即聚集点) 的最近兴趣点。而且这种方法为每个聚集点计算固定数目而不是一 定半径内的最近邻。 除了v n 3 ，所有这些方法的缺点是它们无法增量地检索最近邻。增量最近 邻算法以迭代的形式实现下一个最近邻的检索。这种增量的检索方式是比较好 的，如用户( 使用用户界面) 能在k 个最近邻检索完成之前停止；用户可以在处 理完k 个最近邻后继续检索第( 斛1 ) 个最近邻；由于它是非块( n o n b l o c k i n g ) 的，所以这种方式能够以流水线方式执行。，所有这些方法的缺点是它们无法 增量地检索最近邻。增量最近邻算法以迭代的形式实现下一个最近邻的检索。 这种增量的检索方式是比较好的，如用户( 使用用户界面) 能在k 个最近邻检索 完成之前停止；用户可以在处理完k 个最近邻后继续检索第( 斛1 ) 个最近邻；由 于它是非块( n o n b l o c k i n g ) 的，所以这种方式能够以流水线方式执行。 k o l a h d o u z a n 等人为空间网络数据库的k - n n 查询提出了一种称为上限算 法( u p p e rb o u n da l g o r i t h m ，u b a ) 的方法心6 1 。u b a 限制只在必要的位置进行n n 查询计算，因此减少了n n 计算的数目，具有较好的效率。u b a 利用v n 3 在一 个静态位置返回( 胁1 ) 个n n 。然后计算查询点不需要提交新的最近邻查询的最 小移动距离。然而u b a 仍然需要大量的最近邻查询来找出分割点( 分割点是一 个对象的k 近邻发生变化的路径位置) 。结果当最近邻的数目和对象的密度增 加时运行时间也急剧增加。 f e n g 等人提出了网络中c n n 查询方法幢7 2 引。这种方法以检索路径上必须 执行最近邻查询的位置为基础。这种方式的主要缺点是它只解决了连续的第一 个最近邻( 也就是c 1 n n ) 查询而未解决c k n n 查询问题。 1 4 网络数据库k 近邻查询面临的挑战 空间网络数据库中的k 近邻查询面临着许多挑战，主要表现在以下几个方 面心9 。 1 复杂性两个节点间的距离度量通常是很复杂的例如在网络中，两个 对象间的距离被指定为节点间具有最小权值的最短路径的长度。网络中的权值 既可以是路径的长度也可以是穿过这条路径所需的行程时间，而计算这些距离 的算法是很复杂的( 如网络中计算最短路径的d i j k s t r a 算法的时间复杂度为o ( e + n l o g n ) ，e 和刀分别是网络中边和节点的数目) 。当k 近邻查询考虑约束时距 离函数的度量变的更为复杂。例如，要求查询点g 东南方向的k 近邻或前进方 向的k 近邻时，距离函数的度量更为复杂。 哈尔滨理工人学工学硕上学位论文 2 有效性 当查询点口是一个移动对象时，g 与感兴趣对象的距离函数 就需要经常或实时计算，这就要求候选结果的有效性。 3 健壮性弹性空间网络数据库通常是很大的，一个区域可能会包含数 万个交叉点和道路，所以k - n n 查询的解决方法依赖于主存是不实际的。而且 网络中不同类型兴趣点的密度是不同的，有可能在网络中分布差异很大。因 此，解决方法要独立于兴趣点的密度以及它们在网络中的分布情况，并能处理 较大k 值的情况。 4 适应性 空间网络数据库可能会经常更新。新的节点、连接和兴趣点 都可能会增加或删除，如高速公路一个路段临时的关闭，某个位置一家新餐馆 的开张等。因此，k 近邻查询有能力适应并且有效的处理数据库的更新是很重 要的。 1 5 本文的主要研究工作 本文在广泛调研和对大量中外文献分析的基础上，研究了当前的空间索引 技术、近邻查询方法和数据存储技术，基于已有的k 近邻查询方法，主要进行 了以下工作。 分析了道路网络建模所必要的条件，并结合实际对道路网络模型进行改 进。 分析当前道路网络中k 近邻查询存在的问题，对其中存在的问题进行改 进，使其能适应当今道路网络中查询的需要。 1 6 本文的组织结构 本文共分5 章，各章节的内容编排如下： 第1 章首先介绍了本文的研究背景及目的意义，然后给出了空间查询的分 类及k 近邻查询的研究现状，最后分析了网络数据库中k 近邻查询所面临的挑 战。 第2 章主要介绍了空间数据库的特点及当前的各种空间索引和查询技术， 并介绍了两种典型的空间数据索引结构。 第3 章是对构建道路网络模型及道路网络模型与图的转化的研究。首先对 道路网络及其中的对象进行建模，并设计它们在数据库中的存储结构。然后提 出将构建的道路网络模型转化为图的算法，为道路网络中连续k 近邻查询的研 哈尔滨理工大学t 学硕十学位论文 究奠定基础。 第4 章在第3 章的研究基础上提出了适应本文的k 近邻查询算法，并在移 动查询对象更新时实时更新数据库及查询结果，将新的查询结果发送到客户 端，实现了道路网络中的连续k 近邻查询。 第5 章通过实验验证了算法的正确性和有效性，并对实验结果进行了相关 分析。 最后，总结了本文的研究工作并对以后的研究提出设想。 哈尔滨理t 人学t 学硕i ：学位论文 第2 章空间数据索引与查询概述 对于一个数据库系统而言，一项根本任务就是信息的检索查询，空间数据 库也不例外，查询和检索是空间数据库中使用最频繁的功能之一曲0 。能否快速 的检索信息是移动对象数据库性能高低的一个主要的标志，而检索性能主要取 决于数据库系统的索引机制。本章介绍了空间数据的特点及其索引技术，并对 当前的空间数据查询技术进行了介绍。 2 1 空间数据及其特点 目前，很多计算机应用系统都以一维、二维和三维空间中的对象为基础。 我们简称描述一维、二维和三维空间对象的数据为空间数据。最早的空间数据 应用是计算机辅助设计和几何应用。目前，空间数据应用的范围已经扩展到了 机器人、计算机视觉、图像识别、地理信息处理等领域。 空间数据是一个基于空间参考的数据，它以定点、定线或定面的方式与地 球表面建立位置关系。图像数据如遥感数据；图形数据如普通地图、专题地图 等；地理统计数据以及环境检测数据等，均是空间数据的重要代表。 空间数据不仅能代表实体本省的空间位置及形态，而且还包含实体属性和 空间关系的信息。为了更好的处理空间数据，设计能进行快速空间操作的空间 管理系统，需要了解空间数据包含的主要信息范畴及其特性。 空间数据包括三个主要信息范畴： 1 空间信息主要包括：位信息，能确定在什么地方有什么事务或发生 什么事情；空间量度信息，能计算诸如物体的长度、面积、物体之间的距离和 相对方位等；空问关系信息，能知道空间物体之间的分别关系、拓扑关系( 如 邻接、关联、包含等) 。 2 非空间数据非空间数据( 又叫属性数据) 主要包括专题属性数据和质 量描述数据。专题属性数据是对空间物体进行语义定义，表明该物体是什么； 质量描述数据则包含一些补充性的质量、数量、等级等描述信息。 3 时间因素地理要素的空间与规律是地理信息系统的中心研究内容， 但是空间和时间是客观事务存在的形式，两者之间是互相联系而不能分割的。 因此，往往要分析地理要素的时序变化，阐明地理现象的过程和规律。时间因 素为地理信息增加了动态性质，地理信息的这种动态变化特征，一方面要求及 哈尔滨理工大学工学硕十学位论文 时获取信息并定期更新，另一方面要重视自然历史过程的积累和对未来的预测 和预报，以免使用过时的信息导致决策的失误，或者缺乏可靠的动态数据而不 能对变化中的地理事件或现象作出合乎逻辑的预测预报和科学论证。 空间数据的特性概括如下： 1 空间对象复杂性一个空间对象可以由点或几千个多边形组成，并任 意分布在空间。通常不太可能用一个关系表，以定长元组存储这类对象的集 合。这样空自j 操作( 例如，相交、合并) 就比标准的关系数据库操作要复杂的 多。 2 空间数据动态性删除和插入是以更新操作交叉存储的。这就要求一 个强壮的数据结构以经受住对对象频繁的插入、删除和更新操作。 3 空间数据海量化地理图中的对象经常需要上千兆的存储量。要想进 行高效的空间操作，二级和三级存储的集成是必不可少的。 4 空间算法不标准尽管在过去2 0 多年里提出了许多空间数据算法， 但没有定义一个标准的算法。这就意味着没有一个标准化的基础算子集合。这 使得算子严重依赖于特定空间数据库的应用程序。 5 空间运算不封闭性例如：两个空间实体的相交，可能返回一个点 集、线集或面集。 6 计算代价昂贵虽然空间数据的计算代价会随所采用的空间算子不同 而变化，但他们通常要比标准的关系运算代价昂贵。 由于上述空间数据的特性，加上没有将空间对象从多维到一维的直接映 射，在过去2 0 多年里，研究人员发展了多维数据存取技术，以方便和高效地 建立空间数据的索引。 2 2 空间索引 2 2 1 空间索引的需求 所谓空间索引就是指在存储空间数据时依据空间对象的位置和形状或空间 对象之间的某种空间关系，按一定顺序排列的- - ；f e e 数据结构，其中包含空间对 象的概要信息如对象的标识、外接矩形及指向空问对象实体的指针。作为一种 辅助性的空| 、日j 数据结构，空间索引介于空间操作算法和空间对象之间，通过它 的筛选，大量与特定空间操作无关的空间对象被排除，从而提高空间操作的效 率。 哈尔滨理丁大学t 学硕十学位论文 空间数据通常是基于属性的值和数据对象的空间位置来进行获取和更新。 对空间数据的查询与获取经常需要执行快速的几何搜索运算，例如：点查询、 区域查询等。所有这些运算需要快速存取空间数据对象。要支持这些索引操作 就需要特殊的空间存取方法，即必须引进索引机制。空间索引的目的是为了在 空间数据库中快速定位到所选中的空间要素，从而提高空问操作的速度和效 率。空间索引的技术和方法是空间数据库的关键技术之一，是快速、高效地查 询、检索和显示空间数据的重要指标，它的优劣直接影响空间数据库的整体性 能。高效的空间索引必须满足以下要求： 1 动态性目前由于空间数据趋于海量化，空间数据的存储通常都以关 系数据库为基础，要满足在数据库中可以以任意顺序删除或添加数据对象，空 间索引应不断跟上其变化速度。 2 二级和三级存储管理空间索引机制需要有效的整合二级、三级存 储。 3 支持多空间算子空间索引不应只关注一种空间操作的效率( 如搜 索) ，而忽视了其他操作的效率。 4 输入数据和插入顺序的独立空间索引的效率不应依赖于输入数据的 类型和插入的顺序。 5 简单性复杂的空间索引方法往往会导致实现的错误，对大规模的应 用就不能保证充分的强壮。 6 可伸缩性空间索引方法应能很好地适应数据库的发展。 7 时空和空间的有效性空间索引方法的操作应当快速，同时一个索引 所占的空间应尽量小。 8 最小的影响空间索引方法与数据库系统的融合应对现存系统产生最 小的影响。 2 2 2 空间索引技术 传统的空间数据库索引技术有b 树、b + 树、二叉树、i s a m 索引、哈希 索引等，这些技术都是针对一维属性数据的主关键字索引而设计的，并不能直 接应用于空间数据库的索引。因此，设计高效的针对空间目标位置信息的索引 结构与检索方法，就成为提高空间数据库性能的关键所在。 由于实际应用的需要，最近几十年，对空间索引的研究引起了所内外学者 的足够重视，许多空间索引结构与方法相继提出。从空间数据库的观点看，空 哈尔滨理t 大学t 学硕+ 学位论文 间索引结构可以分为处理点对象的点存取方法( p a m ) 并i 处理空间扩展对象( 包括 点、线、面、体) 的空间存取方法( s a m ) b 引。p a m 包括g r i d 文件船、b u d d y 树 引、k d b 树5 、h b 树m 1 、l s d 树等。s a m 采用空间对象的近似进行索 引，如常用的最小边界矩形( m b r ) 。依据空间对象的不同组织方式，s a m 分 为对象映射、对象分割复制和对象界定三类阳”删。对象映射是把非点对象映射 为高维低维空间中的点，然后利用点一维存取方法索引映射后的数据集，如 常见的空间填充曲线方法将高维空间中的空间对象线性映射到一维空间中，用 空间排列码( 如m o r t o n 码、h i l b e r t 码、g r a y 码等) 作为地址码建立索引h 1 4 2 1 。 对象分割复制是把与子空间相交的数据对象分割成几个子对象，分别存储在 互不重叠的子空间中，在子空间中复制对象本身或其标识符，如i h 树h 、c e l l 树h 钆删、线性四叉树h 6 4 7 1 等。对象界定又称区域重叠技术，它允许子空间的相互 重叠，一个数据对象唯一对应于一个子空间，如r 树h 引、r 木树叫等。 从空间目标映射方法分，空间索引技术可大致分为两大类： 第一类，基于空间目标排序的索引方法。 其基本思想是：按照某种策略将索引空间细分为许多格子，并给每一网格 分配编号，然后用这些编号为空间目标获得一具有代表意义的数字。这样，多 维的空间目标转换为简单的数字，因此一维索引技术可以利用，常规的数据库 系统可以用于管理空间目标的属性与几何信息。用一维值给多维空间目标排序 的技术很多如p e a n o 曲线嗡”、位置键肺、z 排序2 1 等。 第二类，专门的空问索引方法。 在系统中加入专门的外部空间数据结构，来提供对空间数据的索引。常用 的方法有： 1 不允许空间重叠的索引法这种方法将k 维的空间数据空间按某种方 法( 如二叉树划分、四叉树划分、格网划分等) 划分成彼此不相交的子空间，然 后对属于这些子空间的目标分别存储在对应的磁盘页或数据桶中。 目标复制：目标标识重复存储在与该目标相交的所有子空间。 目标裁减：目标被分解成几个不相交的小目标，从而使每一小目标完全包 含在一子空间。k d 树、r + 树等是这类方法的典型代表。 2 允许空间重叠的索引法这种方法的基本思想是：按某种策略将索引 空间层次划分成多级的子空间，这些子空间允许重叠从而使点与非点状目标都 完全包含在某一子空间之内。这种方法的一个重要的优化策略是尽量最小化各 级子空间的重叠与覆盖，因为子空间重叠与覆盖直接关系到查找路径的多少， 关系到空间检索的效率。r 树及其变体是这种方法的主要代表。图2 1 给出了 哈尔滨理工人学工学硕上学位论文 常见的索引结构嵋引。 牙_ e ：j j 二# 丰啐司三二# 靠c - r et 妯, n g m _ a 旁l 啦 | - o e c 妙( 备赫 ? ： ： ： ： ：降r _ 壮d 卜一1 _ 一：8 一：二平。= 唧叫a ，j1。r 1 “f 1 r “t r t | 。t 一 11 r 广 ， 碾? t m t m v b 电略 狮琢呻冀上 i 州一“ l讥 卿e d 聃m ： ， 2 3 t & - 缸e r 一- | jd r - h , e 知3 景t 嬲 t s - m * ，7 了l ，o 人k t -mi 毫妇一1 t - i 、ik iu 、 ， ，、。 ：i s b - 捌” 5强咖! 、， 疑骞吨* i：嘲 l，、m - r 簟 il 才7 r 豫 i i 豫鸣e ，名一珊电 、 卜太- 器，m l i 硝硝p 鲫q i 渤e 班 ；( i-i 憎 ii i 降： p 辍 ：q 砸h g r 0 茁寿嫠! 函赫l 。i 、鼍勺 l： 瓠h o d i睦 8 0 - 8 99 09 19 29 39 4笏9 69 7 鲐够o oo i0 2 0 3 图2 i 常见的索引结构 f i g 2 1s u r v e yo fi n d e xs t r u c t u r e 2 2 3 典型的空间索引介绍 2 2 3 1r 树索 r 树是b 树在多维空间的扩展，它由g u t t m a n 于1 9 8 4 年提 出。对于一棵m 阶的r 树，其节点结构可描述如下： 叶子节点：( c o u n t , l e v e l ， ， ) 。 中i 司节点：( c o u n t , l e v e l ， ， ) 。 其中， 称为数据项，o i i 为空间目标的标识，m b r i 为该目标 在k 维空间中的最小包围矩形( 简称为数据矩形) ； 称为索引项， c p i 为指向子树根节点的指针，m b r i 代表其子树索引空间，为包围其子树根节 点中所有目录矩形或数据矩形的最小包围矩形( 简称为目录矩形) 。c o u n t m 哈尔滨理工人学工学硕1 ：学位论文 指示节点中用到的索引项或数据项个数( 即该节点的“孩子”个数) ，l e v e l ；一 d 指示该节点在树中的层数( d 表示叶节点) 。由于整数和指针所占存储空间相 同，且可以相互转换，因此r 树的叶子节点和中间节点在结构上是相同的。 设聊( 2 聊m 2 ) 为节点包含索引项( 数据项) 的最小数目( 朋通常取m 2 ， 如果节点包含项目数小于m ，则称节点下溢，如果节点包含项目数大于m ，则 称节点上溢溢出) 。r 树必须满足如下特性： 1 若根节点不是叶子，则至少有两棵子树。 2 根之外的所有中间节点至多有m 个子树，至少有m 棵子树。 3 每个叶子节点均包含m 到m 个数据项。 4 所有的叶子节点都出现在同一层次。 5 所有节点都需要同样的存储空间( 通常为一个磁盘页) 。 此外，r 树还具有如下特性： 1 数据矩形可能重叠。 2 目录矩形允许重叠( 即中间节点的索引空间允许重叠) 。 3 即使对于精确匹配查找，查找路径也往往是多条的。 r 树是完全动态的，插入、删除、查询可以交叉进行，不需定期的全局结 构重组。 图2 2 给出了r 树的示意图。a ) 中实线框( ，l ，您，r 8 ) 表示空间目标的 “m b r ”，即数据矩形，p l ，p 2 ，p 1 0 表示空间点的( 点的m b r 就是点本身) ； 虚线框( r 1 ，r 2 ，r 8 ) 表示中间节点( 包括根节点) 索引项对应的索引空间，即目 录矩形。从图中可以看出目录矩形可以重叠。 r 一树具有b 树的优点，如自动平衡、空间利用率较高、适合于外存存储 等。r 树的主要问题是，由于中间节点目录矩形允许且可能重叠，因此往往存 在多条查找路径，而其中的某些查找路径往往不包含查找结果，这就影响了查 找性能。研究显示，随着索引空间维数的增加，r 树中间节点目录矩形的重叠 迅速增加，这无疑会严重影响查找性能。另外，可以预见，随着索引数据量的 增加，树的高度及r 树中间节点目录矩形的重叠均会增加，查找性能会随之下 降，且查找性能的下降速度会高于索引数据量的增加速度。因此，对于r 树而 言，减少中间节点目录矩形的覆盖与重叠是关键所在。 r 树索引通过最小边界矩形( m b r ) 来匹配每个几何体。对于一个几何体图 层，r 树索引包含该层上所有几何体的分层m b r 索引。在o r a c l es p a t i a l 中， r - 树索引存储在空间索引表s d oi n d e xt a b l e 中，而该表又在视图 u s e rs d oi n d e xm e t a d a t a 中。r 树索引通过一个顺序数字发生器来确 哈尔滨理工大学t 学硕十学位论文 保当前用户对索引的实时更新。在创建空间索引的时候，如果不指明任何索引 参数创建的是r 树索引。 霜烫 a ) 平面示意图 p 。l b b ) 结构示意图 图2 - 2 一颗二维空间r - 树的例子 f i g 2 2e x