（计算机应用技术专业论文）tpr树在基于位置服务系统中的应用研究.pdf

江苏大学硕士学位论文 摘要 时空数据库技术是计算机科学的新兴领域。面对着海量的数据，如何在给定 的空问及时问范圈内实现对移动对象快速有效地查询，是实现定位服务、智缝交 通、数字化战争等诸多应用中迫切需要解决的问题。时空索引技术是解决上述问 题的关键技术。 t p r 树是一种可以对移动对象当前位置及未来位置进行有效索引的时空索 引技术。t p r 一树用t p 懿r 仃i m e - p a r a m 醐斑z 甜b o u n d i n gr e c t 褫酉e ) 来近似表示对 象，其基本算法和r 掌一树类似。四辩树不但支持对移动对象将来位置的预测查询， 丽且数据存储量和数据更新频率都相对较低。但髓r 树荠没有得到广泛的应用， 主要是因为其存在以下不足：对移动对象预测查询的精确度不高：t p b r 之间的重 叠随着时间的推移而越发严重，从而影响t p r 树的查询性能：算法的时间花费较 高，不利于系统作出快速的响应。 本文对t p r 树的性能优化进行了研究。首先介绍了时空索引技术研究方面 的成栗。接蓿，根据卯r 树的特性，设计一种可以实现实时查询以及预测查询 的基予位置服务系统。然后分别从四个方面对t p & 树进行研究以及改进：( 1 ) 通 过引入记录的生命期，过期记录( 甑p i f e de l l t f i e s ) 不再被真更删除，只是简单记载 过期的时刻，从而使t p r 树可以应答对移动对象历史信息的查询：( 2 ) 对t p r _ 树所索引的数据对象进行扩展，使得t p r 树可以管理更为一般的数据对象；( 3 ) 提出一种同时考虑移动对象的空间属性和速度属性的结点分裂算法，算法在投影 定积分值最大的轴上进行分裂，并把某段时问内子结点周长的定积分作为代价函 数，不但降低了算法的计算时间，而且使用此算法所建立的开r 树的查询速度 也得到了一定的提高；4 ) 一种可以限制t p 转r 之闽无限重叠的基于距离的结构 调整策略，该算法通过强制重插在某个方向上的移动距离超过阚值的移动对象所 对应的记录，从而达到调整t p r 树整体结构的目的。 实验表明，与原t p r 树结点分裂算法相比，改进后的结点分裂算法的计算 时问降低了5 8 倍，查询速度至少提高了5 0 ：而且，在此基础上应用基予距 离的结构调整策略使查询速度进一步提离约1 0 。 关键词：时空数据库索孳l ，空闻位置预测查询，袋罐 ，静r 弗| ，基于位嚣服务。 江苏大学硕士学位论文 a b s t r a c t s p a t i o - t 如p o 蹦d a t a b a s e ( s t d b ) i san e w6 e l di nc o m p u t 盯s c i 朋c e f a c i n g w i t i ll a r g en u m b e 舟o fd a t a ，f 缸t 趾l de 衔c i t l yi n d e x i r 唱m o “n go b j e c t si nc e r t a i n s p 撕a l 锄dt e m p o m le x t e n ta r cac m c i a li s s i n 删la p p l i c 撕o nd o m a i n s ，眦c h 硒 l b s ，1 1 1 t e l “g e n c et f 锄s p o r t a t i o n 锄dd i g i t a ib a n l e s p a t i o - t e m p o r a li n d e xi s l ev i t a l 妣h n i q u ef o rs o l u t i o no fa b o v ep r o b l e i n s s p a t i o t e m p o r a li n d e xm e t l l o d sf o c u so n 撕oo n h o g o n a ld i r e c t i o n s ：( 1 ) i n d e x i n g t h ep a s t ，( 2 ) i n d e x i n gt h ec l l 嗍1 t 粕dp r e d i c t e dm t u r ep o s i t i o n s t h e r ea r em o 坞 c o n c e 岱a b o u tl a t t 盯o n eb e c a u s eo fi t s 如n c t i o n si np r a c t i c a la p p l i c a t i o r 坞t h e t p r 一仃e ei sat y p i c 面s p a t i o t e l p o 同i n d e xt e c h n i q u et h a t 舳p p o r t st h ee m c i 肌t q u e 聊n go ft h e 叫1 t 锄t 锄dp r o j e c t e d 向t u r ep o s i t i o 船o fm o 们n gd b j e c t s 1 1 1 e t p r - t r c e sb 髂i c 出9 0 r i t h mi st h es a m e 船山a to ft h er 幸n 优，w i mo n ee x c e p t i o n ： i n s t e a do fm b r t p b r ( t j m e p a r 锄e t e r i z 。db o u n m n gr e 吨m 掣e ) a r cu s c d ht h i sp a p e r ，w e6 r s tr e v i e wt h es t d bi n d i c e sm a th a 、，eb e e | lr e s e a r c h e d s p e c i a l l y ，w ef o c u so nt h et h r e em o s ti m p o n 觚ti n d i c e s ，i e ，r - 仃e e 觚dt p r t r w ew i l l0 0 i n c e n t r a t eo nt h c i rb a s i cs n l j 咖r e sa n da l g o r i t h m s ，勰w e l la s ( h e i r a d v a n t a g e sa n dd i s a d v a l l t a g e s b y 柚a l y z i n gt h es 仃u c t u r ea n da l g o 珊i n l so ft p r t r e e ，al b s ( l o c a t i o n b 黜d s e r v i c e ) s y s t 咖s u p p o r tp r c d i c t i v eq u e r yi sd e s i 朗e d t 1 1 e l l ，p a p e ra l s om a k e s m e i m p r o v e m 饥tt om es 咖c t u r e0 ft p r 一仃e e s p e c i a l l y a r 啪莉w ed i s c u s s 卸d 肌a l y z et h ep e r f 0 皿柏c eo ft 1 1 ei i n p r o v e dt p r - t r 髓t h ee x p e r h e m a lc o m p 撕s o n p o i n t e do u tt h a t l ec o m p l e x 时o fi m p r 0 v e dn o d e s 讲i ta i g o r i t h mi so n l y1 2 2 0 o f 研m a 巧n o d e - s p l i ta 】g o 倒1 1 】mo ft p r - 仃e e 龇dt h et p r n - e eu s e di m p m v e dn o d 争s p l i t a l g o r i t h mw h o s eq u e r yp 曲肋锄c ei su pt o5 0 b e t t e rt h 龇岫p m a r yt p r 一仃 f u n h e n l l o f e m eq u e qp e 面咖柚c eo ft p r 吮eu s e ( id i s t 锄c e _ b 豁c ds 劬c t l 鹏 刎u s t i n gp o l i c ya l s oc a ni n s eb yl0 o rs os 0 1 e l y k e y w o r d s ：s t d b ，p 玎c d i c t i v ei n d e x ，r t e t p r - t 玎，s e a r c hp e r 南皿a n c e l b s 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密囫。 专位论j 作者签名：金i 辛蟹 ? 分埸年彦月2d 日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位敝储繇仨渚备 日期：如b 年b 月 江苏大学硕士学位论文 第一章绪论 随着移动计算，无线通信及定位技术的快速发展，人们对持续移动物体所处的 空间位置的跟踪能力不断加强，使得一些应用领域的研究( 如交通控制、实时定位 和智能导航等) 不断深入。在过去的十年旱，时空数据库研究领域得到了人们足够 的关注，在时空数据模型、时空数据索引与查询、时空推理及时空数据库体系结 构设计等方面都出现了大量的研究成果。但总体来说，目前时空数据库在理论研 究和应用上尚处于不成熟的阶段，如何有效地对移动对象进行查询、管理以及提 供准确的基于位置服务等应用需求使得时空数据库研究面临着新的挑战。移动对 象的存储和检索技术根据查询时间窗口范围可以分为三类：检索移动对象历史轨 迹信息、检索移动对象当前位置信息以及移动对象未来趋势预测。目前国内外众 多学者针对不同的应用提出了各种移动对象索引技术，但总的来说移动对象索引 技术方面的研究仍然处于初步阶段。其中移动对象未来趋势预测技术由于更适合 在智能交通调度、基于位置服务( l 0 c a t i o nb a s e ds e r v i c e ，l b s ) 等领域的应用而得 到了广泛的关注，是一个充满挑战性的研究方向。 本章1 1 节回顾了目前时空索引的发展现状，说明该选题研究的必要性及重 要理论意义和实际应用价值：1 2 节将介绍本文的研究内容，简述主要工作及在研 究过程中使用的研究方法等，并且论述了本研究的目标及贡献。1 3 节介绍本文 的组织结构。 1 1 研究背景 时空数据库( ( s p a t i o t c = i i l p o r a ld a t a b 硒e ，简称s t d b ) 是通信技术、计算机技 术以及无线网络技术相融合而产生的一个新兴研究领域。时空数据库中记录了不 同对象在不同时刻的位置，用户可以在数据库中查询移动对象的过去、现在和未 来一定时刻的状态。时空数据库中的核心技术包括以下几点： ( 1 ) 时空对象的表示 时空对象也称为移动对象( m o 、r i n go b j e c t ) ，是空间对象在时问维上的扩展。 基本的时空对象包括移动点对象( m o v i n gp o i n t0 b j e c t ) 和移动区域对象( m o v i n g r e 西0 n0 b j e c t ) 。移动点对象是指空间范围为零或只关心其位置而不考虑其空自j 范 江苏大学硕士学位论文 围的移动空间对象，移动区域对象则不仅要考虑对象空间位置随时白j 的变化，还 要考虑其空间范围的改变。时空对象除具有空间对象应有的空间特性( 位置、范 围) 外，还具有其特有的时间特性，即其位置信息会随着时间而不断发生变化。 按时空对象中时间信息的不同处理方法，时空对象的表示方法主要有： 将时间看成是时空对象的另一个维。该方法用d + l 维的空间数据表示时空 对象( 设d 是参考空间的维度) ，较为直观、简单。如在二维空间中用最小边界矩 形( m b r ) 来表示的空间对象，相应的时空对象则可用三维空间中的最小边界矩形 表示，其中三维m b r 的底为二维空间m b r ，三维m b r 的高对应于时空对象的生 命期。 对象的时间信息与空间信息一起保存。时空对象以 结构存储， 其中s 表示对象的空问信息( m b r ) ，t 是时间信息( 时间间隔) ，p 为指向具体对象 的指针。 对象的时问信息与空间信息分丌保存。使用不同时间戳的时空状态s ( t ) ( t 为时间戳) 的快照集对时空对象进行离散表示。 移动对象的轨迹表示。将移动对象的运动轨迹看成是若干线段的集合， 这样对于每个线段来说，移动对象在作直线运动。可以通过记录线段的起点、终 点和方向或者记录移动对象的起点、速度和方向等来描述移动对象的运动。 ( 2 ) 时空数据模型 时空数据模型主要包括两大类：基于时间戳的时空数据模型【5 】和基于事件和 进程的时空模型【5 】。基于时间戳的时空数据模型将时态信息集成到空间数据模型 中，采用的方法主要有：序列快照模型给层次加上时间戳：时空对象模型给空问 对象加上时问戳；基于事件和进程的时空模型针对基于时间戳的时空模型的不足 进行了改进，它采用了通过事件或是过程进行时空建模的方法。主要包括双重时 域模型( b i t 锄p o r a lc o n c 印t u a lm o d e l ) 和三元组模型( t 锄p e s tt r i a dm o d e l ) 。 ( 3 ) 时空对象索引 即如何索引频繁更新的移动对象位置信息，或者支持对于随时间不断增长的 历史信息的管理。一个好的移动对象索引( 时空索引) 的建立，可以有效地支持对 复杂的时空数据进行存耿和查询。 ( 4 ) 时空数据查询 2 江苏大学硕士学位论文 在不同的时空应用系统中，需要支持面向具体应用的特殊时空查询，如历史 信息查询、时间片查询、轨迹查询、综合查询等等，复杂的时空查询一般为下面 三种基本时空查询类型中的一种或几种的组合： 选择查询( s e l e c t i o nq u e r i 镐) 。查找在指定时间问隔内( 或指定的时问戳) 、 通过特定的空间区域( 或空间点) 的所有时空对象。例如，查找在2 0 0 7 年5 月5 r 下 午2 点至5 点之间通过南京长江大桥的所有车辆。选择查询是最基本的时空查询类 型，包括时间选择查询、空间选择查询和时空综合选择查询。 连接查询( i o i nq u 喇e s ) 。给定两个时空关系，找出这两个关系中在指定时 问间隔内相交的所有时空对象。例如，给出移动区域信息，如年降雨量及人口密 度随时间变化的信息，查询在2 0 0 3 年至2 0 0 7 年问年降雨量低并且人口密度高的省 份。 最近邻居查询( n e a r e s t n e i g h b o rq u 谢e s ) 。查找在指定时间间隔内( 或指定 的时间戳) ，离给定点( 或区域) 最近的一个或多个时空对象。如对在前后5 分钟时 间内离某事故发生地最近的救护车的查询就是最近邻居查询的例子。 时空索引技术是时空数据库的重要组成部分，在时空数据库的查询、修改、 删除、插入等过程中起着重要的作用，因为这些操作都离不开对特定数据的快速 查找。在给定的空间及时白j 范围内，如何构建高效的时空索引结构，实现对移动 对象快速有效地检索，是实现基于位置服务( l b s ) 、智能交通监测、数字化战争 等诸多应用中所迫切需要解决的问题。 目前对移动对象的索引大致包括两个方向：( 1 ) 对移动对象当前位置及离现在 不久的未来时刻位置的索引：( 2 ) 对移动对象历史位置的索引。根据移动对象空间 位置的表示方法不同，对移动对象位置的索引又可细分为离散的时空索引方法和 连续的时空索引方法。离散的时空索引方法根据移动对象在给定时问戳的空间位 置来构建索引结构，这类方法易于实现，但其更新代价较高，且无法实现对移动 对象未来时刻位置的预测和检索。连续的时空索引方法使用空间网格或线性函数 来近似描述移动对象的运动轨迹，最具代表性的方法是t p r - 树【l 】及其变种，这类 方法可以实现对移动对象当前位置以及离现在不久的未来时刻的位置信息检索。 但由于现实世界中移动对象的运动速度参差不齐，以至于那些高速移动对象会在 短时间内造成t p b r ( t i m e - p a 姗e t 嘶z c db o 吼d i n gr e c t a n 百c ) 之间的重叠，而且那 3 江苏大学硕士学位论文 些始终朝着一个方向移动的对象，会使得t p b r 无限制的扩大。另外，当线性函 数的参数变化较快时，该结构更新代价过高。这些都限制了t p r 树【l 】的实用性。 此外，还有一些研究针对限制在路网中运动的移动对象，如汽车、火车等，提出 了基于网络限制的移动对象索引结构，但这些结构无法同时实现对路网中及路网 外的所有移动对象的统一管理。 针对上述问题，本文对t p r 树的性能优化进行了研究，分别从四个方面对 t p r 树进行了改进：( 1 ) 引入逻辑删除机制，过期记录( e x p i r e de i l t r i e s ) 并不被真正 删除，只是简单记载过期的时刻，从而可以应答对移动对象历史信息的查询；( 2 ) 将t p r 树的索引目标从移动对象扩展到移动载体对象、静止对象和类似静止对 象等：( 3 ) 给出了一种综合考虑空自j 属性和速度属性的结点分裂算法；( 4 ) 针对 t p b r 之间的重叠问题，提出了一种基于距离的结构调整策略。实验表明，改进 后的t p r - 树的查询速度相比于原始t p r - 树至少提高了5 0 ，并且重新构建树的 频率也大大降低了。此外，改进后的t p r 树的通用性也得到了加强。最后，设 计了一种基于t p r 树的l b s 应用系统。 1 2 研究内容与目标 最近十年来，随着无线通讯、定位技术的发展，基于位置服务( l b s ) 得到 了非常广泛的应用。比如，需要确定每个手机用户的实时位置和一定时间内的空 间运动趋势，以便预先给特定区域分配合理的带宽，保证通讯不至于出现拥塞现 象；或者需要知道使用手机作为通讯工具报警的人的当前位置；或者需要查询某 个移动终端在某段时问内的运动轨迹：或者查询特定区域内移动终端的分布情况 以及和固定空间目标的相对地理位置信息等等。这都需要对移动终端用户的位置 信息进行实时追踪。 t p r 树【l 】是具有r 树【2 】结构的多路平衡树。使用线性函数x ( t ) = 工( t 时) + y ( t t 。f ) 来记录移动对象在某个时间段内的运动信息。x ( 1 ) 表示移动对象在t 时刻的 位置，工( t ) 表示移动对象在t 时时刻的位置， ，表示移动对象的速度矢量。t p r 树和r 树的不同之处是t p r 树的记录中存储的是t p b r ( t i m e - p a 阳m e t 甜z e d b o u n d i n gr e c t 锄酉e ) 而不是m b r ( m i n i m u mb o u n d i n gr e c t 锄百e ) 并且t p b r 的 4 江苏大学硕士学位论文 每条边会以所包含的对象或t p b r 在该方向上的最大速度扩张。 假如我们使用t p r 树对数量庞大的使用无线通讯的移动终端进行索引，由 于这些移动终端的运动可能纷繁复杂，那些高速的移动对象通常会在短时白j 内导 致t p b r 的迅速扩大，并且有些移动对象很可能朝着一个固定的方向移动很长的 距离，这样的后果就是t p b r 之间的重叠可能达到无法忍受的地步，严重影响 t p r 树的效率。 针对以上描述，本文主要对如下几方面内容进行了研究，具体概括如下： ( i )时空数据库索引技术。首先分析了时空数据库索引技术的研究现状和 分类。并详细介绍了t p r 树的基本算法以及优缺点。 ( i i )根据t p r 树的特点，设计了一种l b s 系统。 ( i i i ) 分别从四个方面对t p r 树进行了改进：首先，引入逻辑删除机制； 其次，将t p r 树的索引目标从移动对象扩展到移动载体对象、静止 对象和类似静止对象等等；再次，给出一种综合考虑空间属性和速度 属性的结点分裂算法；最后，提出了一种基于距离的结构调整策略。 通过上述四个方面内容的研究，达到如下的研究目标。 1 ) 通过引入逻辑删除机制，令t p r 树能支持对移动对象历史信息的查询。 2 ) 通过对t p r 树索引对象的扩展，达到简化索引结构，提高索引通用性的 目的。 3 ) 给出一种综合考虑空问属性和速度属性的结点分裂算法，使分裂所得结 点的周长和扩张速度都较小。 4 ) 采用一种基于距离的结构调整策略，以降低t p b r 之间的重叠。 5 ) 通过实验比较t p r 树和改进后的t p r 树的性能，说明本研究的实际意 义。 1 3 论文组织结构 本文的内容编排如下：第二章阐述时空数据库索引技术的研究现状，并且进 行分类介绍；第三章设计了一种基于t p r 树的l b s 系统：第四章分别从四个方 面介绍对t p r 树的性能进行优化研究：第五章用实验比较了t p r 树和改进后的 t p r 树的性能，并给出实验结果；第六章主要介绍l b s 系统的原型系统架构； 5 江苏大学硕士学位论文 第七章总结本文完成的主要研究工作，并简单概括论文的贡献，以及对下一步的 工作进行展望。 6 江苏大学硕士学位论文 第二章时空索引技术 第一章主要讨论了本文的研究背景以及研究内容与目标。本章将对现存的时 空索引技术进行简要的论述。 2 1 时空索引技术概述 时空数据库处理随着时问变化位置或形状的对象。时空数据库的一个典型例 子就是在d 维空间中的移动对象。移动对象通过位置探测设备( 比如，g p s ) 阅 读自己的位置。然后对象使用内在的通讯网络( 比如，无线网络) 向服务器( s e r v e r ) 报告它们的位置。服务器存储从移动对象传过来的更新，并且保留移动对象的一 个历史时空坐标信息。此外，服务器还存储额外的信息，以便帮助预测移动对象 的未来位置。典型的查询主要包括时间片查询( s l i c eq u 甜e s ) 和窗口查询。 索引技术可以极大地提高数据检索或查询的效率，因此为了有效地实现对时 空数据的查询操作，需要引入行之有效地时空索引技术。针对移动数据对象的时 空索引技术通常借鉴于空间数据索引技术，不同之处在于时空数据索引中有一维 必然是时问维。常用的一些空问数据索引方法( 如r - 树【2 1 、r 树【3 】、q u a d t r e e 【4 】 等等) 不能直接应用于时空数据索引。传统的索引方法主要用来快速检索静态的 对象，更多的只是考虑查询效率。而移动对象位置的频繁更新会引起索引结构的 动态变化，所以移动对象除了要考虑查询效率，还必须重点考虑更新代价问题。 传统的索引方法不适合于频繁更新的移动对象，必须针对移动对象设计新的技 术。 迄今为止，研究人员已经提出了一系列时空对象索引技术。现有的时空索引 技术主要有t p r 一仃e e 【、p r 嘁【5 1 、n s l 与p s i 【6 1 、 v c ir 仃e c 【7 1 、s 仉嫒骶c 【8 1 、 r e x p 缸e 【9 1 、t p 对仃甜0 1 、3 dr t i 甜1 、r t 缸甜12 1 、h r 垃甜1 3 1 、p p r 缸甜1 4 】、 m v t p r 仃甜1 5 1 、s t r 仃c e 【1 6 1 、t b 仃甜1 6 1 、 p m r q 岫d 仃甜1 7 1 、f n r 缸甜1 引、 q 卜卜艮t r e e 【1 9 1 、m v 3 r - 缸甜2 0 1 、 s e t i 【2 、s e b 仃e e 【2 2 】等等。图2 1 给出了时空索引 方法内在的空问和时间结构的演变。图中的直线表明一个新提出的时空索引结构 和原始结构之间的关系。综合目前时空数据库索引方面的研究成果，时空索引技 术按时空数据表示方式是离散的还是连续的情况划分，可分为两大类：基于离散 7 江苏大学硕士学位论文 数据表示的索引结构和基于连续数据表示的索引结构。基于离散数据表示的索引 结构采用离散的抽样时间点的数据来表示移动对象的变化过程，它支持对空间对 象当前( 历史) 位置及属性信息的查询；基于连续数据表示的索引结构通过建立移 动对象随时间变化的函数来表示移动对象，它不仅可以查询移动对象过去和当前 的位置及属性信息，而且还可以预测移动对象将来的位置和属性信息。 空闻素引 时问素引基于皿叉树的素引方法 t 茸它素引方法 索引历史信息：处理时问维 索引历史值量：处理空问维，啪时问维 墙素引历史信息：处理轨迹 童；i j 寸量的当前由素引当前位置和将来位量：基于交换索引当前位置和将来位置：基于空阍信息自口参数化 i ，7 巾l 耵，i 霸卜l ，l - ，口l 啊l 譬l ，4l 料i 日一i _ 再i 孵，i 飘- ，叠册硼口lz 呱矗册挪- 卫l 啊卜 幽2 1 ：时空索引技术纵览【2 3 】 基于离散数据表示的索引结构主要包括3 d r 树、i m 树和h r 树等。3 d r 树将时间看成是时空对象的另一个空间维度信息，用d + 1 维的空f b j 数据表示时空 对象；以r t - 树为代表的时空存取方法，将时间信息和空间信息一起存储到r - 树的结点中；以h r 树为代表的时空索引方法，使用重叠索引结构存储不同时间 戳的时空状态，其主要思想是用二维空间的索引方法对每个时间戳建立一棵对应 的暂存树。这三类方法是基于对象离散变化的情况提出的，不适合于连续变化情 况下的对象的索引。 江苏欠学硕士擘位论文 基于连续数据表示的索引结构主要研究连续移动对象运动轨迹的索引。该类 索引主要包括1 p r 树、1 甲r 幸树、f n r 树、多版本t p r 树 1 5 】、p m r 一四叉树和 r 树。其中基于黜树的时参树( 弧，戳树) 能支持对移动对象在当前和将来的位 置的有效查询，在t p 雕树中，范围矩形的坐标是时润的函数，因此，当对象移 动时，它们麓够跟随对象的变化，从而减少数据更新的次数。 接下来，本文对基予离散数据表示的索引结构和基于连续数据表示的索引结 构进行了分类阐述。 2 。2 基于离散数据表示的时空索引 基于离散数据表示的索葶f 结构主要包括3 d 砧树、r t 树和h r 省! 等。 2 。2 。l3 d r 一树 3 d r - 树在结构上和3 维r 树大致檩同，只是3 维欺树的3 维全部是空间维， 丽3 d r 弗| 剐是2 维空闯加上时闻构成3 维。要了解3 d r _ 树的结构刘必须了解基 本的乳树结构。默树是b - 树在k 维空闽上的扩展。其数据结构是由中间结点和 叶子结点构成的一棵高度平衡树。数据对象的m b r 被存储在叶子结点，中间结 点的m b r 则是包含其所有子结点m b r 的最小边界矩形。 将时阙看成是时空对象另一维度的空闻信息，这样不仅简单，且可矗接使用 传统的空间存取方法如艮树、四叉树) 处理种l 维的空间信息国是参考空闻的维 度) 。3 dr 树将二维参考空间中的最小边界矩形转换成三维空间的最小边界立方 体m 8 歉的离度对应予对象的生命期) ，以表示位置及范酲均不随时间发尘变化 的时空对象，并使用r - 树索引结构存储时空数据。图2 。2 给出了时空对象实例及 其对应的3 dr - 树。 瓣暇慧豢辩囊零 黼羚糍 豳2 2 时空对象安例及相应的3 d 站树 9 江苏大学硕士学位论文 3 d r 树适用于位置和范围均不随时间发生变化或变化较小的时空对象。 3 d r 树的优点是实现较容易，可有效地支持时间片查询，缺点是没有考虑到时 间维的特有属性，生命期长或和位置变化大的对象，都会对应较长大的三维 m b r s ，引起3 dr 树中结点m b r s 的大量重叠，会降低查询的效率。 2 2 2 r t 一树 以r - t - 树为代表的时空存取方法，将时间信息和空间信息一起存储到r - 树的 结点中，是r 树的时空版本。l 弭树中的时间和空间信息分丌维护。时空对象表 示为其生命期内的多个实体，实体以 结构存储，其中s 表示对象的空间 信息( m b r ) ，t 是时间信息( 时问间隔) ，p 为指向具体对象的指针。如果对象在 某个时间戳的空问位置不变，则实体的空间信息s 不变，仅对时态信息进行更新。 一旦对象的空白j 位置变化，则产生新的实体对应新的时间自j 隔，即需要创建一个 新的索引项插入到l m 树中。这种表示方法适用于对象移动较少的时空数据库， 如果数据库中对象的移动量较大，实体数目的增长会很可观。 在i m 树中，时间数据保存在r 树结点内。i m 树是通过空问数据库来实现， 时间数据是一个次一级的因素，仅基于时间域的查询是不可能有较好的查询效率 的。 2 2 3h r 一树 h r 一树是一种采用重叠技术( o v 甜印p i n gt e c h n i q u e ) 、将单一版本的结构转换 为部分持久( p a n i a l l yp e r s i s t e i l t ) 结构的高效时空索引结构。该结构为两级索引机 制，分别对时空对象的时间信息和空问信息进行索引： ( 1 ) h r 树是对事务时间进行索引，它按时间递增顺序将时空对象的时间信 息组织为有序表，并用时空对象不发生空间变化的那个时间片作为时空对象的时 间信息值( 时间索引结点结构如图2 3 所示) ； 区圃 j r t 陀e 图2 3 ：h r 树的时间索引结点结构 ( 2 ) 用r 树索引结构为每个时间片的空间对象建立索引，并将r 树的存储 l o 江苏大学硕士学位论文 信息( 根结点存储地址) 保存到对应时间片的时间索引结点中。为了节省空间，相 邻时间片的r 树可能会重叠，即若相邻时间片的r 树有共同的分枝，则只保存 该分枝的一个版本。 一个h r 树的实例如图2 4 所示，在时间片l ，有新的索引数据项c i 插入、 索引数据项勖被删除，引起了b o 、c o 结点的变化；但结点舢未发生变化，这 两棵r 树共享该分枝( 结点) 。 b lc 图2 4 ：h r 树实例 h r 树与其它的时空索引结构相比，具有以下特性： ( 1 ) 没有发生变化的结点不需要复制，这样节省了一定的存储空间； ( 2 ) 时问查询效率与已存储的数据量无关； ( 3 ) h r 树索引是对事务时间索引。 h r 树的主要思想是为每一个更新时刻均构建一棵独立的r 树，这样时i 日j 片 查询退化为利用r 树进行应答的空间查询，因而可以有效支持时间片查询，但 支持窗口查询时需要访问多棵r 树，效率较低。 2 3 基于连续数据表示的时空索引 该类索引主要包括t p r 树、t p r 树、f n r 树、多版本t p r 树、p m r 四叉 树和q 限树等。 2 3 1t p r 一树 t p r 树是一种基于r 树的索引方法，能够有效地索引在一维、二维和三维 空间中的移动点对象的现在与预测将来位置。t p r 树主要通过考虑移动对象的 速度与方向来预测移动对象在不久将来的大致位置；并且通过考虑在树结构中可 计算的位置来减少时问函数的频繁更新问题，同时它的更新算法也能使其自动地 江苏大学硕士学位论文 调整以适应于一个动态变化的数据集。 2 3 1 1t p r 一树的结构 t p r 树是具有r 树结构的多路平衡树。树中每个非叶子结点都由若干个 ( t p b r ，p o i n t 砷单元组成。t p b r 为当前包含其对应孩子的带时间参数边界矩形， p o i n t e r 是一个指向孩子结点的指针。叶子结点由若干个( t p b r ，o b j e c t i d ) 组成， 其中t p b r 为当前包含对应移动对象的带时间参数边界矩形。o b j e c t i d 是一个指 向移动对象的指针，通过指针可以得到对应移动对象的详细信息。本文中，用术 语边界问隔( b o u n d i n gi n t e r v a l ) 来表示一维边界矩形，用术语边界矩形( b o u n d i n g r e c t a n 西e ) 来表示任意d - 维的超矩形( d 1 ) 。 在任意时刻t ，移动对象的位置可以通过这个公式得出：工( t ) = x ( t 劫+ ，( t - t 佗f ) 。工( t ) 表示移动对象在t 时刻的位置，x ( t 劫表示移动对象在参考时白j t 化f 的位 置，而1 ，表示移动对象的移动速度。t 耐一般为索引建立时间或更新时间。 t p b r 会随着时i 日j 变化，以便在所有的时间罩都可以包含其中的移动对象或 子t p b r 。例如，一个卜维带时间参数边界问隔可以表示为： x ( t ) ，一( t ) 】，假定 在时i 、日j 间隔【t 佗f ，t 】内，对象的移动速度和方向保持不变。其中， x 卜( t ) = x 卜( t 咒f ) + v 卜( t t r e f ) x 1 ( t ) = x 1 ( t r e f ) + v _ ( t t 耐) x 卜( t f e f ) = m i n i o i x 卜( t f e f ) x 叶( t 硝) = m a x i o i x 1 ( t 耐) ) v 卜_ m i n “o i v 卜) 一= m a 】( i o i v 1 ) x 卜( t 耐) 表示在时i 日j t 佗舶带时间参数边界间隔的左边界，一( 钳) 表示在时间 t f e f 的带时间参数边界间隔的右边界；v 卜表示在时间间隔 t 佗f ，t 】内左边界的扩张速 度，一表示在时间间隔【t 耐，t 】内右边界的扩张速度；o i x 卜( t f e f ) 表示在时问t 曲 o i 的左边界，o i x _ ( t r e f ) 表示在时间t 砷o i 的右边界；o i v 卜表示在时白j 间隔【t f e f ， t 】内，o i 左边界的移动速度，o i v 1 表示在时间间隔【t 佗f ，t 】内，o i 右边界的移动速度： m i n i 是取最小值的函数，m 觚i 是取最大值的函数。 很明显，带时间参数的边界矩形并不能保证在所有的时自j 里都是最小的边界 1 2 江苏大学硕士学位论文 矩形。并且这种边界矩形从来不收缩，从而在一段时间过后很可能过度扩张。所 以，希望在对边界矩形进行更新操作时，顺便对边界矩形执行紧缩操作，以使在 更新时问t u p d ，边界矩形成为最小边界矩形( 这将在一定程度上减少t p b r 之间的 重叠) 。把t f c f 等于装入时间的带时白j 参数边界矩形称为装入时间边界矩形 ( l 0 a d t i m eb o 岫d i n gr e c t 锄g l e ) ，而t f e 等于i i p d 的带时间参数边界矩形称为更新时 间边界矩形( u p d a t e - t i m eb o 吼d i n gr c c t a n 百e ) 。图2 5 给出了这两种边界矩形。 图2 5 ：包含4 个移动点的装入时间边界矩形( 租线) 和i 更新时间边界矩形( 虚线) 2 3 1 2t p r - 树查询类型以及查询算法 ( 1 ) t p r - 树查询类型 通常可以将t p r 树支持的查询分成三类。下面，用d 个坐标轴上的投影 【口 - ，口f 】【口 ，口，】，口；口j 来定义一个d 维矩形。令r ，r l ，r 2 为三个d 维的矩 形，t ，t 卜 一为三个不超过现在时间的时间值。 第一类时间片查询( t i m e s l i c eq u e r y ) ：查询q = r ，t ) 返回在时问t 被r 包 含的所有移动对象。 第二类窗口查询( w i n d o wq u e 巧) ：查询q = r ，t 卜一) 返回在时间间隔【t 卜，一】内被r 所包含的所有移动对象。 第三类移动查询( m o v i n gq u e 巧) ：查询q = r l ，r 2 ，t l 一) 则相对复杂， 从时间t 卜到时间t 1 ，其查询窗口也从r l 变成了r 2 。如果把变量r 定义 为查询窗口的话，令r = 【口f ( t ) ，口一( t ) 】，【口；( t ) ，口，( t ) 】， r l _ 【口f ( t 卜) ，口一( t 卜) 】，【口 ( t 卜) ，口，( t 卜) 】， l b = 【口f ( 一) ，口一( 一) 】，【口 ( 一) ，口，( 一) 】， 则口 ( t 户口岁( 一卜砖( t - t ， 江苏大学硕士学位论文 口7 ( t ) = 口岁( 一卜卅( t - t ， 事e 中，砂= ( 口，( 一) - 口岁( t ) ( 一- t ， 卅= ( 口7 ( 一) 口，( t ) ( 一- t ， 1 j d ，t 卜t 一。 那么，查询q 返回在时间间隔 t 卜，一】内，被r 所包含的所有移动对象。 第二类查询是第一类查询的推广，也是第三类查询的特例( r l - r 2 ) 。如图 2 6 所示，其中使用的是1 - 维边界白j 隔，q 0 和q l 是时| 日j 片查询，q 2 是窗口查询， 而0 3 是移动查询。 ；酒二 蜂= !。c 、- j 醇罅 一 v 印 图2 6 ：l - 维数据的乔询类型不例 ( 2 ) t p r 树查询算法 为了算法说明的简单易懂，本文所提出的例子中使用的都是1 维边界矩形。 时间片查询 应答一个时间片查询的处理过程和r 树类似，唯一的不同就是在检查是否有 交叉( i n t e r s e c t i o n ) 之前必须计算在查询时间t 所有记录的t p b r 。例如，一个边 界问隔( x 卜 一，v 卜，一) 满足查询 ( 口卜，口_ 】) ，t q ) ，当且仅当口卜一+ 一( t q t r e f ) 八 口- i x 卜+ v 卜( t q k f ) 成立。 窗口查询和移动查询 对于窗口查询和移动查询( 见图2 7 ) ，其实可以把这两种查询看作是检查在一 定的时间间隔内，由查询定义的移动窗口和t p r 树中记录的t p b r 之间是否存在 交叉，然后根据有交叉的路径进行递归检查，最后得到位于这些交叉中的移动对 象。在1 维空间中这个问题相对简单，但在多维空间中则显得比较复杂。 1 4 江苏大学硕士学位论文 幽2 7 ：边界i 司隔帝l 移动乔询z 同的交义 首先，给出一种算法来检查由参数( 口f ( t ) ，口一( t ) ，口 ( t ) ，口，( t ) v f ( t ) ，v ? ( t ) ，v ；i t ) ， l ，j ( t ) ) 定义的d 维带时问参数边界矩形r 是否和查询q = ( ( 【口 ( t ，口 ( t 】，【口；( t ，口，( t 】，【计( t ，卅( t 】，【以( t ，卅( t 】) ，t 卜，一) 有交叉。 注意到：如果2 个移动矩形发生交叉，则必然存在一个时间点它们的区域在 每一维上都存在交叉。因而，对于每一绚( j = 1 ，2 ，d ) ，算法计算在该维上 矩形区域发生交叉的时间问隔i j = 【f ，f 加c t 卜，t 1 】。如果i = r 、名。i j - 矽，那么说明 这2 个移动矩形没有交叉；否则，查询算法得出矩形交叉的时间间隔i 。 根据下面的公式来计算每一维匕发生交叉的时怕i 洄i 隔： 1 5 度边界矩形 的。 肽 至 如m ” ” 帆 一虾 诹隙 诹隙 一制 惨 k 嗲 k 爿加 扎晰 u o 一 ， 问没 咖咖 办加 舯蚋 一 蝴帅 蝴帅 一卅一一一一一一一一 咐一一一一 咖蓦峨；i；|诽啡m m 啡叫 捌邱h“，m“一 江苏大学硕士学位论文 最后根据得到的时问间隔i ( i 不等于，则存在交叉) ，确定搜索t p r 树的路 径，在每条路径的叶子结点中搜索：在时自j 间隔i 内，出现在查询窗口中的移动 对象。返回所有这样的移动对象。 2 3 1 3t p r 一树删除和插入算法 r 宰树提出了一些对于性能来说至关重要的优势值( g o o d n e s sv a l u e s ) 。r 宰树算 法根据这些优势值来确定记录的最终分配。 ( i ) 面积值。 ( i i ) 周长值。 ( i i i ) 重叠面积值记录m b r s 之间的重叠面积。 ( i v ) 中心距离值记录m b r s 的中心和所在结点m b r 的中心之间的距离。 t p r 树的插入算法类似于r 枣树的插入算法，只是简单地将r + 树算法中的优 势值替换成了优势值的积分。也就是说，这些优势值是依赖于时间的，应关注它 们在时间间隔 t c ，t c + h 】内的演变，其中t c 是索引建立时间或当前更新时间，h 则是一个称作“h o r i z o n ( 用来度量树可以看到多远的未来