（计算机应用技术专业论文）时空数据库中最近邻查询技术的研究.pdf

重庆邮l 乜人学硕十论文 摘要 摘要 i q 窄数据庠是舀+ 字m 数掘辟的摹础上：发展叫1 j 束的新兴数掘库技术，用卜处 删随时间拊移向变化的宅问信息。最近邻( n e a r e s tn e i g h b o r , n n ) 查询是在空问 数据库和时空数据库中绎常会使用的一种查询技术，它返回在数掘痒中所存储 的距离查询对象最近的对象。对f 最近邻查询的实施，首先要考虑的是相关查 询算法的设计和实现。随着无线通信和定位技术的发展，可有效处理大量移动 对象的查询算法越来越引起人们的注意。目i j ，t p r 树( t i m e p a r a m e t e r i z e d r t r e e ，t p r t r e e ) 是针对移动对象现在和将来位置的查询最有效的时空索引结 构，因此基于t p r 树的动态最近邻的查询算法具有相当的研究价值。 本文首先介绍和分析了前人在最近邻查询算法上的研究成果，接着对t p r 树中移动对象动态距离的计算作了相关的讨论。在此基础上，提出了一种基于 t p r 树可扩展的查找多个最近邻对象( k - n e a r e s tn e i g h b o r s ，k n n ) 的查询算法。 陔算法包含两个部分：对t p r 树中结点的优化剪枝遍历和对叶结点中移动对象 的处理。随后，针对在得到查询结果以后移动对象可能会发生更新的情况，描 述了维持查询结果有效性的解决方案。基于所提出的最近邻查询算法，本文提 出了一种简便易行的连续最近令1 ( c o n t i n u o u sn e a r e s tn e i g h b o r , c n n ) 查询的实 现方法。该方法基于当查询| 日j 隔到来时反复执行最近邻查询的思想，通过最近 邻链表来确定动念查询问隔。最后，通过仿真实验对所提出的查询算法的性能 进行了测试，并从移动对象数目、查询时间段长度以及最近邻对象数目几方面 对其进行了分析。从实验结果可以看出，所提出的最近邻查询算法具有较好的 查询性能，在查询的执行时间上也有一定的优势。 关键词：时空数据库，最近邻查询，t p r 树，多个最近邻对象，连续最近邻查 询 亚庆邮l 乜人中硕+ 论文摘要 a b s t r a c t s p a t t o t e m p o r a ld a t a b a s ei s ar i s i n gd a t a b a s et e c h n o l o g yd e v e l o p e df r o mt h e s p a t i a ld a t a b a s e ，w h i c hd e a l sw i t ht h es p a t i a ld a t ac h a n g i n go v e rt i m e t h en e a r e s t n e i g h b o r ( n n ) q u e r yi sac o m m o nq u e r yt h a ta s k st h ec l o s e s to b j e c t st oq u e r yo b j e c t i nb o t hs p a t i a ld a t a b a s ea n d s p a t i o - t e m p o r a ld a t a b a s e f o rt h ei m p l e m e n t a t i o no f n n q u e r y , t h ef o r e m o s ts t e pi st od e s i g na n dc a r r yo u ts u c hr e l a t e dq u e r ya l g o r i t h m s w i t ht h ec o n t i n u e da d v a n c i n gi 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 n o n l n g t e c h n o l o g i 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 f m o v i n go b j e c t sa r eg a i n i n gi ni n t e r e s t c u r r e n t l y , t h et p r t r e e ( t i m e p a r a n a e t e r i z e d r t r e e ) i st h ei n d e xo f c h o i c ef o rt h ee f f i c i e n tq u e r y i n go f t h ec u r r e n ta n da n t i c i p a t e d f u t u r ep o s i t i o n so f s u c hm o v i n go b j e c t s ，s ot h er e s e a r c ho nt h en nq u e r ya l g o r i t h m s f o rt p r - t r e ei so f m u c hs i g m f l c a n e e i nt h i sp a p e r , t h eo t h e rp e o p l e sr e s e a r c hw o r ko nn nq u e r ya l g o r i t h m sa r e p r e s e n t e da n da n a l y z e df i r s t l y a f t e r w a r d s ，t h ec o m p u t a t i o no fm o v i n go b j e c t s d y n a m i cd i s t a n c e si nt p r t r e ei sd i s c u s s e d t h e n ，b a s e do nt h ep r e v i o u sr e l a t e d w o r k ，t h ep r o p o s e de x t e n d i b l ek n e a r e s tn e i 【g h b o r s ( k n n ) q u e r ya l g o r i t h mf o r t p r t r e ei sp r e s e n t e d t h ea l g o r i t h mc o n s i s t so ft w op a r t s ：t h eo p t i m i z e dn o d e p r i m i n gs e a r c hi nt p r t r e ea n dd e a l i n gw i t hm o v i n go b j e c t si nl e a f n o d e i na l l u s i o n t om o v i n go b j e c t s u p d a t ea f t e rg e t t i n gt h en nq u e r yr e s u l t s ，t h ep e r s i s t e n c eo fq u e r y r e s u l t su n d e rs u c hc o n d i t i o ni sd i s c u s s e d f u r t h e r m o r e ，as i m p l ea n dc o n v e n i e n t c o n t i n u o u sn e a r e s tn e i g h b o r ( c n n ) q u e r ym e t h o db u i l tu p o nt h ep r o p o s e dk n n q u e r ya l g o r i t h mi sp u tf o r w a r d s u c hm c t h o db a s e do nt h ei d e ao fe x e c u t i n gn n q u e r yd u r i n gac e r t a i ni n t e r v a ld e t e r m i n e st h eq u e r yi n t e r v a lt h r o u g ht h en e a r e s t n e i g h b o rl i s t f i n a l l y , t h ep e r f o r m a n c eo ft h ep r o p o s e dq u e r ya l g o r i t h m s i s i n v e s t i g a t e dt h r o u g he x p e r i m e n t s d u r i n gt h ee x p e r i m e n t s ，t h ea l g o r i t h mi sa n a l y z e d o nt h ea s p e c t so fn u m b e ro fm o v i n go b j e c t s ，q u e r yi n t e r v a ll e n g t ha n dn u m b e ro f q u e r y i n gn n f o r mt h ee x p e r i m e n t sr e s u l t s ，i ti sm a n i f e s t e dt h a tt h ep r o p o s e dk n n q u e r ya l g o r i t h md o e s n to n l yp r e s e n tag o o dq u e r yp e r f o r m a n c e ，b u ta l s oh a v el o t so f s u p e r i o r i t yi ne x e c u t i o nt i m e k e yw o r d s ：s p a t i o _ t e m p o r a ld a t a b a s e n nq u e r y , t p r t r e e ，k n n ，c n nq u e r y l i 独创性声明 本人声明所叠交i 门学位论文足本人存导帅指导r 进i j 的研究工作及取得 的研究成果。掘我所知，除了文中特别加以杯汀和致谢的地方外，沦文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得 重区唑鱼太堂或 其他教育机构的学f 证或讦书而使用过的材料。与我一同j 作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：黍淼 签字日期：2 协厂年角7 日 学位论文版权使用授权书 本学位论文作者完全了解重庞整电太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文 被查阅和借阅。本人授权重庆整立太堂可以将学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：稚爿k 签字只期：渺f 年f 月占f 1日8伟月， y 君年 廿曰勾巧 d ： 二 名 ： 签 期 师 同 导 字签 重庆邮电人中硕十论文第一荜绪论 1 1 时空数据库概述 第一章绪论 随若数掘瘁技术的f 1 益成熟，越柬越多的数掘通过数掘障管理系统进行存储 和管胛。数掘戽及具管理软什是信息时代的成功案例，它们已渐渐渗透到 1 常7 l 活的各个方面。地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 这一技术的出 现，更是激发了人们开发空间数据库的兴趣。g i s 提供了便于分析地理数掘和将 地理数据可视化的机制。地理数据就是以地球表面作为基本参照框架的空i 日j 数 据。g i s 提供了一套丰富的分析功能，它们可以对地理数掘进行相应的变换。正 是g i s 技术的茁壮成长才推动了空i 日j 数据库【2 l 的诞生。 进入上个世纪九十年代后半期，将时念特性引入g i s 所带来的巨大应用价值 已越来越多地引起人们的注意。与此同时，时态数据库【3 】也得到了蓬勃的发展和 广泛的应用。时态数据库主要用来存储和管理随时问推移而发生变化的一些历史 数据，如工作进度情况，值班人员更替情况等。在时态数据库中通常含有两种时 1 b j ，一个是与现实时问相关的有效时问，一个是系统内部的系统时日j 。随着空i b j 数据库和时念数据库的发展，将两者的特点相结合，进而处理随时日j 推移而发生 变化的空l b j 数据已成为可能。时空数据库便在这样一个环境下诞生了。 时空数据库用于处理随时问变化而变化的空间信息，这给现有的数据库索 引、存储和查询等技术提出了新的挑战。作为数据库研究领域中的一个重要分支， 经过近几年的发展，在时空本体论、时空数据模型、时空查询优化与索引等方面 取得了许多成果。现实世界中的许多实体都具有空间特性和时态特性，需要数据 库管理系统提供有效的时空数据管理能力，如交通管理系统中的车辆，地籍管理 系统中的地块等。由于引入了时态特性，时空数据库在空间数据库的基础上需要 提供针对移动对象的数据模型和索引查询机制。目前的时空数据库根据所处理数 据的不同，可以分为专用于存储历史空间数据的时空数掘库和处理当前、将来数 据的时空数据库。两类时空数据库需要完全不同的索引结构束加以支持。经过近 些年的研究，时空数掘库已经得到了较大的发展，在现实中的应用也越来越广。 1 2 最近邻查询简介 删( n e a r e s tn e i g h b o r , n n ) 查诒j 1 1 耻1 是一种用于空间或时空数据库中的查 询方法，它是不同于点查询和范围查询的另一类查询方法，用来找出空日j 中距离 歪庆邮l h 人彳硕十论文 第一章绪论 某一给定对象最近的对象即最近邻，最近邻的查洵数目可以是1 个，也可以足多 个，即k n n ( k n e a r e s tn e l g h b o r s ) 杏询。根据奄i 自j 对象和被杏询对缘的运动状念， 即处r 静l | 口e j 三：功状态，最近邻卉询t 受分为：静态对象的最近邻赴咖和移动对 象的最近邻夼啪。向移动对象的最i 叵邻态询又廿丁恨掘被查询对象的运动状念分 为：移动对象的静态最近邻奋询( 破存询对象处于静止状念) 和移动对象的动态 最近邻查询( 被查自j 对象处予运动状态) 。最近邻查询在许多应用中部很常见。 例如，电子商务网站接收到砖籍订单后应该把订单发送到最近的配送l p 心。埘丁= 最近邻奄洵的实现而言，最重要的是其相关查询算法的设计和实现。 1 3 论文背景及国内外研究现状 随着移动通信技术的飞速发展，移动通信已经得到了较大的普及。伴随着移 动通信的迅速普及，通过全球卫星定位系统( g l o b a lp o s i t i o n i n gs 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 ，l b s ) 已成为可能。通 过服务器端的时空数掘库可以为用户提供多种增值的定位服务，如查询当前所在 位置、最近的加油站在哪里等。这使得针对时空数掘库中移动对象的相关查询技 术成为研究的热点，而与空间数掘库所不同的是，时空数据库中所存储的都是动 态数据，这又给其查询机制的设计增加了难度。在基于移动对象数据库的移动定 位服务中，很多时候移动用户希望知道离自己最近的特定目标在什么地方，移动 对象的最近邻查询已成为目i i i 研究的重点和难点，对于l b s 技术的广泛应用具 有非常大的现实意义。 国外目前在时空数据库技术领域的研究处于世界领先地位，已有的最近邻查 询技术的研究成果都是国外学者取得的。由于在空问数据库和时空数据库这类存 储海量数据的数据库中查询操作代价很大，已提出的用于最近邻查询的查询算法 都是基于索引技术的。对于空日j 数掘库而言，r 树【4 】【5 】及其变体【6 】已成为应用最 广的空日j 索引结构，在一些提供了空间扩展的商用数据库中已经能够看到r 树 的应用。已有的用于空间数据库的经典最近邻查询算法都是基于r 树的，如： b a b 算法【7 1 和b f 算法【8 l 等。但这些查询算法都只是针对静念的空日j 对象，无法 直接用于移动对象的最近邻查询。经过近几年的发展，已有一些针对时空数据库 中移动对象的最近邻查询算法相继提出，比较典型的有：b e n e t i s 算法【9 i 和 r a p t o p o u l o u 算法1 1 0 j ，其它移动对象的动态最近邻查询算法基本上都运用了与其 相似的查询方案。这些查询算法都各有自己的优势和缺陷，在对已有查询算法进 行分析比较的基础上，研究如何能够更加高效的处理动态最近邻查询已成为目前 研究的重点。 国内对时空数掘库的研究和应用与国外相比相对滞后，对于时空数据库技术 2 垂大邮i u 人等硕十论文 第一章绪论 的研究非常少，专fj 针对最近邻查询技术的研究也不多i “】。从涉及空m 数据库研 究们p 位束石，现仃还很少，主要确- i l ：9 , 人学、中用人民大学、中j 手l 学技术大 。 ，币驴、邮电夫亨和f 乜r f 技大学等少数k 授。从论义发表柬石，f 】天时空数捌 峰的文献中所涉及的范围、广度和深皮仍然有限。 目日0 ，虽然已有一些针对时空数掘车中移动对象的最近邻存词算法提出，但 人都存在着一定的局限性，主要表现色如f 几个方而： 1 能够翻效处理查询对象和被商询对象都处丁运动状态的奄洵算法( 即移动 对象的动态最近邻查询) 还比较少； 2 已有的查询算法在移动对象的动态距离的计算上都没有考虑移动对象的 参考时问； 3 在查询算法的设计过程中，对查询执行的已知条件作了相关假设，扩展性 不强。比如，假设在查询执行时，已经计算了所有移动对象与查询对象之间的距 离变化情况。而当移动对象数目很大时，计算移动对象动态距离的系统开销极大； 4 已有的研究成果对最近邻查询和连续最近邻查询几乎都足单独讨论的，可 同时支持两种最近邻查询的查询算法较少。 1 4 论文工作内容 在现实世界中，运动中的物体更容易引起人们的注意，并且它们的位置通常 都是由二维坐标来表示的。在现实中的移动对象都处于运动状态中，而已有的最 近邻查询算法几乎都对被查询对象的运动状态作了不同程度的静态假设，无法满 足现实的需要。由此可见，如何能利用现有的最近邻查询的研究成果，提出一个 可应用于移动对象的高效的最近邻查询算法，是个很值得研究的课题。 目前最流行的用于索引移动对象现在和将来位冒的索引结构是t p r 树【1 2 1 及 其变体【1 3 l 【1 4 】。现在虽然已经有很多最近邻算法被提出，但支持动态最近邻查询 特别是针对t p r 树这样的动态索引结构的查询算法较少。本文将主要研究基于 t p r 树的动态最近邻的查询算法。为便于讨论，查询算法的设计将主要针对二维 空间中的移动对象的最近邻查询的研究，但该算法也同样适用于多维的情况。本 文的主要研究内容如下： 1 研究t p r 树的结构及其动念特性； 2 提出在考虑了移动对象参考时| 日j 的情况下动态距离的计算方法： 3 在对已有的最近邻查询算法进行分析的基础上，拟提出一种基于t p r 树的可扩展的最近邻查询方案，并提出相关的查询算法； 4 在该算法的基础上进行改进，使其能够支持多个最近邻对象的查询； 5 考虑在移动对象发生更新的情况下，如何维持查询结果的有效性； 咀庆邮电人中硕十论文第一章绪论 6 在该算法的基础上实现连续最近邻查询。 1 5 论文组织与结构 论文的绢织结f ：i 如f ： 第二章将会对空叫数据库和时窄数据库中所使用的索引结构的基本理论作 一个简单的介绍。 第三章介绍了目前最近邻奄询算法的研究现状。 第四章将会介绍提出的用于t p r 树这个时空索引的多个最近邻移动对象的 查询算法，并在这个基础上提出连续最近邻查询的实现方法。同时，对移动对象 发生更新的情况下，对维持查询结果的有效性也作了相关的讨论。 第五章将会对所提出的最近邻查询算法进行仿真实验，并进一步作性能分 析。 第六章将总结本文所做工作，并探讨了进一步的研究方向。 4 叵庆邮l u 人中硕 论文 第一章最近邻存询算法的研究现状 第二章时空数据库相关理论简介 近年末空问数掘庠1 2 1 中随时间而变化的信息越束越受坌u 人们的关江，时念 g i s 的思想和j l ! 沦逐渐地产生和发展起来。作为时念g i s 的核心，时空数掘库 其他类掣的j 、：，用数据库叶等，除了需要实现时空数据的组织、存储、转换及简单 的检索之外，逊应根掘自身的应用需求提供相应的时宅分析能力。 2 1 时空数据简介 随着空i b j 数据库和时态数据库【3 i 的发展，将两者的特点相结合，进而处理随 时间推移而发生变化的空问数据已成为可能。时空数掘库用于处理随时间变化而 变化的空问信息，这给现有的数掘库索引、存储和查询等技术提出了新的挑战。 作为数据库研究领域中的一个重要分支，经过近几年的发展，在时空本体论、时 空数掘模型、时空查询优化与索引等方面取得了许多成果。现实世界中的许多实 体都具有空| 日j 特性和时念特性，需要数据库管理系统提供有效的时空数掘管理能 力，如交通管理系统中的车辆，地籍管理系统中的地块等。由于引入了时态特性， 时空数掘库在空问数掘库的基础上需要提供针对移动对象的数据模型和索引查 询机制。 为了表示在时空环境下的移动对象，时空数据库在空问数据库的基础上引入 了新的时空数据模型【1 5 】【1 6 1 【切。到目前为止，绝大多数关于移动对象数掘模型的 研究都集中在对历史信息的描述上。e r w i g 和s c h n e i d e r 在他们的时空查询语言 s t q l t 博l 的设计中，引入了抽象数据类型的思想1 9 1 1 2 0 l 【2 1 】。s i s t l a 和w o l f s o n 在他 们的未来时态查询语言f t l 中提出了一种可用于未来查询的m o s t l 2 2 1 数据模型， 但他们并没有给出具体的查询处理解决方法。 对于一个移动对象，给定一个时间点t ，移动对象有一个唯一的位詈与其相 对应。如果只对某个移动对象的位置感兴趣，而它在任一时间点的位置表现为时 空坐标中的一个定点，那么它的运动轨迹在时空坐标中表现为一系列曲线。如果 移动物体还有一定的形状，那么它的位置为它的几何中心的坐标。如果还要对一 个移动物体的形状特征( 注意：形状可能也是随时| 日j 改变的) 进行描述，那么它 在一定的连续时问内表现为一系列立方体。由于移动的线在现实中并不多见，在 空间数掘库中未对其考虑。图2 1 表示了移动对象的离散运动轨迹的表现形式。 匝庆邮电人中硕十论史 第二章最近邻存洵算法的研究现状 r ，与前时驯 图2 1 移动对象的离散远动轨迹 为了执行时空查询，在时空数据库中对一些基本的数据类型也提供相应的时 空版本2 3 1 。与空间数掘库一样，时空数据库同样也引入了作用于时空对象的时 空操作符和时空谓词。在时空数据库中的最近邻查询，主要针对的是移动点对象 进行研究。 2 2 索引技术简介 空间数据库与时空数据库，由于要处理庞大的数据，查询处理和数掘存储都 是围绕着索引结构展丌的。因此，时空索引结构在时空数据库中起着十分重要的 作用。 2 2 1 空间索引技术简介 随着空间信息技术的不断发展，空间数据库已经成为存储和处理空间信息强 有力的工具，为地理信息系统( g e o g r a p h i ci n f o r m a t i o ns y s t e m ，g i s ) 和其他应用提 供优化的数据库技术。目前，许多主流的商用数掘库都提供了对空间数据的支持。 为了查询处理空| 日j 数据，空间数据库不仅提供了相应的数据类型和查询语言，而 且实现了特定的索引结构和查询机制来进行空间查询。 由于空间对象和空间操作的复杂性，使得空问数据库中的空间操作既是f o 密集型又是c p u 密集型的因此，充分利用空日j 索引【5 1 1 2 4 1 有效地进行空| 日j 检索， 是空间数据库的一项关键技术。为了快速、有效地处理存储于空间数据库中的空 问数据，已提出了大量的空间索引方法，包括网格文俐2 5 】【2 6 】、k d 树、四叉树和 r 树及其变形树等。 1 k d 树 k d 树2 7 1 1 2 8 1 是早期的多维数掘结构之，也是一棵存储k 维空间点的二叉索 引树。在每一个中甘j 结点，k d 树把k 维空日j 分成两个k - 1 维超平面，即k d 树 亚庆邮电人中硕卜论文 第二章最近邻卉向箅法的研究现状 顶层结点按一绐划分，下一层结点按另一维进行各个维循环往复。当一个结点中 的 数少于给定的最大点数时结束划分。图2 2 表示了_ 维守问中的一组点以及 返些血n 0k d 似夷万：。匀条线对应f 树中i 疗一个结点，什f 结点的最大 数设为l 。 存x 轴卜# i 、i i i 幕发为偶数的随( 般i 内深度认为是o ) ，y 轴r 杯江深度为奇数的值。 a 图2 2 平面上的点的分布及对府的二叉树 新结点的插入很简单；删除可能会导致在删除结点以下的树重新组织，这样 删除就可能变得很复杂。三维以上的点数据更适合使用k d 树。k d 树划分平面 是由点的位置决定，而不是以最可能的位置划分平面，从而导致了该树是一棵非 平衡树。直观上，k d 树适合静态结构，如果频繁进行插入和删除操作，很难维 持其平衡。 2 四叉树 四叉树2 6 1 1 2 明具有一个根结点，每个中问结点有四个孩子。四叉树的每个结点 对应一个正方形或是多维的一个立方体。四叉树主要用于对点数据、曲线、以及 面的表示。四叉树每一层分解成等同的部分，也可以由输入决定。分解的方案可 以事先确定，或者由输入数掘的特性决定。 。 3 r 树及其变形 到目i ； 为止还没有被一致认为是最好的空间索引结构，但r 树1 4 1 1 5 1 及其变形 是空日j 数据库中应用最多的索引结构，已经可以在商用的d b m s 中看到r 树索 引。r 树是一种层次数据结构，它是b 树在k 维空间上的自然扩展，因此和b 树一样，r 树是一种高度平衡树，它能确保高效地利用存储空问。r 树中的结点 所存储的是空间对象的m b b ( 最小的边界框) ，而不是空间对象实际的空l 日j 大小 或形状。图2 3 表示了一个典型的二维r 树结构，它由中日j 结点和叶结点组成， 叶结点存储的是实际空间对象的最小边界矩形( m b r ) ，以及指向实际的空间数 据的指针。在中问结点中存储的是其中各子结点实体( e n t r y ) 的最小边界矩形 ( m b r ) 和指向子结点的指针。r 树的每个结点对应了磁盘上的一个页面，罩 面存储了予结点的相关信息以及指向子结点的指针。 7 -1 v 。 唾庆邮l b 人中硕十论文第1 二章最近邻杏询算法的研究现状 “匝 7 n ，口田n 。血 妣圆 ， n s 口口 、 骱口口 ( a )( b ) 图2 3r 树示例( a ) r 树中结点的最小边界矩形( b ) 相应的树形存储结构 其后，人们在r 树的基础上，提出了许多r 树的变体，如r + 树、r + 树，其 中最著名的是r + 树 5 】【“。它通过大量对不同分布数据的实验研究，找到了一系列 相互影响的决定检索性能的参数，提出了一系列结点分裂优化准则，设计了结点 强制重插技术。r 树在r 树的基础上对插入算法进行了改进，将树中的兄弟结 点之l 、h j 的交叉区域减小到最小，这样做的直接优点是使在对象搜索中所穿过的路 径最小化。 r 树提高了r 树的空i b j 利用率，从而极大地改善了树结构，显著提高了查询 性能，但同时也增加了c p u 计算代价。 2 2 2 时空索引结构简介 到目前为止，人们已提出多种索引结构来对时空数掘进行索引。按照时态查 询范围，它们通常可以被分为三类：查询历史时空数据的索引( 如：t b t r e e ， s e t i ) ，查询当时数掘的索引( 如：2 3t r - t r e e ，l u r t r e e ，b o t t o m u pu p d a t e st r e e ) 以及可预测未来位詈的索引( 如：t p r t r e e ，t p r * t r e e ) 。在第三种索引结构中， 通过引入速度参量，能够对移动对象将来的位置进行预测。其中，t p r 树是最具 有代表性的索引结构，其它可预测将来位置的索引结构皆是在它的基础上演变而 束。 1 t b 树 t b 树1 3 0 】是基于b 树的索引结构，它所存储的是移动物体的运动轨迹片断。 在每个叶结点中所存储的轨迹属于同一个运动对象，这样便于历史运动轨迹的重 组。但同时，地理位置帽近而属于不同移动对象的轨迹却存储在不同的结点中。 随着存储轨迹片断的增多，t b 树对空问位置的识别能力显著下降，这使得基于 重呔邮电人学硕十论文第_ 二章最近邻卉询笄法的研究现状 位冒条件的时空查询的效率变得很低，但对于运动对象的轨迹查询t b 树具确较 人们优势。 2 i ，u r 树 l u r 尉( l a z yu p d a t er t r e e ，l u r t r e e ) | 3 h 是基丁r 嗣的针对移动对象“ji h 仃 营的索引结构。对1 - 迮线运动的对象，山f 移功对象的当前位霄不断更新，这使 得索引的更新频；靼增大，影响了性能。l u r 树提供了一种惰性史新的机制，如 果移动刈象的何胃没有超原先所在m b r 的范幽，则只对u if 绐点中相应的项 进行史新，向不对m b r 进行更新，即使m b r 此时已不再足最小边界矩形。因 为这并未违反r 树的定义，只要父结点的m b r 包含了其所有子结点的m b r ，r 树就是有效的。l u r 树还通过对m b r 增加一种扩展机毒i ( e m b r ) 来处理频繁在 m b r 边界移动的对象。除此以外，l u r 树还提供了一个直接链接表( d i r e c t l i n k ) 来对叶结点直接进行访问，以提高访问效率，如图2 4 所示。 自接链接衷 图2 4 l u r 树的结构 3 b o t t o m - u pu p d a t e s 树 为了处理移动对象的频繁更新问题，在b o t t o m u pu p d a t e s 3 2 】树中也使用了 l u r 树中的惰性更新和直接链接表( d i r e c t l i n k ) 的技术。所不同的是，通过不同 的链接表，不仅可以直接访问叶结点，也可以直接访问中间结点。与一般的r 树更新不同，b o t t o m u pu p d a t e s 树提供了一种自底向上的更新方法，提高了更 新效率。 4 t p r 树 t p r 树( t i m e p a r a m e t e r i z e dr - t r e e ，t p r - t r e e ) l ”1 是具有r 挝结构的平衡树，用 束对动念目标进行索引并能够回答对移动对象的未来查询。与r 树一样，t p r 树中的一个结点对应了一个数掘页面，页面中存储了该结点所包含的各项( e n t r y ) 9 重庆邮电人学硕十论文 第一章最近邻育询芹法的研究现状 的相关数据。存t p r 树中一个移动对象被表示为：( 1 ) 在参考时刻绑定这个对象 的最小边界诤形m p , r ：1 2 ) 1 盘i 界锋嘭f t 每一缗卜的速度矢荦组成的v b r 。与r 树一仟，t p r 树巾缸个绐点逊包括个 彳mf 结 fr j 指针，在叶纡t j ir f - i 幺指针指 向实阢的侈动肘象，通过该指t f 可以衔刮时侈动对象的汗细f 白。在t p r 树 巾，移厶j j 对象的何百n 息足通过线e i 函数柬表示的。图2 5 巾表示了叫个二维的 移动时象a ，b ，c ，d 的m b r 和v b r ，箭头和旁边的数宁分别代表移动对象在相应 维度的速度方向f 人小( 负号表示代表运动方向足沿着半杯轴的负方i h j ) ：a ，b ，c ， d 的v b r 分别为a 、= 1 ，1 ，0 ，0 ，b 、= 2 ，1 ，1 ，1 ，c v = i o ，2 ，l ，一2 ，d 、= l ，一2 ，l ，一l 。 图2 5t p r 树中结点的表示方法 在t p r 树中，一个非叶子结点实体也表示为一个m b r 和一个v b r ，m b r 包含着其当前时刻的子结点实体( e n t r y ) ，v b r 由其子结点实体的v b r 在相应维 度方向的最大速度决定，这样就可以保证在任何时刻结点总是包含着其子结点实 体。在图2 5 中，移动对象a ，b ，c ，d 都在两个叶子结点n 1 ，n 2 中，其中v b r 为n l 。= 2 ，0 ，1 ，一2 ) ，n 2 v - 2 ，2 ，1 ，一2 。由于引入了移动对象的运动速度，t p r 树可对移动对象未束的运动状态作出预测以实现对将来位置的查询。对于在t p r 树中的某个移动对象o ，如果在t o 时刻它的位置为( x ，y ) ，运动的速度矢量为( v 。， v y ) ，则在t _ t o 的任何时刻，该移动对象的位置将变为( x + ( t t o ) v 。，y + ( t t o ) v y ) 。随 后，在t p r 树的基础上，又提出了一些t p r 树的变体，如t p r + 树”1 、r e 栌树【4 】 等。 本文的研究主要集中在对移动对象当曲和将束的最近邻查询，而t p r 树在这 类索引中更具般性和代表性，所以将侧重研究在t p r 树中的最近邻查询。 0 重庆邮电大学硕十论艾 第二二章虽近邻卉询算法的研究现状 2 3 小结 本章肘与最近邻杏询技术相关的时空数据库中索引技术作了一个简单的介 绍，已提出的最近邻盔谢算法大多都是基于r 树的。目日i ，t p r 树是最流行的 用于杏询现在和将束时宅数据的索引结构，研究基于t p r 树的最近邻查询算法 具有非常大的现实意义。 币庆邮电人7 硕卜论文第二章最近邻卉询算法的研究现状 第三章对现有最近邻查询算法的分析 由丁在h e l j 鼓抓晖和时窄数掘库中，索引结构存存储、杏询处理的特殊地f 电， 最近邻杏询算j 三都是刚绕着索引结构束设i l 的。| 1 日口，已有多种n n 台询算法彼 提出，主要分为针对静念对象的最近邻杏询算法、移动对象的静念最近邻查询算 法以及移动对象的动态最近邻杏询算法。 3 1 静态对象的n n 查询算法 3 1 1b a b 算法 b a b ( b r a n c h a n d b o u n d ，b a b ) 算法7 1 是最早提出的基于r 树的最近邻查询 算法。该算法使用分枝界定的r 树遍历算法，提出了两个度量标准用于r 树的 排序和剪枝，一个是m i n d i s t ，称为乐观距离；另一个是m 1 n m a x d i s t ，称 为悲观距离；分别作为查询点到树结点m b r 中最近邻对象的距离下界和上界。 假如一个n 维r 树的m b r 表示为： r ( s ，丁) w h e r e s = 【s l ，s 2 ，s 。】肌d t = i t ，t 2 ，l 。 a n ds t 。f o r l l n ( 3 1 ) 那么对于一个在n 维空间中的点p ，m i n d i s t r ) 可如下计算： m i n d i s t ( p ，r ) = i p i - r i l 2 l 。l i ，i fp ， t i ip i ，o t h e r w i s e m i n m a x d i s t ( p , r ) 可计算如下： 1 2 ( 3 2 ) 币庆m m l gm l = t 人r 硕十论文 第章最近邻卉询算法的研究现状 1。11。11，1，(ip。-tlll。j2 + ；三l p ，一m ，2 。旧 h 旧州，2 l 煞。 j 。：。k ：屯，矿p 。! = 垒生j ；。d c3 3 ， 删，如矿胆掣； 二维空问中的m i n d i s t 和m 仆琢i a x d i s t 如图3 1 所示。值得注意的是，如果 查询对象的位冒在m b r 内部，那么m i n d i s t 则为0 。 m b r x d i s t 图3 1 二维空间中的m i n d i s t 和m i n m a x d i s t 基于这两个度量标准，三个启发式规则被用来过滤不包含最近邻的结点： 1 ) 如果对某个m b rm ，它的m i n d i s t ( p , m ) 大于另一个m b rm 的 m i n m a x d i s t ( p , m ) ，那么m 肯定不包含最近邻对象； 2 ) 如果对一个给定的对象0 ，它与p 的距离大于p 与某个m b r 的 m i n m a x d i s t ( p , m 1 ，那么0 肯定不是p 的最近邻对象； 3 ) 如果对某个m b rm ，它与p 的m i n d i s t ( p , m 1 大于p 与某个对象o 的 距离，那么m 肯定不包含p 的最近邻对象。 b a b 算法通过深度优先( d e p t h f i r s t ，d f ) 遍历r 树中查询最近邻对象。首先， 从根结点开始，所有的结点根据它们距离查询点的m i n d i s t 值排序( m i n d i s t 是指查询点q 和结点e 的子树中所包含目标的距离的最小值) ，具有最小值的结 重庆邮l 也人学硕十论文 第二章最近邻存洵算法的研究现状 点首先被选择访问。这一过程不断藿复直到叶子层中第一个可能的最近邻破找 到。然后在向e 一层j 区l - l 的过稃中，这个算法只访问那些m i n d i s t 值小于当日i 被拽刽的最近邻的趼离f c t t f l f ，点。 3 1 2b f 算法 b f 算i z f , , ( b e s t f i r s t ，b f ) 博1 在b a b 算法的基础七，除去了自n 两个既不能增强剪 枝效果又具有高计算复杂度的r 树剪枝规则，减少了c p u 计算代价。b f 算法采 用一个队列保存到目前为止已经访问过的结点。丌始时，这个队列只保存根结点， 当一个结点被访问时，它就被从队列中移走，它的孩子根据它们的m i n d i s t 值 被添加到队列中，并按照m i n d i s t 进行排序。这一过程不断重复直到找到最近 邻，其具体算法描述如下： b f ( 查询对象q ，r 树1 初始化队列q u e u e r 树的根结点入队：e n q u e n e ( q u e n e ，r t r e e r o o t n o d e ，o ) 宰入队操作隐含了一个排序操作+ w h i l e ( 队列非空1d o 执行出队操作：e l e m e n t i ) k 列头项到q 的距离 f i r s t ( q u e u e ) k e y ) t h e n 对象入队：e n q u e u e ( q u e n e ，o b j e c t ，d i s t ( q ，o b j e c t ) ) e l s e 该对象是最近邻对象 e n d i f e l s ei f ( e l e m e n t 是一个叶子结点1t h e n f o r ( 叶结点中的每一项( o b j e c t ，r e c t ) ) d o 执行入队操作：e n q u e u e ( q u e n e ，【o b j e c t ，d i s t ( q ，r e c t ) ) e n d f o o e n de l s e i f e l s e 严非叶子结点+ f o r ( 该结点中的每一项( n o d e ，r e c t ) ) d o e n q u e u e ( q u e u e ，n o d e ，d i s t ( q ，r e c t ) ) 1 4 亚陕邮l 乜人学硕十论文第二章最近邻存咖算法的研究现状 e n d f o r e n de l s e b f 算法采片j 了个b f 算江是一个较为优越的用于r 尉的最近邻查询算法， 冈为这种方法从所自结点中选择一个要处理的结点，可以从全局进行挎制，从向 只t 方问必要的结点。 然而，不论是b a b 算法还足b f 算法都足基于r 树的，适用丁二静态环境下 的最近邻查询算法；无法满足对动态环境下的最近邻查询。 3 1 3 其他静态对象的n n 查询算法 k o m ，e t a l 提出了一种多步骤的k 个最近邻对象的查询算法【3 3 1 。首先，根据 存储数据，k 个候选对象被选择出来，通过扫描候选对象，将d 。被置为它们中 到查询对象p 的最大距离。然后，通过区域查询找出与p 点距离小于d 。的对 象，并保持不少于k 个对象的查询结果，通过扫描重新更新d 。最后得到最 终的结果。s e i d l 和k r i e g e l i ”l 对这种方法进行了扩展。在他们的算法中，每一次 找到一个候选对象，都对d 一进行更新，使得查询性能得到大大提高。 还有一些方法通过提出更适合最近邻查询的索引结构来处理多维数据进行 最近邻查询，如s r t r e e i ”l 。 3 2