（计算机应用技术专业论文）空间移动对象的轨迹和查询研究.pdf

哈尔滨理t 大学t 学硕l ：学位论文 空间移动对象的轨迹和查询研究 摘要 空间移动对象的轨迹和查询是移动对象数据库中的关键技术，成为当前 数据库领域研究的热点问题。本文重点研究了非约束环境和网络环境中移动 对象轨迹的查询问题。 在建立移动轨迹索引结构之前，首先应该对移动对象的轨迹进行建模。 本文研究了移动对象轨迹问题，介绍了在移动对象数据库中轨迹模型表达的 两种方法：线性插值模型和曲线函数模型。由于数据库中表达的轨迹与真实 轨迹有一些偏差，所以本文阐述了轨迹时空上的不确定性及轨迹不确定查 询，对各种移动对象轨迹的更新策略进行了分析比较。 在非约束环境中，移动对象的轨迹涉及过去、现在和将来查询。在进行 过去轨迹查询时，分析已有的历史轨迹索引结构s t r 树的不足之处，及改 进的索引结构t b 树和t b 树，改进后的索引结构具有更好的保留轨迹的优 点。在进行将来查询时，分析了t p r 树、条带索引和f t 四叉树。目 前，能够同时支持过去、现在和将来的移动对象轨迹查询的索引结构还比 较少，源自q + r 树的启发，提出一个基于t b 树和f t 四叉树的混合树索引 结构r t + q t 树，提出一个基于t b 树和f t 四叉树的r t + q t 树。 在实际应用中，移动对象一般在网络环境中移动。本文详细论述了网络 中移动对象轨迹的索引和查询方法。由于网络移动空间和无约束移动空间的 不同，对网络及网络中的对象轨迹进行了新的建模。针对已有索引结构的不 足之处，在原索引结构基础上，提出了基于固定网格的移动对象运动轨迹索 引模型m o n * 树，此结构能够实现对移动对象当前实时位置信息的索引， 保证了在有效查询对象完整的历史网络轨迹的同时，增强了系统的更新的能 力。 关键词移动对象；轨迹建模；轨迹查询和索引；网络轨迹 哈尔滨理工人学t 学硕一i ：学位论文 r e s e a r c ho nt r a j e c t o r ya n dq u e r y o fs p a t i a lm o v i n go b je c t a b s t r a c t t h et r a je c t o r ya n dq u e r yo fs p a t i a lm o v i n go b je c ta r ek e yt e c h n i q u ei n m o v i n go b je c td a t a b a s e t h em a n a g e m e n to fm o v i n go b j e c t sh a sb e e ni n t e n s i v e l y s t u d i e di nr e c e n ty e a r s i nt h i sp a p e r ，w ef o c u so nt h eq u e r yo fm o v i n go b j e c t t r a je c t o r i e si nu n c o n s t r a i n e de n v i r o n m e n ta n di nn e t w o r k b e f o r ee s t a b l i s h i n gi n d e xs t r u c t u r eo fm o v i n go b je c tt r a je c t o r y , w es h o u l d s e tu pm o d e lo fm o v i n go b j e c tt r a j e c t o r y t h ei s s u eo fm o v i n go b j e c tt r a j e c t o r yi s r e s e a r c h e di nt h i sp a p e r t w oe x p r e s s i o n so fm o v i n go b je c tt r a je c t o r y a r e l i n e a r i t yi n s e r tm o d e la n dc u r v ef u n c t i o nm o d e l t h e r ea r es o m ew a r p st ot r a j e c t o r y m o d e la n da c t u a lt r a j e c t o r yi nt h ed a t a b a s e s ot h es p a t i o t e m p o r a li n c e r t i t u d e a n dd u b i o u st r a j e c t o r yq u e r ya r es e tf o r t h t h eu p d a t es t r a t e g i e so fd i v e r s i f i e d m o v i n go b je c tt r a je c t o r i e sa r ea n a l y s e da n dc o m p a r e d t h ep a p e ra n a l y s e st h ed i s a d v a n t a g e sa b o u ta ni n d e xm e t h o db a s e do ns t r t r e ew h i c hi n d e xt h ep a s tt r a j e c t o r i e s t bt r e ea n dt b t r e es h o w si t sa d v a n t a g e s i nh o l d i n gf u l lt r a je c t o r y t p rt r e e ，b a ri n d e xa n df tq u a r et r e ea r ed i s c u s s e di n t h ef u t u r eq u e r y t h ei n d e xm e t h o dt h a tc a ns u p p o r tp a s t ，c u r r e n ta n df u t u r e t r a je c t o r i e ss i m u l t a n e i t ya to n et i m ei sf e w , d r a w i n gi n s p i r a t i o nf r o mt h es u c c e s s o fq + rt r e e ，i n d e xm e t h o d sr t + q tt r e ea n dr t 。+ q t8 x ep r e s e n t e d i nm a n ya p p l i c a t i o n s ，m o v e m e n ti sm o d e l e dt oo c c u ri nn e t w o r kr a t h e rt h a n i t su n c o n s t r a i n e de n v i r o n m e n t w ed e v e l o pn o v e lm o d e l sf o rn e t w o r ka n di t s o b je c tt r a je c t o r i e sd u et ot h ed i f f e r e n c e sb e t w e e nu n c o n s t r a i n e dm o v e m e n ta n d c o n s t r a i n e dm o v e m e n t a i ma tt h es h o r t a g eo ft h ei n d e x e st h a th a d b e np r e t e n t e d ， an o v e lm o v i n go b j e c tm o t i o nt r a j e c t o t i e sm o d e lm o n * - t r e et h a tb a s ef i x n e t w o r ki sd e v e l o p e d t h i ss t r u c t u r ec a ni n d e xt h er e a lt i m ep o s i t i o ni n f o r m a t i o n o fm o v i n go b j e c t t h i ss t r u c t u r ec a ni m p r o v et h eu p d a t ea b i l i t yo ft h es y s t e ma n d s t o r et h ec o m p l e t et r a je c t o t i e so ft h em o v i n go b je c t si nn e t w o r k k e y w o r d sm o v i n go b j e c t ，t r a j e c t o r ym o d e l i n g ，q u e r ya n di n d e xo ft r a j e c t o r y , t r a je c t o r yi nn e t w o r k 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文空间移动对象的轨迹和查询研 究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行研究 工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己发表或撰 写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以明确方 式注明。本声明的法律结果将完全由本人承担。 作者签名：氮b 当日期：么，谬年多月厂口日 哈尔滨理工大学硕士学位论文使用授权书 空间移动对象的轨迹和查询研究系本人在哈尔滨理工大学攻读硕士学位 期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大学所 有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨理工大 学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文和电子 版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、缩印或 其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密日。 ( 请在以上相应方框内打4 ) 作者签名：贝蒸缶驾 导师签名：善钐季 日期：秘霜年多月o 日 日期：d 矿年多 月，2 ，日 哈尔滨理t 人学t 学硕上学位论文 1 1 课题背景 第1 章绪论 本课题来源于黑龙江省自然科学基金( f 2 0 0 6 0 1 ) 。 随着无线通信技术以及全球定位技术的发展，管理空间移动对象动态信 息成为可能，这使移动对象轨迹的查询和管理的研究得到了广泛关注【1 l 。 时态数据库和空间数据库作为现代数据库的两个分支，都已经发展得比 较成熟，也出现了支持时态和空间数据库的数据库管理系统。随着数据库技 术的发展，用户也提出了越来越高的要求。结合空间和时间的时空数据库， 日益成为当前研究的热点。在过去的十年里，移动计算得到了迅速发展，并 给信息产业带来了一场深刻的革命。移动对象( 如车辆，飞机，移动用户 等) 【2 1 是移动计算下的运行主体，因而如何实现对移动对象的有效管理便成 为了这一领域的研究热点，即移动对象数据库技术。移动对象数据库是时空 数据库的特殊化，它主要针对离散的和连续变化的空间和时间信息。 传统的数据库能有效的管理移动对象的非时空属性，有效处理移动 对象非时空属性的查询。移动对象的移动属性是动态的，即移动对象的 位置随着时间连续变化，在变化过程中不像静态属性那样明显更新数据 库。因此，在移动对象数据库的服务器的设计中，移动对象轨迹模型的 建立、对象轨迹的存储更新以及这些轨迹的查询等问题是非常重要的。 空间移动对象轨迹及查询技术在许多领域展现出了广阔的应用前 景，可用于智能交通管理、军事指挥系统、货物运输管理及消防现场作 业等。在军事上，对象轨迹查询技术可以回答常规数据库无法回答的问 题；在民用领域，利用轨迹查询技术可以实现智能运输系统，出租车警 员自动派遣系统以及高智能的物流配送系统。此外，移动对象轨迹查询 技术还在电子商务领域有着广泛的应用。因此，空间移动对象轨迹和查 询研究具有十分重要的意义。 1 2 本课题在国内外的研究现状 从九十年代后期开始，各国研究机构就纷纷展开对移动对象数据库的研 究，并获得了许多有价值的研究成果。移动对象数据库技术是一项新兴技 术。空间移动对象轨迹和查询是移动对象数据库的关键部分，在国际和国 内，该领域的研究均处于起步阶段。 1 哈尔滨理丁火学t 学硕j ：学位论文 实际上，有几个移动对象系统和几种移动对象轨迹模型已经提了出来， 然而，近期对这些系统和模型的研究，显示出对移动对象轨迹表达部分不够 真实，对查询求值的准确性、索引方法中的轨迹更新性能、轨迹空间的表达 以及轨迹查询代价等问题也缺乏统一的研究。在国外，早期的大多数研究基 于一种假设：即在每一时刻，可以获得移动对象轨迹的准确信息。然而，由 于有限的网络带宽和服务器中数据库的更新性能，数据库中的轨迹信息不可 能连续更新，所以在实际应用中不能保证这种假设成立，轨迹信息与潜在的 不确定性相联系。因此，后来不采用连续记录任何时刻对象的轨迹，而是采 用如下方法 3 , 4 1 ： 1 记录一些离散的点； 2 记录对象在运动过程中的运动轨迹函数。通过运用对象的运动参数 和位置函数来表示对象的运动。 目前采用前者的方法比较多，但是得到的数据只是离散的点，而不是真 实的运动轨迹。所以，第二种方法目前引起人们的广泛关注。 最具代表性的移动对象数据模型是：e r w i g mm 与w o l f s o no 。e r w i g m 从三维角度( 二维空间+ 一维时间) 来观察移动对象( m p o i n t ) 和移动区域 ( m r e g i o n ) 。该模型可与关系、面向对象或其它d b m s 数据类型相兼容，但 没有考虑高维模型。w o f s o no 的研究主要是指出动态属性的概念，即属性 值是随时间连续变化的，并且提出f t l ( f u t u r et e m p o r al o g i c ，简称f t l 语 言) 和m o s t ( m o v i n go b j e c ts p a t i o t e m p o r a l ，简称m o s t ) 模型。这些数据 模型的研究都是从某一角度来表示移动对象，主要查询移动对象现在和过去 的轨迹信息，而没研究将来轨迹的查询。另外，s i s t l a 和t a y e b 提出的移动 对象模型对轨迹语义的表示也不够完整。 在相关系统的应用开发方面，许多研究机构已经开发出了一些实用系 统。如新加坡c o m f o r ts e r v i c e 中心基于g p s 的出租车自动派遣系统、i b m 公司、r a n kx e r o x 公司、s e a r s 公司的技术服务人员派遣及实时数据采集系 统等。在国内，空间移动对象轨迹和查询研究刚刚起步。从2 0 0 1 年初开 始，国内的研究小组展开了对移动对象数据库系统的研究，并且设计开发了 一个初步的移动对象数据库原型系统。该原型系统包括移动对象管理子系 统、移动对象索引子系统、位置更新子系统、地图生成及管理子系统以及查 询管理子系统。这些子系统中就有移动对象轨迹和查询的研究，这一原型系 统为科学的研究各种移动对象模型和算法奠定了基础。但大多系统尚处于研 究开发的实验阶段，对象轨迹也采用多段线表示。缺乏一定的真实性，使得 查询求值具有不确定性，功能也不完善，需要进一步扩充。 2 哈尔滨理工人学t 学硕上学位论文 对当前的空间移动对象轨迹模型和其查询方法的调查表明，这些系统模 型有四个主要不足之处： 1 不能很准确的表达移动对象真实的轨迹； 2 轨迹的查询求值不够准确； 3 移动对象轨迹的更新代价高； 4 移动对象轨迹空间表达不够全面。 对于一种满足需求的移动对象轨迹表达及其查询技术来说，我们当然希 望它能够具有一些良好的特点，比如： 1 真实准确的表达移动对象的轨迹； 2 能够准确进行各种类型的查询； 3 较高的轨迹更新效率； 4 轨迹的查询和索引方法可以方便地应用到各种移动环境中。 1 3 本课题研究拟采取的方法 1 阅读资料首先阅读研究与课题相关的论文资料和专业文献，关注有 关的国际会议，学术交流，认真分析之后对课题大概有一个初步了解。 2 注意积累、分析总结本课题所涉及的知识面很宽，每个知识点的方 法也很多，要有重点地去分析研究。在获悉目前国内外在空间移动对象轨迹 和查询研究这方面的进展以及所采取的技术和方法之后，对各种实现模型和 算法在功能、性能、通用性等方面进行分析比较，分析各种模型和算法的优 缺点。在掌握现有技术的基础之上归纳总结。对所采用的算法进行分析改 进，提出自己的观点。采用插值法和函数表示法建立有效的移动对象轨迹模 型，描述移动对象轨迹的动态特征，建立有效的移动对象轨迹模型。 3 理论联系实际在理论研究的基础上和现实中的应用相联系，使理论 能够推动应用实践，在一定条件下，对对象模型和算法进行实验。重点考虑 索引方法的更新代价和查询效率。 1 4 本课题的难点 1 移动对象轨迹的表示和建模为了对移动对象的轨迹进行行之有效的 管理，移动对象数据库系统必须能够准确的获取轨迹的过去、当前和将来信 息，并建立有效的轨迹管理模型，本文将采用离散点插值和轨迹函数相结合 的方法，以便完成对象轨迹过去、当前和将来查询。 2 移动对象轨迹的索引技术以往大多数的轨迹的索引技术只能对过去 或当前或将来实现索引，而未能在一个索引中同时实现对过去、现在和将来 1 哈尔滨理丁人学t 学硕一i ：学位论文 轨迹的索引，本文结合已有的索引技术，致力于结合三者为一体的实现。另 外，对象实时位置的信息对索引更新也是非常重要的，目前比较常用的索引 还不具有这一功能。 3 移动对象轨迹查询处理移动对象轨迹的查询处理是在所提出的索引 结构的基础上进行查询，完成移动对象的过去、当前和将来轨迹的查询，给 出移动对象轨迹的范围查询、连续查询和拓扑查询等查询类型的实现方法。 4 实验分析比较通过移动对象产生器模拟移动对象的运动轨迹，利用 编写的基于索引结构的更新和查询算法，将新的索引结构与其它索引结构在 空间利用率、轨迹查询性能和索引结构的更新代价等方面进行分析比较。 1 5 本文概要 本论文主要讨论了空间移动对象的轨迹和查询的问题。全文共分为四 章，内容结构安排如下： 第一章是绪论部分，主要介绍了本论文选题背景、本课题在国内外研究 现状、课题研究拟采取的方法及本课题的难点要点。 第二章研究了移动对象的轨迹问题，包括轨迹的建模、存储和更新等问 题。 第三章详细研究了移动对象过去、现在和将来轨迹的索引及查询。 第四章基于实际应用，介绍了道路网络环境中移动对象轨迹的索引及查 询。 本文最后是结论部分，总结了本课题主要的研究工作，指出不足以及今 后需要进一步研究的问题和方向。 哈尔滨理t 大学t 学硕上学位论文 第2 章移动对象的轨迹模型 2 1 移动对象的轨迹模型 随着g p s 及无线通信技术的发展，目的，对于配备了g p s 设备的移动 对象，如行人、汽车、飞机等，可以随时查询它们的空间位置。但是，如果 要查询移动对象在过去某一时刻或将来某一时刻的位置，则必需要求能恢复 对象过去的运动轨迹，或预测对象将来的运动轨迹。为了满足这些查询需 求，最直观的方法是保存对象在过去每一时刻的位置信息，但是移动对象的 数量巨大，保存所有移动对象每一时刻的位置信息，其开销是不能接受的。 因此，我们必须建立合适的轨迹模型，使它既能保持对象的轨迹信息，又能 适合系统软硬件的现实状况。另外，移动对象的运动空间有高低维之分，如 汽车在一个二维的平面上运动，飞机在三维的空间里运动，因此对移动对象 的建模也有高低维之分。 2 1 1 线性插值模型 线性插值方法是目前采用最多的轨迹建模方法，其主要的思想是：每隔 一个固定的时间对移动对象进行采样，保存该时刻对象的位置和速度信息， 最后在得到的采样点之间进行线形的插值，从而得到完整的运动轨迹。线性 插值方法简单易行，且能够建模低维和高维模型。 线形插值方法首先要采样移动对象的位置信息，在某一时间点，移动对 象的属性主要包括对象的唯一标识符、位置、速度、时间等，我们做如下定 义： 定义2 1 ( 移动对象) 移动对象m o ( m o v i n go b j e c t ) 是一个四元组： m o = o i d ，pt ，0 其中，o l d 表示唯一标识符，p 表示位置，v 表示速度，表示时间。 定义2 2 ( 移动对象轨迹)移动对象轨迹m o t ( m o v i n go b j e c t t r a j e c t o r y ) 由一系列的采样点组成： m o t = ( m l ，m 2 ，m 3 ，m 0 其中m = 阳i d ，p ，v ，力， n 表示采样点的个数。 不同的移动对象其运动的空间维数是不一样的，如汽车在二维的平面上 运动，飞机在三维的空间中运动。对于在一维空间中运动的对象，采样得到 气 哈尔滨理1 二人学t 学硕l ：学位论文 的信息可以表示为向i d ，p ，v ，0 。对于在二维空间里运动的对象，采样得 到的信息可以表示为阳i d ，d x ，硝，以，蚶，0 ，其中，觑，硝分别表示 对象在x 坐标和y 坐标的位置，几，v v 7 分别表示对象在x 坐标和y 坐标的 速度向量。我们采用结合时间维的方法，将时间信息看作空间的另一维，结 合坐标信息来共同表示对象的位置。一维、二维移动对象的采样轨迹分别如 图2 1 、图2 ：2 所示。图2 1 中，折线的各个转折点代表了采样点，在采样 点之间采用线形插值的方法进行连接，便得到完整的轨迹，折线在x 轴上的 投射即为对象在一维空间里的实际运动轨迹。同样，图2 2 中的折线也表示 了对象的模拟轨迹，其在平面上的投射( 即粗虚线) 表示对象实际在二维空 间里的轨迹【5 1 。 得到对象在过去时间罩的模拟轨迹后，就可以根据轨迹得到过去任意时 刻的对象位置，或任意时刻间对象的轨迹。以图2 2 为例来举例说明，如要 查找对象在f 时刻的位置，t l f 一。三是任意垂直平面，可以得到点位置的三维体，这些点 是关于彳7 在任意p 丁狮上的所有点。结果是以么7 伍，y ，t 9 为中心，为轴 的旋转椭圆体。因此，椭圆体等式为： 掣+ 掣- t 一骘! ：j( 2 3 ) r r 6 为得到所有关于给定轨迹乃的p t u r 的界限，在乃上的每一点应用等 式( 2 3 ) 。结果是旋转椭圆体的“扫描”，其中心是沿着乃上的点，轴分别是 ，、，、占。上面的三维体称为已知轨迹乃的不确定体积v u ( u n c e r t a i n t y v o l u m e ) 。 图2 5 说明以上概念。虚线椭圆体以轨迹上的点伍，y ，f 为中心，其 中伍7 ，y 是移动对象在时刻f7 的期望位置，点a ( x ，y ，0 是可能的三维点， 它是沿着p t u r ( 用虚多段线表示) 上的一点。 哈尔滨理t 人学工学硕l 学位论文 图2 5 不确定轨迹及不确定体积 f i g 2 5u n c e r t a i nt r a j e c t o r ya n dv o l u m e 下面介绍移动对象不确定查询的两类操作，点查询和范围查询： 1 点查询的两种操作 w h e r ef l t ( t r a j e c t o r yt r ，t i m e 力一返回时间，对象在轨迹乃或路线上的 位置。 w h e nf i t ( t r a j e c t o r yt r ，l o c a t i o n0 一返回对象在轨迹乃上期望位置的 时间。 2 时空范围查询 这部分的重点是不确定性对时空范围查询的影响。此操作语义与语法定 义为：给定己知轨迹的不确定参数，返回移动对象轨迹在某二维区域某时间 段轨迹的可能值。 乃是移动对象的轨迹，r 是以多边形包围的二维区域，有意义的结果是 对象在时间间隔口，可是否有时或总是在区域尺内，在时态域中对应“存 在”和“一般”两个量词。因此，对应有两个操作：s o m e t i m el n s i d e 向i d ，r ， f ，纠和a l w a y si n s i d e 佃i d ，r ，f j ，纠。显然，具有不确定性的模型在输 出操作中产生可能值。如果将二维区域尺和时间间隔p j 歹幻7 结合，则成为 三维表达的棱柱，此棱柱以位于水平面t = t j 的r 为底，高度是t 2 一f ，。v p r 表示此棱柱约束的三维体，称为查询棱柱。表示如下定义的三维体： = 阿r 、v p r 。图2 - 6 说明了这些概念。 图2 - 6 不确定体积和杏询柱体的相交 f i g 2 6t h ei n t e r s e c t i o no fu n c e r t a i n t yv o l u m ea n de n q u i r i e sc y l i n d e r 1 l - 哈尔滨理t 人学工学硕 ：学位论文 已知查询的时间范围是p ，纠，使y ，2 表示y u 的子集，v u 被以 伍，y ，圳和阢，如，纠为中心的椭球体包围，其中伍，y 和( x 2 ，y 2 ) 分别 是移动对象在f l 和t 2 时刻的期望位置。同样，使，2 = 呦，2 r 、v p r 。 2 3 移动对象轨迹的更新策略 移动对象的位置随着时间连续变化，需要不断地进行更新 1 1 , 1 2 , 1 3 1 ，离散 的的更新策略可以分为如下几类： 1 固定时间间隔更新策略将一对连续更新之间的时间间隔定义为“报告 间隔”。每一移动对象以某种方式具有固定的报告间隔x ，每x 时间单元向 服务器发送一条时空记录。除了第一条时空记录外，每一时空记录包括有效 的不确定值，即每一移动对象使用与服务器相同的方法( 相同的数学等式) 估 计它当前的位置，并且每一时间单元测量估计位置和真实位置之间的偏移 ( 欧几里得距离) 。将最大偏移作为不确定值写到下一条时空记录中。报告位 置p 。的不确定值表示连接尸和尸，曲线段的最大偏移。 2 简单的绝对估计更新策略每一移动对象具有最新报告的时空记录和 以某种方式选择的固定极限砌。每一时间单元移动对象同数据库服务器一 样估计它的当前数据库位置，并且测量数据库中的位置和真实位置之间的偏 移。当当前位置与对应数据库中位置的偏移砌超过砌时，将具有不确定值 砌的时空记录发送到数据库服务器。因此，报告位置尸，的不确定值表示连 接p f _ ，和p ，曲线段的最大偏移。 2 4 本章小结 本章重点研究了移动对象轨迹问题，介绍了在移动对象数据库中规迹表 达的两种方法：插值法和函数表达法。由于数据库中表达的轨迹与真实轨迹 有一些偏差，所以本章阐述了轨迹的时空上的不确定性及轨迹的不确定查 询，对各种移动对象轨迹的更新策略进行分析比较。 哈尔滨理工人学工学硕l ：学位论文 第3 章移动对象轨迹查询的研究 3 1 轨迹索引方法简介 目前的主流移动对象索引方法如下： 1 对偶转换它是基于对偶转换的，即原空间的一条线段对应转换空间 的一点【1 4 j 。其索引空间是线性的或二次分布的，且移动对象的速度固定。 2 r 树及其变形现在大多数处理移动对象信息的索引结构都是以r 树 为基础的，有效处理移动对象轨迹各种类型查询。其中主要有：s t r 树 ( s p a t i o t e m p o r a lr t r e e ) ”1 、t p r 树( t i m ep a r a m e t e r i z e dr t r e e ) 1 6 , 1 7 、t p r * 树 【1 8 ，1 9 1 、l u r 树( l a z yu p d a t e dr t r e e ) 1 2 0 , 2 1 1 等。 3 四叉树及其变形此方法能有效索引高维数据。主要有p m r 四叉树 1 2 2 、x b r 四叉树【2 3 1 等。 4 网格文件及其变形此方法处理静态一致分布式数据很有用1 2 4 1 。 5 混合索引结构移动对象各种索引方法各有优缺点，多种索引方法结 合可取长补短。例如，q + r 树是由r 树和四叉树组成的混合树结构【2 5 1 。 3 2 查询移动对象过去轨迹 3 2 1 移动对象轨迹建模 在高维空间中，移动对象轨迹记录移动对象穿越时间的位置，是结合空 间和时间信息的多段线。高维空间轨迹可以映射n - - 维空间。图3 1 ( a ) 是在 二维空间与一维时间里建模对象轨迹，采样点是线段的终点。 a ) ( 2 + 1 ) 维空间 a ) ( 2 + 1 ) d i m e n s i o n a ls p a c e b ) m b b 近似表示轨迹 b 、m bba p p r o x i m a t e l y s h o w st r a j e c t o r y 图3 1 轨迹 f i g 3 - 1t r a j e c t o r y 1 3 3 c ) 线段在m b b 中的映射 c ) m b bl i n em a p p i n g 哈尔滨理t 人学t 学硕l ：学位论文 虽然实际上大多数对象的运动不是线性的，但是采用线性模型经常是合 理的，这是因为：1 避免了任意移动类型的复杂化，允许分析许多典型的时 空问题。否则，这些问题都是很难处理的；2 分片的线段可以近似任何曲 线。 3 2 2r 树索引轨迹存在的问题 r 树【2 6 1 是空间数据库中最流行的索引结构之一，目前已成为许多空间索 引方法的基础，有必要详细地介绍r 树的数据结构。r 树是一棵高度平衡 树，其插入算法基于最小外包矩形( 简称m b r ) 的最小扩张准则，即以 m b r 递归地对数据集空间按照面积规则进行划分，删除过程与插入过程相 反。r 树的非叶子节点中的每条索引记录为( i ，子节点指针) ，i 是空间上 包含其子节点中矩形的最d , 夕t - 包矩形；叶子节点上的每条索引记录为( i ， 元组标识符) ，i 是最小外包矩形，在空间上包含了所指元组表达的k 维数 据对象，这时也称为最小边界盒( 简称m b b ) 。每个节点对应一个磁盘页 面，r 树的平面划分与数据结构如图3 1 所示。当检索r 树时，首先判断哪 些节点中的矩形区域与检索窗口( 比如范围查询) 重叠，再进一步判断窗口 内矩形区域中有哪些是被检索的对象。由于允许m b r 之间重叠，在每一层 索引可能有多个节点与检索窗口重叠。、 移动对象的位置随时间连续变化，需要不断地更新索引结构，只是简单 地应用r 树存在许多问题【2 7 1 ，可以归纳为四方面： 1 重新调整r 树的整个索引结构是不可避免的。例如，在图3 2 中， p 加从一个叶子节点移动到另一个叶子节点，导致了所到达叶子节点的分 裂，使p ，的移动一直传播到根节点。 图3 - 2r 树的平面划分与数据结构 f i g 3 - 2t h ep l a n ed i v i s i o na n dd a t as t r u c t u r eo fr t r e e 2 在用m b b 近似表示轨迹线段时，会产生大量的“死空间”，如图3 1 ( b ) 所示。显然，与轨迹对应的m b b 覆盖了一大部分空间，然而轨迹所占 茂l 孺引 沁层一 芝嘣 f暂磷型 哈尔滨理_ 人学t 学硕l ：学位论文 据的实际空间却很小，造成存储空间的浪费，产生无效的遍历。 3 由于空间移动对象千姿百态，其索引空间经常重叠，并且重叠的程度 随着对象的数量和空间维数的增加而剧增。 4 r 树不能用来索引移动对象的轨迹，因为它不能确定每条线段具体属 于哪一条轨迹。 3 2 3s t r 树索引过去轨迹 由于r 树不能索引移动对象的轨迹，对r 树进行修改。图3 1 ( c ) 中， m b b 中的线段只有四种存在方式。通将叶子项的形式修改为( 谢，m b b ，方 位) ，方位的取值域为 j ，2 ，3 ，4 ) 。假设轨迹的标号从d 到n ，那么叶子 节点的形式可以为( i d ，# t r a j e c t o r y ，m b b ，方位) ，其中# t r a j e c t o r y 是轨迹标 识。这种改进实施起来比较简单，也能在r 树索引移动对象轨迹线段时提 高效率，但在处理查询时仍存在问题，因此提出了索引轨迹的s t r 树。 s t r 树的插入操作不仅考虑对象的空间接近程度，而且考虑轨迹保存问 题，即将属于同一轨迹的线段尽可能保存在一起。 s t r 树是r 树的扩展( 在r 树基础上适当修改) ，有效支持移动对象轨 迹的查询处理。这两种的方法区别是插入和删除方法的不同【1 5 i 。 3 2 3 1s t r 树的改进方法一s t r 树利用新的插入删除策略定位轨迹，同时 也没有太大影响索引的空间区别能力。r 树假设是所有插入的几何对象是独 立的，这表明所有的线段是独立的。s t r 树是基于r 树的存取方法。然 而，r 树和s t r 树只是隐含“线段是轨迹的一部分”。s t r 树对于时间片查 询有很好的性能，但对于像轨迹查询这样的复杂查询类型还不能很好的处 理，因此在s t r 树的基础上进行改进。改进树的目标是严格保存轨迹，结 果是叶子节点只包含属于同一轨迹的线段，因此将索引理解为轨迹束 ( t r a j e c t o r yb u n d l e ) ，此索引结构称为t b 树。只有在放弃r 树的一些重要性 质时，比如节点重叠和空间区别能力，这种索引才是可行的。t b 树缺点是 空间上接近轨迹但独立于轨迹的线段存储在不同的节点中。由于重叠程度增 加，空间区别能力降低，因此传统的范围查询代价增加。然而，放弃了空间 区别能力却达到轨迹保留的目的。下面将看到，这种属性在求值时空查询时 是很重要的。 1 插入过程目标是将移动对象的轨迹切成许多段，每一段包括m 条线 段，m 是扇出，即每一叶子节点包括m 条轨迹片段。图3 3 说明了插入过 程，整个过程的重要阶段是图中的标号。 哈尔滨理t 大学t 学硕l ：学位论文 图3 3t b 树的插入 f i g 3 - 3t h ei n s e r t i o no ft bt r e e 在插入算法中，当插入新项时，必须找到新项所属轨迹所在的叶子节 点。遍历树时，从根节点开始，进入与新线段m b b 相交的每一叶子节点， 选择包括与新项相连接的段的叶子节点( 图3 3 中第一阶段) 。f i d e n o d e 算法 总结了与s t r 树相同的搜索段的过程。如果叶子节点己满，需要执行分裂 算法。叶子节点的分裂将影响完全保留轨迹的原则。因此，替代方法是创 建一个新的叶子节点。例如，在图3 3 中，向上一步步寻找未满的非叶子节 点( 阶段2 到阶段4 ) 。选择最右边路径( 阶段5 ) 来插入新的节点。父节点中 ( 阶段5 ) 如果有空间，则插入新的叶子节点。如果父节点己满，通过在非叶 子节点第一层( n o n l e a f l e v e l ) 上创建一个新节点来分裂父节点，新创建的节 点有一个新的叶子节点作为唯一子孙，必要时向上传播分裂。t b 树的增长 从左到右，即插入时首先是最左边的，最后是最右边的。 2 轨迹保留t b 树的每一叶子节点包括部分轨迹，即轨迹分布在不相连 接的叶子节点中。在讨论查询处理时会发现，基于轨迹标识符检索段是必要 的。一个简单的解决办法是通过有层次的数据结构连接叶子节点。使用双链 表按照时间顺序把包含相同轨迹部分的叶子节点连接起来，这样达到轨迹保 留的目的。为说明这种方法，图3 4 给出t b 树索引结构的一部分和一条轨 迹。为清楚起见，将轨迹表示成带子而不是线。以灰带表示的轨迹穿越六个 节点，它们是c ，c 2 等。在t b 树中，这些叶子节点通过链表连接。 当访问任意叶子节点时，链表的存在使检索代价最小，叶子节点的扇出 厂是指包括在叶子节点中部分轨迹的大小为厂。假设仑3 ，根据前面定义，伊 刀条线段是双连接的，一条是前连接，一条是后连接。要找到同一轨迹剩下 的段，必须根据链表前后指针进行查找。 哈尔滨理丁人学t 学硕l ：学位论文 图3 4t b 树的索引结构图3 5 组合查询 f i g 3 4t h ei n d e xs t r u c t u r e so ft bt r e ef i g 3 5c o m b i n a t i o nq u e r y 3 查询处理新的查询类型：由于时空数据的特殊属性，一些新的查询 类型也越来越重要。所谓基于轨迹的查询可分为拓扑查询和航行查询，拓扑 查询涉及对象运动的所有信息，航行查询涉及如速度和航向的导出信息。 拓扑查询：涉及对象的所有或部分轨迹，通过检查多段轨迹可以确定对 象是否进入、穿越或绕过己知区域。比如，如果最早段的开始点( 对应地， 最新段的结束点) 在已知区域之外，那么对象在已知时间范围“进入”了区 域。对于离开、穿越以及绕过等谓词有相同的定义。 动态信息和航行查询：动念信息没有明确存储，必须从轨迹信息中导 出。对象的平均或最大速度由某时间穿越距离的比例决定，对象的航向由两 个特定点所确定的矢量决定。根据这些定义，对象的属性是唯一的，但是依 赖于时间间隔。比如，在前十分钟对象的航向是正东，但是若考虑前一小 时，航向则是东北。速度也是如此。涉及速度和航向的查询在现实生活应用 中非常重要。例如，查询飞机的速度是多少，最大速度是多少。前者考虑时 间范围内的现在时刻，而后者是较长时间的聚合。但是，为计算结果，必须 检查属于同一轨迹的一组线段。 组合查询：时空查询的重要问题是抽取有关轨迹的信息，必须经过两 步：( a ) 选择轨迹；( b ) 选择需要返回的一部分轨迹。轨迹选择可能发生在以 下四种情况：( i ) 查询轨迹标识符；( i i ) 利用时空范围选择轨迹片段；( i i i ) 拓 扑查询；( i v ) 利用导出信息查询。例如一个组合查询的例子是：“查询今天 七点到八点之间移动对象离丌图森一小时之后的轨迹”。这个查询使用时间 范围“在图森今天七点到八点之间”来确定对象轨迹，“在下一小时”给出时间 范围确定要检索的部分轨迹。图3 5 说明这个原理，点线立方体表示选择轨 哈尔滨理t 大学丁学硕l 学位论文 迹的时空范围，多段线代表移动对象的选择轨迹，多段线的黑体部分表示返 回的部分轨迹( 比如，在下一个小时) 。根据这个原理，可以在时空应用环境 中构造各种合理的查询组合。 查询算法：下面设计两种不同的查询算法。一种是关于r 树和s t r 树 的组合查询算法，另一种是关于t b 树的算法。t b 树的查询算法是不同 的，因为使用链表的数据结构来检索部分轨迹。 r 树和s t r 树的组合查询算法：处理组合查询的第一步是在时空范围 的基础上检索一组原始段，方法是利用r 树和s t r 树中的范围搜索方法。 在图3 - 6 中，使用立方体c ，搜索树，结果是轨迹f ，的两段( 标注为l 和2 ) 以 及轨迹，2 的四段( 标注为3 至6 ) ，包围在立方体c ，中的六段以灰色所示。第 二步是选取部分轨迹。从找到的段出发，寻找与之相连的段，首先在同一叶、 子节点中寻找，其次是其它叶子节点。考虑轨迹f ，的段l ，则找到两段，一 段是前连接，另一段是后连接。可能在同一叶子节点中找到这些段，也可能 在不同的叶子节点中找到。当到达叶子节点时，算法检查一条段是否以某种 方式与正在检查的段相连。使用这种递归方法，可以检索越来越多的轨迹 段，继续算法直到新找到的段在立方体旬范围之外。 图3 - 6 组合查询阶段 f i g 3 - 6t h es t a g eo fc o m b i n a t i o nq u e r y 下面给出了组合查询算法，需要注意的问题只能检索同一轨迹一次。起 初的范围查询检索到轨迹，的段1 和段2 ，将两段都作为出发点将检索同一 轨迹两次。为避免这种情况，当第一次检索到轨迹时，则存储轨迹标识 ( t r a j e c t a r y # ) ，在检索轨迹之前，首先检查是否已经被检索过。在所指出的 范例中，如果首先使用段1 检索了部分轨迹f ，并存储这部分信息，那么就 省略使用段2 再检索这部分轨迹。r 树与s t r 树的基于轨迹的组合查询算 法如下。 算法3 1r 树与s t r 树的基于轨迹的组合查询算法： 输入：组合查询范围r a n g e l 和r a n g e 2 输出：满足查询条件的部分轨迹 1 8 哈尔滨理t 火学工学硕一i ：学位论文 a l g o r i t h mc o m b i n e d s e a r c h ( n ， 幸为树的根节点，r a n g e l 与 b e g i n ( 1 ) i f ni sn o tl e a ft h e n r a n g e l ，r a n g e 2 ) r a n g e 2 是组合查询范围 ( 2 ) f o re a c he i n n d o ( 3 ) i f i n t e r s e c t ( m b b ，r a n g e1 ) t h e n ( 4 ) i n v o k ec o m b i n e d s e a r c h ( n ， ( 5 ) e l s e ( 6 ) r e t u m0 ； ( 7 ) e n di f ( 8 ) e n df o r ( 9 ) e l s e 奎不是叶子节点木 枣对于中的每一项e * * e7 的m b b 与r a n g e l 相交木 d ；宰是e7 所指的孩子节点宰 宰没有与r a n g e l 相交的轨迹木 f 1 0 ) f o r e a c he ，i n n d o幸对于中所有的项幸 ( 1 1 )i f ( i n