（计算机软件与理论专业论文）移动对象轨迹索引技术研究与实现.pdf

中山大学硕十学位论文 移动对象轨迹索引技术研究与实现 移动对象轨迹索引技术研究与实现 专业：计算机软件与理论专业 硕士生：于海斌 指导老师：叶小平副教授 摘要 上世纪九十年代以来，时空数据库领域的研究取得了极大的进展，其中，移 动对象轨迹数据管理引起了人们的广泛兴趣，并逐渐形成了专门管理移动对象及 其位置的数据库移动对象数据库。与此同时，随着移动定位技术和无线通讯 技术发展，车载定位设备、p d a 、移动电话等移动设备广泛应用，移动对象数据 库的应用越来越广泛，使得相关研究已经成为时空数据库技术的研究热点。 由于移动对象的位置随时间不断变化的特性，移动对象数据库需要管理庞大 的移动数据，为提高数据库的查询效率，需要有效的索引技术的支持，国内外学 者已经提出了大量的索引技术，其中大多数方法都是将移动对象的时间维看做空 间维，从而将时空情形转换成更高维的空间数据处理，以便利用较为成熟的空间 数据库索引技术。但是无论是从理论分析还是应用实现角度看，时间和空间毕竟 存在基本差异，研究基于时间和空间整合的时空索引技术很有必要。 本学位论文在研究并总结当前移动对象索引技术的优缺点的基础上，研究基 于时间和空间有效整合的移动对象数据索引技术。论文首先概括地描述了移动对 象数据库领域的基本概念和理论，并对当前提出的主要的移动对象索引技术进行 简要的介绍。在此基础上，讨论有效时间拟序关系和空问相平面的基本概念，提 出时间线序分枝算法和基于相平面划分方法；然后，在此框架内研究了一种移动 对象数据索引技术，其基本特征是分别考虑数据的时问和空间特性，并将时间索 引和空间索引进行有效的整合；另外，研究了基于时空索引的数据查询以及索引 更新算法；最后，本论文设计并实现了仿真实验和比较评估，相应结果表明本论 文工作是可行的和有效的。 关键词：时间拟序、线序分支、空间相平面、相平面划分、移动对象轨迹索 引 中山大学硕士学位论文 移动对象轨迹索引技术研究与实现 r e s e a r c ha n di m p l e m e n t a t i o no nt h ei n d e x i n go fm o v i n g o b j e c tt r a je c t o r i e s m a j o r ： n a m e ： c o m p u t e rs o f t w a r ea n dt h e o r y h a i b i ny u s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rx i a o p i n gy e a b s t r a c t s i n c et h en i n e t i e so ft h ep a s tc e m u r y , g r e a tp r o g r e s sh a sb e e nm a d ei nt h e r e s e a r c h e so ns p a t i o - t e m p o r a ld a t a b a s e ，a m o n gw h i c ht h et r a j e c t o r yd a t am a n a g e m e n t o fm o v i n go b j e c t sh a sa t t r a c t e dp e o p l e sg r e a ti n t e r e s t g r a d u a l l y , as p e c i a ld a t a b a s e ， m o v i n go b j e c t sd a t a b a s e ，h a sb e e n s e tu pt om a n a g et h em o v i n go b j e c ta n di t s p o s i t i o n s i m u l t a n e o u s l y , w i t ht h ed e v e l o p m e n to fm o b i l el o c a t i o nt e c h n o l o g ya n d w i r e l e s sc o m m u n i c a t i o nt e c h n o l o g y , t h em o b i l el o c a t i o nd e v i c e sl i k ev e h i c l e p o s i t i o n i n gd e v i c e ，p d aa n dm o b i l ep h o n ea r ew i d e l ya p p l i e da n dt h em o v i n go b j e c t d a t a b a s ei sa p p l i e dm o r ea n dm o r ew i d e l y , w h i c hm a k e sr e l e v a n tr e s e a r c h e sb e c o m ea h o t s p o to ft e m p o r a la n ds p a t i a ld a t a b a s et e c h n o l o g yr e s e a r c h t h el o c a t i o no fm o v i n go b j e c t sc h a n g e sc o n s t a n t l yw i t ht i m e a sar e s u l to ft h i s c h a r a c t e r i s t i c ，t h em o v i n go b j e c t sd a t a b a s eh a sah u g ed a t at om a n a g e i no r d e rt o i m p r o v i n gt h eq u e r ye f f i c i e n c yo ft h ed a t a b a s e ，t h es u p p o r to fe f f e c t i v ei n d e x i n g t e c h n o l o g yi si n e v i t a b l e s c h o l a r sa th o m ea n da b r o a dh a v ea l r e a d yp r o p o s e dag r e a t n u m b e ro fi n d e x i n gt e c h n o l o g i e s 。a m o n gt h e m ，m o s to ft h em e t h o d st a k et e m p o r a l d i m e n s i o na so n eh i g h e rs p a t i a ld i m e n s i o ni no r d e rt ot a k ea d v a n t a g eo ft h er e l a t i v e l y m a t u r es p a t i a l i n d e x i n gt e c h n o l o g i e s h o w e v e r , n om a t t e r f r o mt h e a n g l eo f t h e o r e t i c a la n a l y s i so rr e a l i s t i ca p p l i c a t i o n ，i n t r i n s i cd i f f e r e n c e sd oe x i s tb e t w e e nt i m e a n ds p a c e t h e r e f o r e ，t h er e s e a r c ho fs p a t i a l - t e m p o r a li n d e x i n gt e c h n o l o g yw h i c hi s b a s e do nt i m ea n ds p a c ei n t e g r a t i o ni sh i g h l yn e c e s s a r y t h i sd i s s e r t a t i o ns t u d i e sa ni n d e x i n go fm o v i n go b j e c t sd a t aw h i c ho r g a n i c a l l y i n t e g r a t e st h es p a c ea n d t i m eo nt h eb a s i so fs t u d i n ga n ds u m m a r i z i n gt h ea d v a n t a g e s i i i 中山大学硕l = 学位论文移动对象轨迹索引技术研究与实现 a n dd i s a d v a n t a g e so fc u r r e n ti n d e x i n gm e t h o d so fm o v i n go b j e c t s f i r s t l y , t h e d i s s e r t a t i o nd e s c r i b e st h eb a s i cc o n c e p t sa n dt h e o r i e so fm o v i n go b j e c td a t a b a s e ， p r e s e n t st h ep r o p o s e di n d e x i n gt e c h n o l o g i e so ft h em o v i n go b j e c t s ，a n dp r o p o s e sa f r a m e w o r ko ft e m p o r a l q u a s i - o r d e r i n g a n ds t u d i e sf u n d a m e n t a la l g o r i t h m so f t e m p o r a ll i n e a rb r a n c h e sa n dc l a s s i f i c a t i o no fm b r i np h a s ep l a n e a n dt h e n ，t h e d i s s e r t a t i o nd i s c u s s e sa ni n d e x i n gm e t h o do fm o v i n go b j e c t sd a t aw h i c hc a nb o t h r e f l e c tt h ec h a r a c t e r i s t i c so fs p a c ea n dt i m er e s p e c t i v e l ya n di n t e g r a t et h e me f f i c i e n t l y f i n a l l y , t h ed i s s e r t a t i o nd e s i g n ss o m es i m u l a t i o nt oe v a l u a t et h ei n d e x i n ga n dt h e r e s u l t so ft h ee x p e r i m e n ts h o wt h ew o r ki sf e a s i b l ea n de f f i c i e n t k e yw o r d s ：t e m p o r a lq u a s i - o r d e r , l i n e a ro r d e rb r a n c h ，s p a t i a lp h a s ep l a n e ， p a r t i t i o no fp h a s ep l a n e ，i n d e x i n go fm o v i n go b j e c tt r a j e c t o r i e s i v 论文原创性声明 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位做作者答字0 承叭 日期：0 辨，月堙同 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 、 篙嚣吾磬氓 r 期幽户，月渤 导师签名： 讶卜孕 醐j 年r 肌硐 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 1 1 研究背景 第一章引言 由于空间和时间是现实世界客观实体的基本因素，时态和空间数据库已分别 成为现代数据库技术中的基本领域。数据的时间和空间信息在很多重要实际应用 中相互关联，难以分割，需要统一描述和管理，因此，自2 0 世纪9 0 年代初期以来， 作为一种同时处理时空对象的时间和空间属性新型数据管理技术时空数据 库( s t d b ) 随之产生并快速发展起来。 在时空数据管理研究中，移动对象轨迹数据管理引起了人们的广泛关注。移 动对象( m o v i n go b j e c t s 基本概念主要由a es i s t l a 等人于19 9 7 年提出【l 】，此后， 移动对象数据管理逐渐成为时空数据库中基本研究课题，并形成了专门管理移动 对象及其位置的数据库系统移动对象数据库( m o v i n go b j e c t sd a t a b a s e s ， m o d ) 。对于一般的移动对象来说，由于其位置随时间变化而形状却保持不变， 因此相应的空间属性可抽象为相平面中的点。随着时间变化，点的位置在三维时 空( x ，y ，f ) 中形成一条称之为轨迹线的曲线。移动对象的轨迹线是移动对象数据库 管理的基本单元。近年来，随着移动定位技术和无线通讯技术发展，车载定位设 备、p d a 、移动电话等移动定位设备逐渐发展及广泛的应用，移动对象轨迹线应 用需求越来越迫切，应用领域越来越广阔，相关研究已经成为时空数据库技术研 究热点。 移动对象数据库需要管理极其庞大的移动数据，如果在查询处理时进行遍历 扫描会对系统性能产生巨大影响。为提高查询性能、减小搜索空间，研究和开发 有效的数据索引方法已成为移动数据查询的基本途径。移动对象的索引方法从查 询的时态角度可分为基于历史轨迹信息、基于历史和当前位置信息以及基于当前 和未来位置信息的索引三类【2 】。到目前为止，国内外学者已经提出了各种移动对 象索引方法，比如基于历史轨迹信息的索引t b t r e e 树【3 】，基于历史和当前位置的 索引技术2 3t r t r e e 4 ，针对未来位置信息预测的索引技术t p r - t r e e 5 】等。但从总 体来说，移动对象的索引技术还处于理论研究阶段。 中山大学硕：l 学位论文移动对象轨迹索引技术研究与实现 1 2 研究的出发点及意义 现有移动对象数据索引方法大都将时间维看做新增的空间维，将时空数据作 为比原有空间维更高一维的空间数据处理。这种方式可以使用现有成功的空间数 据索引技术特别是r t r e e ，有效展开相关研究与应用开发。但这种将时间等同于 空问的模式存在一些有待深入探讨的课题。例如，从概念表述上看，时间概念相 对于空间概念的表述更为复杂，更不统一，“时间等同于空间”难以反映时间概 念复杂性：从概念分类上看，时间可分为有效时间、事务时间和用户自定义时间， 而涉及到的各个空间维在本质上没有区别，将不同时间维作为空间维处理，难以 反映应用中实际语义；从涉及要素相互关系上看，时态关系注重顺序关系，而空 间关系注重拓扑关系，两者在理论分析上方式各异，在应用实现过程中效率不同； 从处理时空问题的顺序角度看，同时处理时间和空间与实际应用中先定位时间再 定位空间模式不同，而处理顺序不同可能导致实现效率的较大差异。实际上，三 维“时空”和三维“纯”空间并不完全相同，有必要在体现时空对象的时间和空 间特征处理的基础上讨论能够将它们有机整合的索引方法。 因此，针对移动对象时间和空间特征，本论文首先分别讨论了基于时态线序 分枝的时态索引t i n d e x 和基于空间相平面划分的空间索引s i n d e x ，在此基础上研 究了移动对象数据索引结构m o d i m ，该结构特点是在先进行时态索引基础上，通 过适当方式，再进行空间索引，体现了时间索引和空间索引各自特征与优势，并 对其中关键的整合技术进行了必耍探讨；此外，本论文提出的t i n d e x 和s i n d e x 模块具有基本数学支撑，能够应用于移动对象数据查询管理，也有可能适合于更 为广泛的情形；同时，本论文还设计了基本实验进行仿真，通过与常规移动对象 数据索引方法进行对比，表明本论文所提出的索引模型具有良好的可行性和有效 性。 1 3 论文组织结构 本学位论文共分为七部分。内容组织如下：第一章阐述论文研究的背景、研 究的出发点和意义，以及论文的组织结构；第二章阐述了移动对象数据库以及移 动对象索引的相关概念及理论；第三章讨论了时问拟序和空问相平面的概念，为 2 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 本论文所提出的索引模型的建立提供基本的数学框架；第四章提出并研究移动对 象的数据模型和索引模型；第五章讨论了基于论文中提出的索引模型的数据操 作，并讨论数据查询的算法；第六章是仿真实验，对本论文提出的索引模型的有 效性进行评估；第七章是对本论文的内容进行总结，并阐述了下一步工作。 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 第二章移动对象基础及理论 由于传统数据库中存储的数据在被显式的更新之前，被看做足固定不变的， 因此不适用于存储不断变化的数据，比如移动对象的位置。为了解决移动对象的 存储问题，出现了专门管理移动对象及其位置的数据库移动对象数据库 ( m o v i n go b j e c t sd a t a b a s e ，m o d ) 。本章主要阐述移动对象数据库涉及的一些 概念，并简要地讨论为提高移动对象的查询效率而引入的移动对象数据索引技 术。 2 1 移动对象基础 移动对象是位置随时间不断变化的空间对象，其位置的变化可以是离散的， 也可以是连续的。移动对象数据库的目的是为了有效的存储不断变化的移动对象 的相关信息，并为与物体运动相关的查询( 比如查询“某辆汽车在某一时刻所处 的位置”) 提供有效的支持。移动对象数据库所管理的移动对象可以是汽车、轮 船、手机用户等，对于这些对象，其位置随时间变化不断改变而对象的形状保持 不变，因此可以将这类对象抽象为移动点( m o v i n gp o i n t ) ；也可以是飓风、森林 火灾等，这些对象不仅位置随时间不断变化，而且具有一定的范围，形状也不断 变化，因此将这类对象抽象为移动区域【6 】( m o v i n gr e g i o n ) 。本论文的研究对象 是移动点，因此下面章节中，在不引起歧义的前提下，将移动对象抽象为移动点 以便于描述。 与传统数据库中存储的对象不同，移动对象具有其特有的性质：( 1 ) 移动对 象具有不确定性和不精确性。移动对象的运动具有连续性，而计算机只能以离散 的方式对数据进行存储和计算，同时由于数据采集设备的精度限制以及数据源与 数据库之间传输的时延，因此无论采用何种存储和更新策略，移动对象数据库中 所存储的移动对象的位置信息与移动对象实际的位置总会有一定的偏差，即不精 确性。( 2 ) 移动对象的查询与查询给出的时间和对象所处的位置相关。在传统数 据库中，如果没有对数据进行显式的更新，则在不同时刻的同一查询总会返回相 同的结果。但在移动对象数据库中，由于即使没有对数据显式更新的情况下，移 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 动对象的位置也可能会不断变化，因此在不同的时刻给出的同一条查询可能返回 不同的结果集。 2 2 移动对象数据模型 移动对象数据库的数据模型主要由两个方向发展而来【6 】：基于位置服务的管 理和时空数据库。 2 2 1 基于位置服务管理的数据模型 在基于位置服务的管理方面，考虑的首要问题是如何在数据库中有效地管理 移动对象的当前位置。如果简单的在数据库中保存移动对象的坐标位置，由于移 动对象的位置随时间而不断变化，需要对数据库进行不断更新。如果更新的频度 大，能够有效的保证对象位置的准确性，但频繁的更新会对数据库的性能造成严 重影响：如果降低更新的频度，可以降低系统的更新负担，但是会造成对象位置 的不准确性。因此需要采用更为有效的方法存储移动对象的位置：在数据库中存 储移动对象的运动向量( 比如对象的速度) 而不是具体坐标位置，移动向量也需 要不断的更新，但是更新的频率要小得多。 a p s i s t l a 等人提出 m o s t ( m o v i n go b j e c t ss p a t i o - t e m p o r a l ) 模型【l 】。在 m o s t 模型中，移动对象的位置被表示为时间的函数，并提出了动态属性的概念。 所谓动态属性是指即使不用显式更新，其属性值也随时间变化的属性，比如移动 对象的位置的坐标。一般地，动态属幽由三个子属性组成：a v a l u e 、a u p d a t e t i m e 、 a f u n c t i o n 。其中，a f u n c t i o n 是时间的函数并满足当户0 时，a f u n c t i o n ( t ) = o ：a 在 时刻a u p d a t e t i m e 的值为a v a l u e ；在时刻，a u p d a t e t i m e ，a 的值通过 a v a l u e + a f u n c t i o n ( t - a u p d a t e t i m e ) 计算得到；a u p d a t e t i m e 既可以表示属性的有 效时间也可以表示事务时间。 由此可见，在基于位置服务的管理中，数据库只存储移动对象当前状态信息 ( 如当前位置，当前速度等) ，因此主要目的是通过有效的管理移动对象的当前 位置，从而满足对移动对象当前位置的查询或者未来位置的预测。 6 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 2 2 2 移动对象时空数据模型 与基于位置服务的管理类似，在时空数据库方面，也需要对移动对象的大量 信息进行存储，但不同的是，在时空数据库中不仅要存储移动对象的都当前状态， 而且要存储移动对象的所有历史状态，以便能够查询移动对象在过去某一时刻的 运动状态信息。 为了有效存储和管理移动对象的运动轨迹，通常在离散时间点对移动对象的 位置进行抽样，通过一系列直线段将抽样位置连接形成折线段以表示一个移动对 象轨迹。一般情况下，平面上一个移动对象的运动轨迹被抽象为三维空间的折线， 其中，两维用来表示对象所在空间平面，第三维用来表示时间【6 】o 定义1 - 1 ( 移动对象轨迹) 在一个三维空间x x y x t 中，一个移动对象的轨 迹表示为由序列点，y l ，t 0 ，( x 2 ，y 2 ，f z ) ，( 洳，弦，厶) 构成的折线，其中 t l t 2 t n 。折线中的每一段都是直线段。对于一条给定的轨迹t r a j ，在二维 空间平面x x y 的投影叫做t r a j 的路径，如图2 1 所示。 图2 - l 移动对象轨迹 同样地，移动对象的位置也被看做时间的函数，由定义2 1 可知，移动对象 在时刻的位置为，矽) ，在时间区间【t i , t , + i 内，移动对象被假定从点，矽) 到点 + 1 ，矽+ 1 ) 沿直线做匀速运动，其速度可以通过公式 7 中山大学硕士学位论文 移动对象轨迹索引技术研究与实现 m ：坚型二挈生丛掣得到。因此移动对象在时间区间 t i , h + l 】内任意时刻 ( + 。一) 的位置可以通过线性插值的方法得到。 2 3 移动对象数据索引技术 在移动对象数据库中，通常要管理数量极为庞大的移动数据。在进行数据查 询时，如果遍历扫描所有的移动对象必然会严重影响系统的性能。因此为减少搜 索空间，有效地实现对移动对象的查询操作，需要引入有效的移动对象索引技术。 移动对象数据的索引技术研究已成为移动对象数据库领域的一个研究热点，到目 前为止，已经提出了大量的索引方法，由于时空数据与空间数据的相似性，大多 数索引方法将时空数据的时间维作为空间维处理，在成熟的空间数据库索引方法 ( 如r t r e e 7 ，四叉树【8 】等) 的基础上进行扩展，比如3 dr - t r e e 9 1 ，h r - t r e e 1 0 1 ， m v 3 r - t r e e 1 1 1 ，t b 骶e 【1 2 】等。本节将对移动对象数据索引的相关基础及现有的一 些索引技术作简要阐述。 2 3 1 移动对象数据索引基础 现有的移动对象索引技术大都基于空间索引技术r - t r e e 及其变形树( 如 r * - t r e e 1 2 】等) 和四叉树( q u a d t r e e ) ，本论文所提出的索引模型中对空间维的索 引也借鉴了四叉树的思想。 r - t r e e 7 】在1 9 8 4 年提出，主要用于空间数据的索引，其后在r t r e e 的基础上 提出了一系列的变形，形成t r - t r e e 系列空间索引技术。r t r e e 是一个层次数据结 构，可以看作是b t r e e 在n 维空间上的自然扩展。因此与b t r e e 类似，r - t r e e 是一个 高度平衡的n 叉树，叶结点中包含实际对象数据的指针。r t r e e 的结点分为叶结点 和目录结点。叶结点中的索引项用( m b r ，o l d ) 表示，其中d 耐为指向实际对象的指 针，m b r 为包含d 耐指向的对象的最小外包矩形；目录结点的索引项用( m b r ， n o d e i d ) 表示，其中力d 沈f 踹向下一层结点，m b r 为包含n o d e 耐所指向的结点中所 有索引项的最小外包矩形。 设m 为每个结点包含的索引项的最大个数，m 为每个结点包含的索引项的 最小个数，其中m m 2 。r - t r e e 满足以下特点： 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 ( 1 ) 每个结点包含m 到m 个索引项，除非它是根。 ( 2 ) 根结点至少包含两个子结点。 ( 3 ) 所有的叶结点都在同一层上。 图2 - 2 给出了空间对象及其对应得r - t r e e ，其中空间对象的个数为1 1 ，对应 r t r e e 中索引项的个数满足m = 4 ，m = 2 。 r - t r e e 具有树高保持平衡，空间利用率高，有效减少磁盘访问次数等优点。 同时r - t r e e 也有一些不足之处，其中一点是r - t r e e 中的最小外包矩形是固定不变 的，这决定了在应用到移动对象索引时，只能用于对历史轨迹的索引。 1 ，2 ，3 ) 图2 2 空间对象m b r 及其对应r - t r e e 四叉树【8 】在1 9 7 4 年提出，其主要建立在对一个平面进行循环分解的思想之 上。首先在平面内选取一点，将平面划分为四个区域，然后在每个区域中选取一 个点再进行划分，以此类推，如图2 - 3 ( a ) 所示。这样就可以得到一棵出度为4 的 树，树的每个结点代表平面上的一个点，同时每个结点最多有4 个子节点，分别 代表四个分区，如图2 - 3 ( b ) 所示。 9 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 图2 3 平面划分及对应的四叉树 一般情况下，通过数据随机插入形成的四叉树的高度约为o ( 1 0 9 n ) ，其中 为结点的个数，对一棵四叉树的点查询最多l o g n 次比较即可，因此具有较高的 查询性能。但是对于一些特殊的数据，比如如果建立四叉树时，每次插入的结点 都落在当前四叉树最底层结点的子节点位置，则查询最坏情况下需要比较每个结 点，从而使得查询性能急剧下降。因此，为使建立的四叉树尽可能平衡，在选取 划分结点的时候，需要采取一定的优化措施。 2 3 2 移动对象数据索引相关研究 目前所提出的移动对象数据索引中，根据所支持的查询时间窗口的范围可以 分为三类：移动对象历史轨迹的索引技术、移动对象当前位置的索引技术和移动 对象未来轨迹的预测索引技术。鉴于本论文所提出的索引技术属于对历史轨迹的 索引，因此在本小节中将重点讨论移动对象历史轨迹的索引的相关技术，并对移 动对象当前位置和未来轨迹预测的索引技术作简要的阐述。 移动对象的历史轨迹随着时间变化不断延伸，如果在数据库中记录移动对象 的具体位置，则每当移动对象的位置发生变化时，都需要更新数据库，这样必然 会导致数据库的数据随着时间的变化线性增长，这是不可行的。为了减少数据库 数据库存储，人们提出了两种解决方案【l 】：( 1 ) 采样处理，对移动对象的历史轨 迹在特定时间点上进行采样存储，然后对相邻采样时间点之间轨迹采用插值( 一 般采用线性插值) 的方式进行拟合；( 2 ) 函数描述，在数据库中存储移动对象运 l o 中山大学硕士学位论文 移动对象轨迹索引技术研究与实现 动轨迹的参数信息( 比如起始位置、速度等) ，只有当移动对象的某一参数发生 变化时才对数据库提出更新要求。基于这两种方案，移动对象历史轨迹索引可以 分为三类：基于传统空间索引方式，基于多版本结构与重叠技术索引方式以及面 向移动对象轨迹查询的索引方式。 基于传统空间索引的时空索引技术一般将对空间维的索引的首要考虑因素， 而对时间维作为次要因素处理。目前主要的索引技术有r t - t r e e 3 1 ，s t r - t r e e 3 1 ， 3 dr - t r e e 9 1 。其中，r t - t r e e 使用r t r e e 作为历史轨迹所覆盖空间的存取方法，同 时使用t s b t r e e h 1 作为历史轨迹对应的有效时间区间的存取方法，r t - t r e e 对空间 维的查询提供很好的性能，但对于时间片和时间窗口的查询可能会延伸到整棵 r t - t r e e ，因此性能低下。s t r - t r e e 是对r - t r e e 的扩展，它与r - t r e e 的不同之处主要 在于插入和分割算法。3 dr t r e e 贝j j 采用了更为激进的索引策略，将移动对象的时 间维直接看做更高一维的空间维，从未将r 树扩展到三维空间，3 dr - t r e e 可以支 持空间和时间查询，但是由于时间维的延伸性，会导致m b r 的死区域不断增大， 从而严重影响时间片查询的性能。 基于多版本结构与重叠技术的索引方式主要思想是通过将时间维和空间维 分离，从而在不同的时刻上建立一棵独立的r - t r e e 。目前该类索引方法主要有 m r - t r e e 1 3 1 、h r - 仃e e 【i o 】、h r + t r e e 1 5 】和m v 3 r - t r e e i l l 】o 其中，m r - t r e e 和h r t r e e 主要思想是在每个采样时间点上都建立一棵r t r e e ，并通过在相邻的时刻只复制 位置发生变化的对象来减少在各个时刻分别存储r t r e e 的空间消耗，h l h t r e e 贝l j 是对h r t r e e 的存储策略的优化，三种方法都能有效的支持时问片查询，但对于 时间窗口的查询可能要同时查询多棵相邻的r t r e e ，因此性能较低。m v 3 r - t r e e 的主要思想是建立两棵索引树，一个m v r - t r e e 用来处理时间点查询，一个3 d r t r e e 用来处理长时间间隔查询，对于短时间间隔的查询则根据一定的优化准则 来选取m v r t r e e 或3 dr - t r e e 进行查询。总之，基于多版本结构与重叠技术的索 引方式都需要对移动对象进行重复的存储，因此需要消耗较大的空间。 与前两种索引不同，面向移动对象轨迹查询的索引方式主要考虑的是移动对 象的轨迹线。主要的索引方法有t b t r e e 3 1 ，s e t i 1 6 】和s e b 骶e 【1 7 】等，其中，t b t r e e 是一个类似r t r e e 的结构，保存了轨迹线的完整性，并且要求每个叶结点只能包 含属于同一轨迹的线段，具有良好的区域及时间片查询性能和更新效率，鉴于在 中山大学硕士学位论文 移动对象轨迹索引技术研究与实现 第六章实验的性能评估中要用到t b t r e e ，因此在下面小节中将对t b t r e e 作详细 的阐述。s e t i t r e e 基于时间维无限变化而移动对象的轨迹受限于空间范围的考 虑，将空间区域分割成互不重叠的区域，对每个区域下的轨迹线段的时间区间利 用r - t r e e 进行索引，s e b t r e e 设计思想与s e t i 类似，但具有快速的插入与查询算 法。 由于随着时间向前推移，移动对象当前位置不断更新，常规索引结构难以有 效适应这种频繁更新的动态性，同时对历史和当前位置信息建立索引具有挑战 性。这方面工作主要2 + 3r - t r e e 18 1 、2 3r 仃e e 【4 1 、l u r t r e e 19 1 、b o t t o m u pu p d a t e s 2 0 1 和h a s h i n g 2 l 】等。其中，2 + 3r t r e e 和2 3r - t r e e 的思想类似：通过两棵r - t r e e 来分 别索引移动对象的历史和当前轨迹，其中2 dr - t r e e 用来索引当前位置，而3 d 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 s 贝j j 是针对r - t r e e 提出了更 有效的更新策略；而h a s h i n g 则是基于空间划分的思想。 面向移动对象当前位置和未来位置预测的索引是m o d 数据库领域的研究热 点，预测移动对象未来运动轨迹需要存储额外信息( 比如当前速度、运动方向等) 并将移动对象运动表示为关于时间的函数( 一般用线性函数表示) ，这方面主要 工作有 p m r - q u a d t r e e 2 2 1 、t p r - t r e e 5 1 、t p r * - t r e e 2 3 1 、n s i t 2 4 1 和p s i 2 4 1 等，其中， p m r - q u a d t r e e 是基于四叉树结并引入动态属性；t p r - t r e e 主要是基于对t r e e ，它 可有效索引移动对象的当前位置并对将来某时刻位置做出预测，随后人们对其进 行各种改进，如t p r * t r e e ，s t a r - t r e e 2 5 】以及r 毋t r e e l 2 6 】等。 2 3 3t b t r e e 索引模型 t b t r e e 3 】基于r - t r e e 树，并放宽了r t r e e 对结点的一些限制，同时为了保持移 动对象轨迹的完整性而增加了一些限制。t b t r e e 中组成移动对象轨迹的线段可 表示为( i d , 乃酬，m b b ) ，其中，鼢实际线段的标识符，乃洲为移动对象轨迹的 标识符，m b b ( m i n i m u mb o u n d i n gb o x ) 为包含线段时空位置的最小，z 维区域。 t b t r e e 要求在一个叶结点中只能包含组成同一轨迹的不同线段，如果轨迹的线 段的个数超过了结点允许的最大索引项数地则轨迹线段需要保存到多个叶结点 中，为保持轨迹线段的完整性，同一轨迹的多个叶结点通过双向链表连接，如图 2 4 所示，为了表明移动对象的轨迹，图中将组成轨迹的线段加粗表示。 中山大学硕士学位论文 移动对象轨迹索引技术研究与实现 t b t r e e 的插入算法的重点在于插入过程中保持叶结点中只包含同一轨迹线 的线段。插入新线段时，首先找到轨迹的前一条线段( 即时间上满足时间终点等 于待插入线段的时间起点的线段) 所在的叶结点，如果找到并且该叶结点不满， 则直接将线段插入该叶结点，如果该叶结点已满，则需要分裂，为保持叶结点中 只包含同一轨迹线的线段的要求，t b t r e e 没有采取r t r e e 的分裂策略，而是直 接增加一个包含待插入线段的新的叶结点。 图2 - 4t b t r e e 结构1 3 1 t b t r e e 不仅支持一般的范围查询和时间片查询，还能支持基于轨迹的组合 查询，这也是t b t r e e 索引的优势所在。由于t b t r e e 的叶结点中只包含同一条 轨迹的线段以及属于相同轨迹的不同叶结点之间相互连接的特性，使得组合查询 容易进行。 2 3 4 移动对象时空查询分类 建立移动对象数据索引的首要目的是为了提高移动对象数据库的查询性能。 从时间角度讲，对移动对象的查询大致可分为对移动对象当前和未来位置的查询 和对移动对象历史位置的查询两类。第一类查询主要是在存储移动对象的当前位 置、速度以及运动方向的基础上预测移动对象在未来的位置和移动轨迹。对于第 二类查询，d p f o s e r 等人【3 】进一步划分为基于坐标的查询( c o o r d i n a t e b a s e d q u e r i e s ) 、基于轨迹的查询( t r a j e c t o r y b a s e dq u e r i e s ) 以及组合查询( c o m b i n e d q u e r i e s ) 。 基于坐标的查询包括区域查询和时间片查询。区域查询可表示为 中山大学硕士学位论文 移动对象轨迹索引技术研究与实现 q = ( 尺，乃，乃) ，其中r 为n 维的空间超立方体， 乃，捌表示查询的时间跨度，r 和 【殆，冽共同构成一个n + l 维的时空查询超立方体。时间片查询表示为驴职，乃， 其中，r 为在时刻丁的一个玎维空间超立方体。时间片查询可以看做舻乃的特 殊的区域查询。 基于轨迹的查询涉及到移动对象的自身的特性，包括拓扑查询和导航查询。 拓扑查询是对移动对象轨迹的一部分或整体的查询。拓扑查询的基本空间谓词主 要有进入( e n t e r ) 、离开( 1 e a v e ) 和穿过( c r o s s ) 等。要判断一个对象是进入、 离开还是穿过一个给定的区域，需要判断一条轨迹的多个线段。导航查询涉及移 动对象的一些动态信息( 比如移动对象的最大速度等) 。 在实际应用中，查询往往更加复杂，因此出现同时涉及到基于坐标的查询和 基于轨迹的查询的组合查询。组合查询不仅要检索出满足给定时空要求的线段， 而且还要求得到属于同一条轨迹的其他线段。比如查询“在上午8 点到9 点位于 中山大学的汽车在l o 点到1 l 点期间的运动轨迹”，首先要根据给定空间位置中 山大学和给定时间区间【8 ，9 】进行范围查询，得到满足条件的对象的轨迹的肋； 然后通过查找到在 1 0 ，11 】期间的轨迹的线段。 1 4 中山大学硕士学位论文移动对象轨迹索引技术研究与实现 第三章时间拟序和空间相平面 目前所提出的移动对象索引技术大都是在空间索引技术上的扩展，本论文中 提出的索引方法采用了与之不同的方法，并引入了一些新的概念。本章对时间拟 序和空间相平面等概念作详细的阐述，时间拟序和空间相平面是本论文提出的索 引模型的数学基础。 3 1 时序矩阵及线序划分 本节阐述线序划分及其相关的概念，线序划分为第四章提出的索引模型中的 时间索引模块提供基础。 本论文中所用的时间为数据的有效时间。有效时间是指一个对象在现实世界 中发生并保持的那段时间，即该对象在现实世界中为真的时间【2 9 】。数据u 的有效 时间期间( v a l i dt i m ep e r i o d ，i t ) 表示为v t ( u ) = v t s ( u ) ，v t e ( u ) ) ，其中z z s ( u ) 和 v t e ( u ) 为时间点，并满足胁( “) g t e ( u ) ，而 胁( 功，v t e ( u ) ) 表示r z s ( u ) 和v t e ( u ) 之 间包括z r s ( u ) 但不包括v t e ( u ) 的所有时间点集合。本论文中，所考虑的时间期间 集合记为r 。本节中，在不引起混淆的前提下，r 可同时表示数据点集合与相应 时间期间集合。 3 1 1 时序矩阵 定义3 - 1 ( 时序关系) 设r 为时间期间集合，i 上相应时序关系定义如下： ( 1 ) v u ，1 ，f ，如果z t ( u ) z r ( v ) 成立，则记甜1 ，。若1 v v y 甜) ， 则称“，互不相容； ( 2 ) v u ，v f ，其中w r ( u ) = 1 t s ( u ) ，v t e ( u ) ) ，r r ( v ) =