（计算机应用技术专业论文）移动对象的动态反向最近邻的研究.pdf

哈尔滨理工人学t 学硕j 二学位论文 移动对象的动态反向最近邻的研究 摘要 空间数据库是近年新的研究领域，是一门前沿的交叉学科，它在地理信 息系统、计算机辅助设计c a d 、多媒体信息系统m m i s 以及数据仓库 d w h 技术等诸多应用领域中都有着广泛的应用。 反向最近邻查询是空间数据库中最重要的算法之一，是在最近邻查询的 基础上提出的一种新的查询类型。传统的反向最近邻查询方法主要是静态对 象的查询，随着无线通讯和定位技术的快速发展，移动对象发出的查询请求 成为新的研究热点，传统的反向最近邻查询算法不能满足移动对象的查询请 求。 本课题在研究目前多种反向最近邻查询技术的基础上，提出了一种解决 移动对象动态反向最近邻的查询方法。将t p r t r e e 作为算法的索引结构， 并提出了基于矩形框的对角线的修剪策略，将现有半平面修剪策略进行了改 进，给出了移动对象的动态反向最近邻的查询方案，对算法的可终止性、正 确性和时间复杂性进行了分析，并用实例进行了验证。同时将移动对象的动 态反向最近邻查询技术扩展到移动对象的动态反向k 最近邻的查询，并给出 了移动对象的动态反向k 最近邻的查询方案及相关证明。本课题提出的查询 技术能够高效地处理查询点和查询点集为动态的情况，对移动对象的动态反 向最近邻的查询技术的发展有重要意义。 关键词空间数据库；最近邻查询；反向最近邻查询；t p r t r e e ；移动对象 r e s e a r c ho fd y n a m i cr e v e r s en e a r e s tn e i g h b o r f o r m o v i n go b j e c t s a b s t r a c t r e c e n ty e a r ss p a t i a ld a t a b a s eb e c o m ean e wr e s e a r c hf i e l d ，a n d i ti sa m u l t i d i s c i p l i n a r yr e s e a r c h s p a t i a ld a t a b a s ei sp o p u l a ri ng 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 ，c o m p u t e ra i d e dd e s i g ns y s t e m ，m u l t i m e d i ai n f o r m a t i o ns y s t e m ，d a t a w a r eh o u s ea n do t h e ra r e a s o n eo ft h em o s ti m p o r t a n ta l g o r i t h m si ns p a t i a ld a t a b a s ei sr e v e r s en e a r e s t n e i g h b o rq u e r yw h i c h i san e wq u e r ym e t h o dp r o p o s e db a s e do nn e a r e s tn e i g h b o r q u e r y c o n v e n t i o n a lq u e r y m e t h o df o c u so ns e a r c h i n gs t a t i co b je c t sm a i n l y w i t h t h er a p i da d v a n c e m e n ti nw i r e l e s sc o m m u n i c a t i o n sa n dp o s i t i o n i n gt e c h n i q u e s ， a l g o r i t h m sf o re f f i c i e n t l ya n s w e r i n gq u e r i e sa b o u tl a r g ep o p u l a t i o n so fm o v i n g o b ie c t sa r eg a i n i n gi n t e r e s t c o n v e n t i o n a l 。q u e r ym e t h o do fr e v e r s en e a r e s t n e i g h b o ri sn o ta n s w e r i n gm o v i n go b j e c t sq u e r i e s o nt h eb a s i so fa n a l y z i n gs o m er e v e r s en e a r e s tn e i g h b o rq u e r ym e t h o d s ，t h i s p a p e rp r o p o s e dad y n a m i cr e v e r s en e a r e s tn e i g h b o rq u e r ya l g o r i t h mf o rm o v i n g o b j e c t s t p r t r e ei su s e dt oi n d e x i n gc o n t i n u o u s l ym o v i n go b j e c t s at r i m m i n g s t r a t e g yw h i c hi m p r o v e dh a l f - s p a c et r i m m i n gs t r a t e g yi sp r o p o s e da c c o r d i n gt o t h ed i a g o n a lo fr e c t a n g l e 。f u r t h e r m o r e ，t h ed y n a m i cr e v e r s en e a r e s tn e i g h b o r q u c r yf o rm o v i n go b j e c t si sp r e s e n t e d t h ec o r r e c t l y , e f f e c t i v e l ya n dc o m p l e x i t y o fm ed y n a m i cr e v e r s en e a r e s tn e i g h b o rq u e r ya l g o r i t h mi sp r o v e d a tt h es a m e t i m et h et e c h n o l o g yo fd y n a m i cr e v e r s en e a r e s tn e i g h b o rq u e r yf o rm o v i n g o b je c t si se x t e n d e dt od y n a m i cr e v e r s ekn e a r e s tn e i g h b o rq u e r y t h ea l g o r i t h m f o rd y n a m i cr e v e r s ekn e a r e s tn e i g h b o rq u e r yf o rm o v i n go b j e c t s l sa l s o p r e s e n t e d a n dt h ec o r r e c t l y , e f f e c t i v e l ya n dc o m p l e x i t yo f t h ed y n a m i cr e v e r s ek n e a r e s tn e i g h b o ra l g o r i t h mi sa l s op r o v e d t h em e t h o do f t h i sp a p e rp r o p o s e dc a n a n s w e rt h es e a r c ho fd y n a m i co b je c t se f f e c t i v e l y t h i sr e s e a r c hi si m p o r t a n tt o d e v e l o p m e n to fs p a t i a ld a t a b a s eq u e r yt e c h n o l o g y i i 哈尔滨理工人学工学硕士学位论文 k e y w o r d ss p a t i a ld a t a b a s e s ，n e a r e s tn e i g h b o rq u e r i e s ，r e v e r s en e a r e s tn e i g h b o r q u e r i e s ，t p r - t r e e ，m o v i n go b j e c t s i i i 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文移动对象的动态反向最 近邻的研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人己发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：朽奄啦 日期：印q 秀年弓月，。日 哈尔滨理工大学硕士学位论文使用授权书 移动对象的动态反向最近邻的研究系本人在哈尔滨理工大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨 理工大学所有，本论文的研究内容不得以其他单位的名义发表。本人完全了 解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大 学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密囤。 ( 请在以上相应方框内打4 ) 作者签名：物鸯z 和 日期：加富年弓月冈日 导师签名： j - - 擀4 hj t 目：睹年岁月d 日 1 1 研究背景和意义 第1 章绪论 空间数据库是近年的热点研究领域，是一门非常前沿的交叉学科，它在 地理信息系统g i s ( g e o g r a p h i ci n f o r m a n t i o ns y s t e m ) 、计算机辅助设计 c a d ( c o m p u t e ra i d e dd e s i g n ) 、多媒体信息系统m m i s ( m u l t i m e d i a i n f o r m a t i o ns y s t e m ) 以及数据仓库d w h ( d a t aw a r eh o u s e ) 技术等诸多应用领 域中都起着非常重要的作用。与传统文件方式相比，空间数据库技术有明显 的技术优势，包括海量数据管理能力、图形和属性数据一体化存储、多用户 并发访问、完善的访问权限控制和数据安全机制等。空问数据库技术正在取 代传统文件，成为越来越多的大中型空间数据库应用系统的空间数据存储和 查询的解决方案。 反向最近邻查询是空间数据库中最重要的算法之一，是在最近邻查询的 基础上提出的一种新的查询类型n 1 。反向最近邻查询问题是与人们平常所遇 到的影响集概念相一致的。例如一家百货公司想在某一地点设一个新的分公 司，这必然会对附近的同类公司或商店( 假设人们一般选择就近购物) 带来 商业上的影响，而受其影响最大的同类公司或商店，就是其反向最近邻查询 所要的结果。另外，在相似形查询问题中，也同样存在反向最近邻问题。例 如，某公司为一新产品做广告，以电子邮件的形式发到用户的信箱里，而要 发给那些对本产品相当感兴趣的人，这就不会使用户的信箱总是被一些垃圾 邮件充满，也能使产品的广告更加有效，而要发给哪些用户? 实际上，这就 是反向最近邻查询问题。反向最近邻查询在许多数据库应用中都起着非常重 要的作用，成为空间查询研究中的重点和难点。 作为空间数据库中最重要的算法之一的反向最近邻查询问题，近些年 来，相应的研究机构投入了大量的人力和物力来从事该领域的研究。传统的 反向最近邻查询方法是查询点和查询点集为静态的情况，随着无线通讯技术 的快速发展，移动设备使用越来越广泛，移动对象发出的查询请求成为新的 研究热点。传统的反向最近邻查询算法不能满足移动对象的查询请求，这就 使移动对象的动态反向最近邻的研究成为新的研究热点。 哈尔滨理工人学工学硕十学位论文 1 2 国内外研究现状 在反向最近邻查询问题的研究中，国外已提出了几种处理模型和相应的 算法，并作了大量的模拟分析和评测工作，结合理论与实践，积累了较多的 经验，但是对于移动对象的动态反向最近邻的研究还是空白；而在国内，对 反向最近邻查询问题的研究还刚刚起步，目前只有少量的相关论文发表 f 2 ，3 ，4 】 o 求反向最近邻的最直接的方法是先查找每个点的最近邻，然后利用最近 邻嘲或者范围查询阳1 判断集合中的哪些点将查询点作为最近邻。然而，此种 方法是不可行的。因为此方法的时间复杂度是o ( n 2 ) ，当集合中的点的数量 很大时，复杂度会迅速增加( ，z 为集合中元素的个数) 。 反向最近邻查询问题最早是由f k o m 和s m u t h u k r i s h n a n 在2 0 0 0 提出 的盯1 ，并在后续的几年里受到了很大的关注。现存的研究按不同的分类方 法，基本上可以分为：单色和双色反向最近邻查询问题；低维( 一般为二、 三维) 和高维( 三维以上) 反向最近邻查询问题；静态和动态反向最近邻查 询问题；预处理方法和空间修剪方法的反向最近邻查询问题等等。 现存的方法基本上都是单色r n n 的情况，所谓单色也就是所有的点都 是属于同一种类。双色反向最近邻查询问题与单色的情况不同的是，有两种 不同种类的数据点集。双色反向最近邻查询伸1 目前研究的还很少。 在单色r n n 的基础上，提出了各种有效的处理方法。这些方法可以分 成两类：预处理方法( p r e c o m p u t a t i o n ) 和空间修剪方法( s p a c ep r u n i n g ) 。 预处理方法阳，1 0 1 在索引结构中提前处理和存储每个数据点的最近邻，并 通过n n 查询或者范围查询来判断是否是反向最近邻。这种方法仅仅对更新 数据较少或静态时效率高，在处理频繁更新数据时，查询性能就会急剧下 降。为了提高更新速度，k i n g 1 pl i n 等人提出了一种能够在r d n n 树n 中 高效地插入大量数据点的技术n2 。而且这种预处理方法是不能处理r k n n 的，除非相应的k 最近邻信息是有效的。空间修剪方法3 1 利用了反向最近邻 的几何属性，在原节点集的基础上查找更小范围的点集作为候选点集，并通 过最近邻查询或者范围查询来证实他们是否是查询点的反向最近邻。现存的 方法都是以r t r e e 为基础的。空间修剪的方法之所以灵活是因为这种方法 不需要预处理最近邻信息。然而，当数据维数高或者k 值大的时候，这种算 法的代价也是很昂贵的。 哈尔滨理t 大学t 学硕上学位论文 以往讨论的反向最近邻查询问题大都是静态的，也就是说查询点q 和数 据点集s 是静态的、不动的，并且是可以定义和存储数据点集的。然而， 在许多应用中，查询点和数据点集却都是动态的，先前讨论的静态的方法就 不能满足这样的查询。目前此类的最近邻查询也有许多，并在此基础上提出 了针对移动对象的、数据点集是动态的情况的反向最近邻查询。目前的这类 方法有：1 y u f e it a o 提出了一种数据点集是动态情况的反向最近邻查询n 方法；2 k o r n 提出了基于数据流的反向最近邻问题n 5 1 的研究，并提出了反 向最近邻聚集的概念，通过它可以形式化地探索和研究基于数据流的反向最 近邻问题；3 s t a n o i 用到了空间修剪方法，将二维空间分成六个区域，这种 方法不需要特殊的索引结构，避免了数据点更新时频繁的计算和修改索引结 构，效率大大地提高了；4 b e n e t i s 将t p r t r e e 作为底层的索引结构n 引。 t p r t r e e 引入了时间参数，可以查询在某时间片段内的移动对象的最近邻和 反向最近邻。此方法可以针对移动对象来进行查询，这是前面的方法所不能 实现的，t p r 树在移动对象的查询中有广泛的应用。 在现存的研究中，大部分方法都是只能应用到一、二、三维的空间中， 如果维数增加就会使算法的效率急剧降低。高维的情况n 7 1 8 1 研究得也不是很 多，如y u f e it a o 给出了高维反向k n n 的查询算法n 9 20 。，此方法以r 树索引 结构为基础，不需要预处理计算，并采用t p l 方法，此方法使用了过滤提 纯技术，分两步处理：1 过滤：检索所有的候选结点，并保证包含所有的 反向最近邻；2 提纯：排除所有不是反向最近邻的结点。第二步中采用了 无缝的方法，不存在重复访问同一个结点的情况。这种方法效率比前面的提 高了，但是只能针对静态查询点的情况。 目前，除了以上的反向最近邻查询问题外，还提出了大图中的反向最近 邻查询问题心、连续的反向最近邻查询问题和在特定维上进行反向最近邻心副 的研究，而非所有维上。m a nl u n g 等人提出的大图中的反向最近邻查询问 题中给出两个算法：e a g e r 算法和l a z y 算法，这两个算法可以在查询过程中 对图进行裁剪，大大缩小了查询范围。y u f e it a o 等人提出的连续反向最近 邻查询问题中给出了c r n n 查询算法，该算法能够有效地处理查询对象不 为点，而为一条线段的反向最近邻查询问题。在特定维上进行的反向最近邻 查询具有重要的研究价值，具体原因在于：1 由于数据维数过大，导致常 规的反向最近邻查询没有实际意义；2 数据使用者可能对数据的某些维感 兴趣；3 高维数据在某些维上的丢失导致只能在特定维上进行查询。 哈尔滨理工大学t 学硕上学位论文 1 3 课题来源及主要研究内容 1 3 1 课题来源 本研究课题来源于黑龙江省自然科学基金项目，项目编号为f 2 0 0 6 0 1 。 1 3 2 主要研究内容 本文在对现有的反向最近邻查询技术进行分析比较的基础上，较好地把 握了各种方法的优点和不足，进而融会贯通，加以改进，提出了一种基于移 动对象的动态反向最近邻的算法。本课题的研究内容主要有以下几方面： 1 移动对象的动态反向最近邻查询现有的反向最近邻查询技术只能 处理静态查询点静态数据点集、静态查询点动态数据点集或者移动查询点静 态数据点集的查询。针对这一情况，本文提出了一种新的反向最近邻查询方 法：移动对象的动态反向最近邻查询。将t p r t r e e 作为算法的索引结构， 并提出了基于矩形框对角线的修剪策略，将半平面修剪策略进行改进，给出 了移动对象的动态反向最近邻的查询方案。该方案将查询划分为过滤阶段与 提纯阶段，在过滤阶段，查询算法求得反向最近邻的候选节点的集合，其中 包含所有的最终结果；在提纯阶段，修剪掉候选节点集合中的非反向最近 邻，并返回最终结果。实验证明，这个方案能够很好地处理移动对象的动态 反向最近邻查询。 2 移动对象的动态反向k 最近邻查询目前的反向最近邻查询技术大 多都只支持k = l 的情况。针对这种情况，本文在移动对象的动态反向最近 邻查询技术的基础上进行扩展，将基于矩形框对角线的修剪策略应用到k l 的情况，给出了扩展后的半平面修剪策略。移动对象的动态反向k 最近邻算 法与k = l 的情况相同，同样分为两个步骤进行处理：过滤阶段和提纯阶 段。实验证明，算法能够处理k l 时的移动对象动态反向k 最近邻查询。 哈尔滨理t 大学工学硕士学位论文 第2 章空间数据库关键技术 2 1 空间数据和空间数据库 空间数据库乜3 1 是一个用于存储空间( 地理) 和非空间数据的数据库系 统，在它的数据模型和查询语言中能提供空间数据类型，可以进行空间索 引，并且提供空间查询和其他空间分析的方法。空间数据库是一种特殊的数 据库，与一般数据库最大的不同是它包含“空间 ( 或几何) 概念。任何事 物都有其空间形式和基本特征。作为反映现实世界的数据库，空间属性应当 是数据的基本属性。虽然在某些应用中，空间属性往往是隐含的，没有显现 出来，但一般而言，数据也能表示事物的当前状态。因此，从根本上讲，一 个数据应当既有非空间内容，又有空间内容。例如，一个国家至少有一个非 空间数据( 国家名) 和一个空问数据( 国家的边界) 。 2 1 1 空间对象 现实世界中的对象存在于空间当中，在特定的空间信息系统应用环境中 如地理信息系统、全球定位系统的应用中，我们必须要考虑对象在空间中的 位置。这些将空间物体进行抽象得到的对象称为空问对象( s p a t i a l o b j e c t s ) 。空间对象由两方面数据共同构成：与空间无关的描述性数据，通 常称为主题属性或属性数据；对象在空间中的位置，称为空间属性或空间数 据。 2 1 2 空间数据特征 空间数据是适用于表示空间物体的位置、形状、大小和分布特征等方面 信息的数据，适用于二维、三维和多维分布的关于区域的现象。空间数据库 处理的主要是和空间位置、空间关系有关的数据。一般来说，数据具有选择 性、可靠性、时间性、完备性、详细性和综合性。空间数据除了具有一般数 据的特征外，还具有一些区别于其他数据的特征心制： 1 空间特征每个空间对象都有空间坐标，即空间对象隐含了空间分 布特征。这意味着在空间数据组织方面，要考虑它的空间分布特征，所以除 哈尔滨理t 大学t 学硕 ：学位论文 了通用性数据库管理系统或文件系统关键字的索引以外，一般都需要建立空 间索引。 2 非结构化特征在当前通用的关系数据库管理系统中，数据记录一 般是结构化的。即它满足关系数据模型的第一范式要求：每一条记录是定长 的：数据项表达的只能是原子数据；不允许嵌套记录。而空间数据则不能满 足这种结构化要求。若将每一条记录表达一个空间对象，它的数据项可能是 变长的。 3 空间关系特征空间数据除了前面所述的空间坐标隐含空间关系 外，空间数据中记录的拓扑信息表达了多种空间关系。这种拓扑数据结构虽 然一方面方便了空间数据的查询和空间分析，但在另一方面也给空间数据的 一致性和完整性维护增加了复杂性。特别是有些几何对象，没有直接记录空 间坐标的信息，如拓扑的面状目标，仅记录组成它的弧段的标示，因而进行 查找、显示和分析操作时都要操纵和检索多个数据文件方能得以实现。 4 分类编码特征一般而言，每个空间对象都有一个分类编码，而这 种分类编码往往属于国家标准，或行业标准，或地区标准，每一种地物的类 型在某个地理信息系统中的属性项个数是相同的。因而在许多情况下，一种 地物类型对应于一个属性数据表文件。当然，如果几种地物类型的属性项相 同，也可以多种地物类型共用一个属性数据文件。 5 海量数据特征空间数据量是巨大的，通常称海量数据。之所以称 为海量数据，是指它的数据量比一般通用数据库要大得多。一个城市的地理 信息系统的数量可能达到几十个g ，如果考虑影响数据的存储，可能达到几 百个g 。这样的数据量在其他数据库中是很少见的。正因为空间数据量大， 所以必须要建立合理的空间索引以达到提高空间数据库的效率。 空间数据是数字地球的基础信息，数字地球功能的绝大部分将以空间数 据为基础。随着科学和社会的发展，人们已经越来越认识到空间数据对于社 会经济的发展和人们生活水平提高的重要性，这加快了人们获取和应用空间 数据的步伐。 2 1 3 空间数据模型 空间数据模型与其它数据模型相比，一个突出的特点就是其模型的提 出、引入与相应的实际应用密切相关。其关键问题是选择一组基本空间数据 类型来满足对地图常用建模的需要。最为通用的形状是由“空间表示体系 哈尔滨理工大学t 学硕上学位论文 中所描述的“几何体 来表示的，“空间表示体系”是一个坐标系统，“几何 体”分为4 类： 1 点描述一个零维对象的形状，例如城市。点只表示其空间位置， 不表示其范围。 2 线描述一维对象的形状，例如河流，街道，通信或者电力线路 等。线不仅表示线上各点在空问的位置，而且还有一长度，即表示其在空间 的延伸范围。 3 面描述二维对象的形状，例如行政区域。面不但有位置，而且有 面积，周长等参数，以表示其覆盖范围。 4 几何体集合表示复杂的形状，例如一群岛屿。几何体集合有三种 类型，即多点、多线、多面。 2 1 4 空间数据库 空间数据库首先是一个数据库管理系统( d b m s ) ；其次，在空间数据 库的数据模型和查询语言中支持空间数据类型和空间操作；第三，在空间数 据库的实现中支持空间数据类型，提供空间索引，支持空间选择和空间联 接。 空间数据库是提供空间对象管理的复杂系统。在空间数据库中，空间对 象的主题属性一般用传统数据类型来表示，而空间数据的管理则需要增加新 的空间数据类型和空间操作。 空间数据库的核心问题是空问数据的表示和操作。空间可以是二维或多 维的。在地理信息系统的应用当中，二维和三维空间数据是最为常见的空间 数据。因此目前对空间数据库的研究也基本上集中于二维和三维空间数据的 管理上。二维空间数据通常包括点、线和面。三维空间数据还包括体。目前 对空间对象主要有两种不同的表示方法：栅格模型和矢量模型。 栅格模型实际中通常以一个栅格来表示一个像素点，因此图像通常以栅 格数据的形式存在。栅格模型的优点是可直接利用遥感、数字摄影测量等图 像数据，数据结构比较简单，其方向、邻接及连通计算易实现，但栅格模型 对设备的存储空间要求过高( 一般以栅格图像方式存储) ，而且不存储空间 坐标，这使得空间实体的识别和标识比较困难，查询速度也相对较慢。栅格 模型对于按实体组织数据的数据库来说并不合适。 矢量模型以基本几何对象( 点、线、面，体等) 来表示空间数据。基本 哈尔滨理t 大学工学硕十学位论文 几何对象以采样点的空间坐标表示。例如一个二维空间可以通过一个由区域 的边界点构成的多边形来表示，而三维空间可以通过一个由空间边界面构成 的多面体来表示。矢量模型存储了空间数据的边界坐标，可以方便地表达空 间数据之间的空间拓扑关系。而且在矢量模型中容易对单个目标进行定义和 操作。其缺点是不能直接处理图像数据，而且数据结构相对复杂。矢量模型 是目前流行的空间数据表示方法，在g i s 等应用中得到广泛的应用。 空间数据的操作包括空间拓扑操作、空间几何操作和空间属性操作。空 间拓扑操作即空间谓词，它判断两个空间数据之间的空间拓扑关系并返回 t r u e 或f a l s e 。典型的空间拓扑关系包括相邻、相离、相交、部分覆 盖、完全覆盖和包含等。空间几何操作是对空间数据执行的几何运算，如求 空间数据的交、空间数据的并等。空间几何操作一般将空间数据视作点集， 并以集合操作的方式来实现。空间属性操作计算空间数据本身的特性值，如 求面积、周长等。 2 2 空间索引 空间索引乜5 1 是指存储空间数据时依照空间对象的位置和形状或空间对象 之间的某种空间关系，按一定顺序排列的一种数据结构，其中包含空间对象 的概要信息，如对象的标识、外包矩形框及指向空间对象的指针等。空间索 引是对存储在介质上的数据位置信息的描述，作为一种辅助性的空间数据结 构。空间索引介于空间操作算法和空间对象之问，通过筛选，大量与特定空 间操作无关的空间对象被排除，从而提高空间操作的效率。 海量空间数据管理使得索引机制显得尤为重要，为了提高对空间数据的 处理效率，必须引入合适的索引技术。至今为止，人们提出的空间索引结构 种类繁多。我们可以按其支持的空间对象类型来进行分类。比如，对点对象 进行支持的空间索引结构有网格文件，对空间区域对象( 包括线对象和面对 象) 进行支持的空间索引结构有四叉树等。但从设计上讲，人们探索新的索 引结构主要有两个思路。 1 分区的方法将空间划分成很多个小的分区。 2 基于空间对象的最小边界矩形二维以上的空间对象称之为包络 体，空间对象的边界矩形能够粗略反映出空间对象的空间特性，从而加速空 间对象的定位过程。 空间索引中都很好地使用了近似的思想。首先在近似的基础上，执行一 哈尔滨理1 = 大学工学硕十学位论文 个过滤步骤，它返回一个候选集，作为满足某个谓词的所有对象的超集；其 次，在精炼步骤中，对于每个候选对象，用精确的几何信息进行检查。 2 2 1 空间索引分类 目前，已经研究出许多高效的空间索引方法，大致可以分为如下五类： 1 基于二叉树的索引技术基于二叉树索引结构的典型范例包括k d 树心引、m k d 树心引、s k d 树心8 等。这种索引结构的典型k d 树是一种二分索 引结构，主要用于索引多维数据点，但对复杂的空间目标的索引必须采用近 似方法和空间映射技术。因此针对空间关系的查询效率非常低、索引树非常 庞大、需要存储在外存的缺点，同时为了能够索引复杂的空间目标，提出了 适合索引二维空间目标的基于实体标志重复存储技术的m k d 树。s k d 树 的提出避免了空间目标的重复存储和空间映射，用空间目标的中心点来对空 间目标集进行二分索引。但是所有这些方法对非点状空间目标的索引效率都 较低。 2 基于b 树的索引技术b 树及其变体，被广泛应用于常规的数据库 管理系统之中，实践证明其对大型数据库的索引具有出色表现。目前的空间 数据索引技术，很多都基于b 树，如r 树瞳9 1 。从r 树的结构上可以看出， 让空间上靠近的空间对象拥有尽可能近的共同祖先，能提高r 树的查询效 率。但是怎样衡量空间对象的聚集，是一个非常复杂的问题。由于衡量的方 法不同，也产生了众多的r 树的变体 3 0 , 3 1 ，如疋树婚引、r + 树、t p r 树 1 3 3 , 34 3 引、t p r + 树鸭引、h i l b e r tr 树 和r 1 i n k 树m 1 等等。 3 基于哈希的网格技术这种基于哈希方法的基本思路是将索引空间 划分为相等或者不相等的一些小方网格，与每个网格相关联的空间目标存储 在同一磁盘页上，而网格的访问地址则可以直接通过求数组下标或应用某种 算法得到，常见的方法有网格文件等，这类方法主要适用于索引多维空间中 的点。 4 空间填充曲线法这一类索引结构的特点就是希望找到某种方法对 多维空间中的数据进行近似的排序，使得原来在空间中比较接近的数据能在 排序后以比较高的概率靠在一起，那么就可以用一维数据对它们进行索引。 这种索引方法的实质是将多维空间的实体映射到一维空间中，然后采用一维 的数值对多维的空间目标进行排序，常见的方法有四叉树、z 序刚等。 5 v a f i l ev a f i l e 是一种非常有效的索引方式，其基本思想是将高维 哈尔滨理t 大学工学硕十学位论文 数据进行压缩和近似存储。首先，对每一维j 分配一定的比特数b ，对于给 定的总的比特数b 以及维数d ，则当j b r o o d d 时，b ，= 【b d 】+ 1 ，当j 为其 它值时，b ，= b d 】。每一维上的比特数决定了在这一维上的刻度数，一般 来说，第j 维需要2 吩+ 1 个刻度来得到2 q 个区间，其中第一个刻度对应着该 维上的最小值，最后一个刻度对应着该维上的最大值，其余的刻度值则对该 维进行等分，在插入和删除过程中这些刻度值一般保持不变，只有在区间之 间的点数超过了一定的限制后才进行重新计算。 2 2 2r 树索引 r 树是大多数商用数据库采用的空间索引模型，也是研究得比较成熟的 一种算法。r 树最早是由g u t t m a n 在1 9 8 4 年提出的，g u t t m a n 参照b + 树 的定义形式，给出了r 树的定义。因此它不仅具有b + 树特有的动态平衡 性，而且能进行多维索引。r 树中用对象的最小边界矩形m b r ( m i n i m u m b o u n d i n gr e c t a n g l e ) 来表示对象。r 树有如下几条特性： 1 每个叶结点包含m 至m 条索引记录，其中m m 2 ，除非它是根结 点： 2 一个叶结点上的每条索引记录了( i ，元组标识符) ，其中i 是最小边 界矩形，在空间上包含了所指元组表达的k 维数据对象； 3 每个非叶结点都有m 至m 个子结点，除非它是根结点； 4 对于非叶结点中的每个条目( i ，子结点指针) ，其中i 是在空间上包 含其子结点中矩形的最小边界矩形； 5 根结点至少有两个子结点，除非它是叶结点； 6 所有叶结点出现在同一层； 7 所有m b r 的边与一个全局坐标系的轴平行。 以上是r 树区别于其它索引结构的特性，下面通过一个例子来分析。 图2 1 是在二维空间中的一组空间对象( m b r ) 。 图2 2 是对应图2 1 中一组m b r 的r 树，树中叶结点上的对象在图2 - l 中用阴影标出。 考虑搜索图2 2 中与矩形5 交叠的对象。根结点中的项x 与矩形5 交 叠，搜索沿着r 树的这一分支继续。在x 中，项b 和c 与矩形5 交叠，因 而继续搜索。最后矩形4 、5 和6 确定为与查询矩形5 交叠的叶结点项。 由于r 树是一棵平衡树，在与插入对象对应的叶结点已满的情况下， 哈尔滨理工人学工学硕十学位论文 图2 1 空间对象集合 f i g 2 - 1s e to fs p a t i a lo b j e c t s r 图2 - 2r 树 f i g 2 - 2r t r e e 插入操作可能会导致结点向根部分裂。虽然页面分裂算法非常复杂，但是r 树已经在许多商用数据库系统中实现了。r 树的优点是它按数据来组织索引 结构，具有很强的灵活性和可调节性，即无需预知整个空间对象所在的空间 范围，就能建立空间索引。由于它具有与b 树相似的结构和特性，使其能 很好的与传统的关系型数据库相融合。 2 3 空间查询 空间查询与检索是空间数据库的最基本的操作，也是g i s 空间分析的 哈尔滨理工大学t 学硕 ：学位论文 主要功能之一，是指从空间数据库中查找出满足某一条件的空间目标的过 程。空间查询回答用户的查询问题，不改变空间数据库中的数据，不产生新 的空间实体和数据，常用的空间查询操作主要分为两大类：空间选取与空间 厶士厶 ；日i = 1o 2 3 1 空间选取 空间数据查询的结果通常是满足查询性质的空间对象的集合。应用在 空间数据库上的空间选取查询操作主要有八种，复杂空间查询大多在这八种 查询的基础上进行的。 1 精确匹配查询找出所有和空间查询对象具有完全相同空间内容的 空间对象。 2 点查询找出所有和查询点重叠的空间对象。 3 包含查询找到所有包含查询对象的空间数据对象。 4 相交查询、区域查询或者重叠查询找出所有和查询对象有至少一 个公共点的空间数据对象。 5 窗口查询或者范围查询找出和d 维查询窗口有至少一个公共点的 空间数据对象。 6 被包含查询找出所有被查询对象包含的空间数据对象。 7 相邻查询找出所有和查询对象相邻的空间数据对象。如果两个对 象有共同的边界并且没有相互包含，那么称这两个对象相邻。 8 最近邻查询h 旷4 副找出所有和查询对象具有最小距离的空间数据对 象，通常以两者最近点的距离作为空间对象间的距离。 2 3 2 空间结合 空间结合的定义为：给定两个空间对象集r 和s ，以及空间谓词副，找 出所有空问对象对( o ，o ) r s ，使该对象对满足关系p 。对于空间谓词口可 以有多种形式，如相交( i n t e r s e c t ) 、包含( c o n t a i n ) 、被包含( i se n c l o s e db y ) 等 等。其中最常用的是相交，因此相交运算符也是最重要的空间谓词。对于诸 如包含、被包含、相邻等谓词，相交结合是一个有效的过滤器，通过该结合 可产生比笛卡尔集r s 要小的多的查询候选集合。 m b r 空间结合是经常使用的结合方法，其中心思想是如果两个空间对 象的m b r 不相交，那么他们所包含的空间对象也不相交。使用该性质，通 哈尔滨理工大学工学硕上学位论文 过检查空间对象m b r 的相交情况，即可过滤要进行空间结合查询操作的空 间对象对。 空间结合的查询过程可概括为三个步骤：首先，计算两个空间对象集 的m b r 结合，并用简单的几何过滤去判别明确不相交的空间对象对( 不命 中) 和相交的空间对象对( 命中) ，从而减少需要进一步处理的空间候选集， 这一过程可以通过高效的空间存取方法来实现。随后，在需要进一步处理的 空间对象对中为了识别不符合要求的对象，采用精确的凸起多边形近似法计 算候选集的每个对象，同时进行新一轮的相交检查。例如：通过对每个候选 空间对象对最小内接矩形m e r ( m a x i m u me n c l o s e dr e c t a n g l e ) 的相交检查， 过滤出符合查询条件的空间对象集。对象的m e r 指的是空间对象的空间范 围所能包含的最大d 维矩形。如果两个对象的m e r 相交，则对象肯定相 交。在以上两个步骤完成后，剩下的候选集就需要使用更复杂的几何处理 ( 如空间对象分解) 去找出符合查询条件的空间对象集。在整个查询过程中， 空间对象经历了3 次几何精化操作。 2 4 最近邻问题 最近邻查询( n e a r e s tn e i g h b o rq u e r y ，简称n nq u e r y ) 是一个非常著名的 问题，在很多领域内都有着广泛的需求。n n 问题描述如下：在维空间中 给定包含m 个对象的集合s ，我们可以有效的查询到给定对象的最近邻居。 现在我们给出一般的最近邻居搜索问题的定义h7 。：在d 维空间中，给定 对象集s ，和一个查询对象g ，则n n 搜索问题就是寻找s 的一个子集 刀( g ) ，使得：n n s ( q ) = p siv r s ，d ( q ，p ) d ( q ，- ) 。 2 4 1 最近邻( n n ) 应用领域 1 资源配置从城市中各种公用设施、救灾减灾中物质的分配、全国 范围内能源保障、粮食供应等，到机构在各地的配置都是资源配置问题， n n 在这类应用中的目标就是保证资源的最合理配置和发挥最大效益。 2 城市规划和管理空间规划是地理信息系统的一个重要应用领域， 城市规划和管理是其中的主要内容。例如，在大规模城市基础建设中如何保 证学校、医院、公共设施、运动场所、服务设施等能够有最大的服务面。 3 应急响应解决在发生洪水、火灾、战争等重大自然或人为灾害 时，如何安排最佳的人员撤离路线，并配备相应的运输和保障设施的问题。 哈尔滨理工大学t 学硕十学位论文 4 商业与市场商业设施的建立充分考虑其市场潜力。例如：大型商 场的建立如果不考虑其他商场的分布，待建区周围居民区的分布和人数，建 成之后就可能无法达到预期的市场和服务面。有时甚至商场销售的品种和市 场定位都必须与待建区的人口结构( 年龄构成、性别比例、文化水平) 、消费 水平等结合起来考虑 5 选址分析根据区域地理环境的特点，综合考虑资源配置、市场潜 力、交通条件、地形特征、环境影响等因素，在区域范围内选择最佳位置， 是n n 的一个典型应用领域。 2 4 2k n n 搜索 k n n 搜索h 引( k n e a r e s tn e i g h b o rq u e r y ) 是n n 搜索的一个扩展。心烈问 题在很多方面尤其是数据挖掘上有很重要的意义，其本质就是给定某一对象 q 以及正整数k ，从数据库中找出距离q 最近的k 个对象。 k 最近邻居搜索问题的定义h 引：在d 维空间内给定一个对象集合s ，对 于一个查询对象g ，以及一个正整数k ，则k n n 搜索问题就是寻找s 的一个 子集k n n s ( q ) ，使得：k n n s ( q ) = 厂si 坳s ，d ( p ，q ) d ( q ，p k ) ) ，其中既是 口的第k 个最近邻。 2 5 本章小结 本章首先明确了空间数据库的概念和研究内容，然后详细阐述了空间数 据库的空间对象、空间数据特征、空间数据模型和空间数据库，对空间索引 和空间查询的分类和技术做了相应的介绍，并对最近邻查询问题做了简单介 绍，为下面的研究工作奠定了概念基础。 哈尔滨理工大学t 学硕十学位论文 3 1 引言 第3 章移动对象的动态反向最近邻 在众多空间查询问题中，本文主要研究的是反向最近邻查询。现有的反 向最近邻查询方法大部分都是针对查询点或数据点集为静态的情况。本文提 出了一种新的反向最近邻查询，即针对移动对象的动态反向最近邻查询，也 就是查询点和数据点集都是动态的情况。 本文提出的基于移动对象的动念反向最近邻的研究方法，是以t p r t r e e 为索引结构，提出了一种利用矩形框的对角线判断是否保留剩余m b r 的策 略，对现有的半平面修剪策略进行了改进，并采用过滤提纯的处理方法来获 取移动查询点的反向最近邻，实现了移动对象的动态反向最近邻的查询。 3 2 基本定义 本节将给出反向最近邻查询概念，并对半平面修剪策略和t p r t r e e 进 行详细的介绍。 3 2 1 反向最近邻查询 定义3 1 ：反向最近邻查询( r e v e r s en e a r e s tn e i g h b o rq u e r y ，r n n q ) 哺们 给定数据集s 和一个查询点q ，找出s 中所有把g 作为最近邻的对象的集 合，如公式( 3 1 ) 所示： r n n s ( q ) = r sv p s ，d ( r ，g ) d ( r ，p ) ) ( 3 1 ) 其中s 是d 维空间中的数据点集，d ，g ) 是p 、q 两点之间的距离。反 向最近邻查询是在数据点集s 中查找将查询点g 作为最近邻的点的集合。虽 然反向最近邻查询问题是在最近邻问题的基础上提出来的，但是二者的关系 是不对称的，即假设p 是查询点g 的最近邻，但是并不意味着p 的最近邻是 g