（计算机软件与理论专业论文）移动对象在线数据索引技术研究.pdf

哈尔滨理t 人学t 学硕f j 学位论文 移动对象在线数据索引技术研究 摘要 移动对象数据库记录了不同移动对象在每一时刻的位置信息，用户可以 在其中查询目标过去、现在与将来的信息，在智能交通与导航、地理信息、 军事等系统中有着广泛的应用前景。目前，相关领域的研究还处于起步阶 段，离实际应用有一定的差距。在这种背景之下，针对移动对象索引技术的 研究具有重要的理论意义和实用价值。 本文首先介绍了时空数据库的相关知识，主要说明了时空数据库中移动 对象的相关概念和理论，并对移动对象的索引方法进行了系统归类。在此基 础上以3 d r 树索引结构为出发点，针对其不考虑时间维的特殊性，只能处 理离线数据，而且对于那些长期保持静止的对象索引性能下降等缺点进行改 造。通过节点分裂的方法，来减少索引中长条立方体的数量，提高历史数据 的索引性能；通过将历史数据和在线数据分开索引的方法，实现对在线数据 的索引，最终形成3 d r 一树索引结构的扩展版本。最后通过数据生成器产生 的虚拟数据将扩展版本与3 d r 一树和h r 树索引结构进行比较，通过对存储 空间大小和外存访问次数两个指标的计算，证明查询效率的提高。 本文研究的主要贡献如下： 1 通过节点分裂，对历史演变周期长的时空对象人为的沿时间轴方向 进行分裂，很大程度上减少时空对象的最4 , # 1 - 接立方体体积，进而减小了时 空对象数据集的密度，提高索引效率。 2 通过树分裂，将3 d r 树索引结构改造为双树结构，即活跃树和历 史树，使其能够实现在线数据的索引功能。 3 针对改造后的3 d r 树索引结构，设计相应的插入、查询操作。 4 通过虚拟数据进行测试，证明索引性能在时间段查询有2 0 的提 高。 关键词移动对象；在线数据；节点分裂；树分裂；3 d r 树索引 哈尔滨理t 大学t 学硕f 。学位论文 r e s e a r c ho nt h ei n d e x i n gs c h e m ef o ro n l i n ed a t a o fm o v i n g o b j e c t a b s t r a c t m o v i n go b j e c t sd a t a b a s e s r e c o r d st h el o c a t i o ni n f o r m a t i o n o fd i v e r s e m o v i n go b j e c t s a l lt h et i m e u s e r sc a nq u e r yt h ep a s t ，p r e s e n t ，a n df u t u r e p o s i t i o n so fm o v i n go b j e c t si ni t m o v i n go b j e c t sd a t a b a s e sh a v eaw i d er a n g e o fa p p l i c a t i o n si n i n t e l l i g e n tt r a f f i c ，n a v i g a t i o n ，g e o g r a p h i ci n f o r m a t i o na n d m i l i t a r ys y s t e m s ，e t c a l t h o u g hm o v i n go b j e c t sd a t a b a s e sh a sg r e a tp r o s p e c to f a p p l i c a t i o n ，b u tr e s e a r c h e so ni ss t il li nt h ee a r l ys t a g e ，t h e r e f o r e ，r e s e a r c h e so n m o v i n go b j e c t si n d e xi so fp r o f o u n dt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e t h i sp a p e rs t a r t sf r o mt h er e l e v a n tk n o w l e d g eo fs p a t i o - t e m p o r a ld a t a b a s e ， m a i n l yd e s c r i b i n gc o n c e p t sa n dt h e o r i e so fm o v i n go b je c t s i ns p a t i o - t e m p o r a l d a t a b a s e a n dt h es y s t e m a t i cc l a s s i f i c a t i o no fi ti se x p l a i n e d w i t h3 d r t r e e i n d e xs t r u c t u r ea st h es t a r t i n gp o i n t ，i th a si m p r o v e di t s i m p e r f e c t i o n s ，s u c ha s i n c o n s i d e r a t eo ft h ep a r t i c u l a r i t yo ft h et i m ed i m e n s i o n ，o n l yd e a l i n gw i t ho f f l i n e d a t a ，d e c l i n i n gi n d e xp e r f o r m a n c ef o rt h o s el o n g t e r ms t a t i o n a r yo b je c t t h r o u g h t h en o d es p l i t t i n ga p p r o a c h ，s p a t i o t e m p o r a ld a t a b a s er e d u c e st h ei n d e xn u m b e r o fl o n g - c u b es oa st oi m p r o v et h ei n d e xc a p a b i l i t yo fh i s t o r i c a ld a t a a l s ob yt h e s e p a r a t ei n d e xm e t h o do fh i s t o r i c a ld a t aa n do n l i n ed a t a ，t h ei m p l e m e n t a t i o no f o n l i n ed a t ai n d e xi sa c h i e v e d t h e nan e wi n d e xs t r u c t u r ei sf o r m e d f i n a l l y ，a s e to fv i r t u a ld a t a sf r o md a t ag e n e r a t o rh a v e b e e nu s e dt ot e s tt h et r a n s f o r m a t i o n o f3 d r - t r e ei n d e xs t r u c t u r ef o rp e r f o r m a n c ea n a l y s i s ，a n df r o mb o t ht h es i z eo f t h es t o r a g es p a c ea n dt h en u m b e ro fv i s i t si n d i c a t o r s ，t h e3 d r t r e ea n dt h eh r t r e ei n d e xs t r u c t u r ea r ec o m p a r e dt op r o v i n gt h eq u e r ye f f i c i e n c y t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s ： f i r s t l y , b yu s i n gn o d es p l i t t i n g ，t h ev o l u m eo fm b ri sr e d u c e d ，a l s ot h e d e s t i n yo fd a t as e ts oa st oi m p r o v ep e r f o r m a n c eo f3 d r - t r e e s e c o n d l y , s at h e r e s u l to ft r e es p l i t t i n g ，i tc a nf o r mt w ot r e e ss t r u c t u r e ，w h i c hc a nr e a l i z et h e o n l i n ed a t ai n d e x t h i r d l y , a i m i n ga tt h en e wi n d e xs t r u c t u r e ，s o m eo p e r a t i o n s 哈尔滨理t 人学t 学硕l ：学位论文 s u c ha si n q u i r y , i n s e r t i n g ，h a v eb e e nd e s i g n e d l a s t l y , v i r t u a ld a t ag e n e r a t o rh a s b e e nu s e dt op r o v et h a tt h ep e r f o r m a n c eh a sb e e ni m p r o v e db y2 0 i np e r i o d m q m r y k e y w o r d sm o v i n go b j e c t ，o n l i n ed a t a ，n o d es p l i t t i n g ，t r e es p l i t t i n g ，3 d r t r e e i n d e x 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文移动对象在线数据索引技术 研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进行 研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己发 表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中 以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：李啊天 日期：卯7 年y 月7 日 哈尔滨理工大学硕士学位论文使用授权书 移动对象在线数据索引技术研究系本人在哈尔滨理工大学攻读硕士学 位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工大 学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨 理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论 文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影 印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密图( ( 请在以上相应方框内打v ) 作者签名： 鹰啊 剥噬辄币 。趣 1 日期： 砌7 年v - - , 9 7 日 日期刹7 年午月7 日 哈尔演理t 人学t 学硕i ：学化论文 1 1 研究目的及意义 第1 章绪论 移动对象在线数据索引技术属于时空数据库研究范畴。移动对象是指位 置不断变化的空间对象。数据库技术发展到今天，关系数据库是最成熟的，包 括我们最常使用的数据库管理系统a c c e s s ，s q ls e r v e r ，o r a c l e ，d b 2 等，但 是它们均不能对空问的和时间的数据库进行有效的管理。随着移动计算、全球 定位系统、g i s 等相关技术的发展，数据库需要存储和管理大量现实世界中带 有时空信息的物理对象，并且它们的空间位置或范围会随着时间的变化而变 化，促使时空数据库的研究受到关注。时空数据库能同时管理时间和空间特 性，它管理的是随时间变化的空白j 数据，即形状和位置随时间变化的空间对象 信息。g u t i n g | 2 】认为时空数据库的研究主要是针对移动对象的时空变化过程 进行的。 在时空数据库系统应用领域，所管理的移动对象不断向系统发送最新的位 置信息。系统需要保存大量的历史位置信息，数据量非常大，必须存放在磁盘 中。由于需要保存的数据量随着时问持续快速地增长，磁盘成为影响系统效率 的瓶颈。为获得较好的查询性能，数据库系统必须使用索引技术。传统数据库 索引技术为管理更新周期相对较长的数据而设计，用它们直接管理随时问不断 变化的移动对象位置信息会使得更新过于频繁而导致系统资源枯竭，响应速度 下降；或是更新频率小于信息变化频率，导致信息过时，系统准确率下降；同 时，对象的位置信息在二维三维空问存在着距离、方向、范围等相关属性， 传统数据库索引技术无法识别这些空间属性。时空数据库系统需要一种新的索 引技术来满足其实际应用需求。在时空数据库系统中，索引机制是保证对时空 对象进行有效存取的关键技术，已成为时空数据库研究的焦点。 1 2 国内外研究状况 要管理时间和空间数据，必须考虑以下的两个因素：数据存放问题，时空 数据库存放的不仅是当前的对象属性，还有历史的属性，这样就需要大量的磁 哈尔滨理t 人学t 学硕i j 学位论文 盘空间；实时性问题，时空数据库的数据量要远远大于一般的关系数据库，特 别是空间谓词查询的求值_ 丌销。在这种情况下若没有索引，按照存储顺序扫描 的方法来查询，则花费的时间是让人无法忍受的，而且查询所得的结果往往是 过时的。在这种需求下，移动对象的索引技术成为研究的热点，相当多的移动 对象索引方法被提了出来。 常见的空i 、日j 索引方法一般是自顶向下、逐级地划分地理空间，从而形成各 种树状空间索引结构【3 。为了实现对时空数据的快速存取，可以对已有的空间 索引方法和时态索引方法进行修改和扩展。时空数据库索引方法主要分为：轨 迹索引方法和坐标索引方法。 面向轨迹的索引方法是这样考虑的，移动对象的历史时空数据在逻辑上可 以看作是各条轨迹的集合，如果参照轨迹自身的特点对时空数据进行组织，就 可以提高移动对象的整条( 部分) 轨迹的检索效率。对于同一条轨迹的线段，不 仅要考虑线段的时空分布，还要将这些线段集中存放以提高轨迹查询的效率， 即轨迹保护阳1 。t b 树做到了严格的轨迹保护，一个叶子结点中只能存放同一条 轨迹的线段。t b 树的叶子结点也可以理解为轨迹包，采用双向链表把存放同 一轨迹的叶子结点依次连接起来，使得轨迹检索时所需的结点存取次数大幅减 少。但是轨迹的集中存放会造成结点之间的重叠区域增大，某些时空查询 ( 如：时i 、日j 段查询) 的性能会随之下降。s e t i 【9 1 采用两级索引结构分别存取空间 和时间信息。该索引将空i 日j 划分为静态不重叠的区域，如果对象从一个区域移 动到另外一个区域，则在两个区域的交界处分裂轨迹线段，并将分裂后的两条 线段分别加入到所在区域。划分后的每个区域对应多个数据页面，而页面也只 能存放该区域的轨迹线段。在此基础上，为每个区域建立一个r 树时态索引， 叶子结点的索引项是数据页面的生命周期( 数据页面包含所有线段的最小时间 间隔) 。不同的划分方法能够把同一条轨迹的线段存储在同一个区域，这样虽 然会降低索引时空分布的紧密程度，但是做到了轨迹保护。s e b 树“酬也是将空 间划分为若干个区域，但是区域之间允许重叠。为每个区域建一个s e b 树索 引，对经过该区域的移动对象的开始结束时间进行索引。该索引和s e t i 最大 的不同在于只记录移动对象在各个区域的起始时间，并将时问段转换为二维空 间中的点进行存取。s t r 树是对r 树的扩展，主要思想是同时考虑时空分布 和轨迹线段集中存放，这是部分的轨迹保护。参数p 的引入是为了平衡时空分 布和轨迹保护这两个重要特性。p 是轨迹保护时参照的层数，当插入一条新的 轨迹线段时，要保证新线段的插入位置在p 层内尽可能的接近前一条轨迹线 段。较低的参数p 会降低索引的轨迹保护，增加时空分布的紧密程度。 哈尔滨理t 人学t 学硕i j 学位论文 用坐标索引方法索引物体的位置不考虑它们的轨迹，把空间运动的物体简 化为点，忽略其空间形状。在这方面的研究比较早，其中主要有r 树1 系列和 q u a d t r e e 2 | 系列，由于基于q u a d t r e e 的方法比较少，我们主要讨论基于r t r e e 的方法。 在基于r t r e e 的时空索引方法中，由于时空对象的查询可能是跟时空对象 的位置布局相关的，因此可以将该类索引方法分为索引过去、索引现在，索引 现在与将来三类。r t - t r e e 驯和3 d r 树引，h r t r e e 5 。，h r + - t r e e 引，m v 3 r t r e e “7 1 是索引过去对象位置的索引结构。r t - t r e e 是在r t r e e 的基础上加入了两个时间 项，表示最小边界矩形的有效时间。3 d r 树的主要思想是把时间加入到空间维 中，查询时不对时i 、日j 和空间进行区分，它的优点有两个：( 1 ) 索引机制基于统一 的结构，只有一个空间数据结构需要执行和维护：( 2 ) 对时空操作的效率较高 ( 如比较耗费时间的空间连接操作) 。h r t r e e 的基本结构是建立在r t r e e 基础上 的，它在每一个时间点建立一个r t r e e ，过一段时间如果节点内的对象位置发 生变化则生成一个新的节点，没有变化则使用原来的节点，然后在新节点基础 上建立一个当前时间r t r e e 。如果经过一段时间，某个节点内的物体一直均未 移动，那么它将被好几个r t r e e 所共享。 t p r ( t i m ep a r a m e t e r i z e dr t r e e ) 树”8 1 是最近提出的一种可以索引物体未来位 置的方法。它的叶子节点形式如下( 一维) ：( o i d ，x a r 4 ) ，v a ，其中，o i d 代表 物体的代号，z 是在时间，的坐标，h 是在时间锄的速度。它使用公式 x ( o 爿+ v p 吲来计算物体未来的位置。与r t r e e 的最小边界矩形( m b r ) 相 似，t p r t r e e 采用了一个“保守 边界矩形( c o n s e r v a t i v eb o u n d i n g r e c t a n g l e s ) ，它的下限是由矩形所包含的物体最小速度来决定，上限由矩形包 含的物体最大速度来决定。由于随着时间的推移，边界矩形会越来越大，它采 取了如下策略：如果其中一个物体更新，那么这个物体所在节点到根的路径 上，所有边界矩形均要更新。t p r t r e e 虽然支持对未来的查询，但它是一种非 常粗略的预测方式，对运动规律相对固定的物体预测有一定的参考价值，对于 没有运动规律或者运动规律经常改变的物体的预测参考价值不大。由于t p r t r e e 使用了动态的v b r ( 速度边界矩形) ，其更新删除的代价很大。为了提高其 算法效率，在t p r t r e e 基础上有人提出了t p r - t r e e ”圳，它的基本结构与t p r t r e e 大致相同，仅仅是对索引算法作了改进。为了克服t p r t r e e 查询未来太粗 糙的缺点，在文献中提出了一种速度限制索引结构v c i 【2 ，它的主要思想是在 每个节点中加入一个最大速度项，记录在节点中所有对象的最大速度，如人的 最大行走速度、汽车的最大时速。在这样一个约束条件下，一定的时间内就可 哈尔滨理t 人学t 学硕i j 学 t 论文 以计算出节点m b r 的最大值，从而可以对查询的窗口进行限制。 目前国外主要有p u r d u e 大学的p l a c e “( p e r v a s i v el o c a t i o n a w a r e c o m p u t i n ge n v i r o n m e n t s ) 项目组，欧洲研究者训练委员会资助的c h o r o c h r o n o s 项目组以及西欧多个大学组织的t i m e c e n t e r 项目组等其他数据库项目组对 时空数据库技术的发展做了大量工作。国内有中国人民大学的数据库实验室， 香港城市大学的时空数据库实验室以及华中科技大学的数据库研究组等大学教 研室对时空数据库进行了广泛地研究，并提出了一些有创新的想法。 p l a c e 在个人定位系统，无线通讯技术以及信息科技环境下为用户提供 有效的基于位置的服务，是一个可扩展的基于位置的数据库服务器。服务器使 用逐层演化技术来响应并发连续时空查询，主要有以下特征：( 1 ) 可扩展性， p l a c e 服务器使用共享执行算法，根据连续时空查询的数量来实现可扩展 性；( 2 ) 逐层演化，服务器使用正负元组，连续更新对查询结果有影响的用户信 息实现逐层演化机制；( 3 ) 新的操作符，服务器使用一组新的时空操作符( 如 i n s i d e ，k n n ) 来支持连续查询。 c h o r o c h r o n o s 【2 2 1 项目组研究s t d b m s 的设计和实现，主要包括下面的工 作：( 1 ) 空间和时间的结构以及表示；( 2 ) s t d m b s 的建模以及语言；( 3 ) 时空信 息的图形化界面；( 4 ) 时空数据库的查询处理；( 5 ) 时空数据库的存储结构以及 索引技术；( 6 ) d b m s 的架构。 t i m e c e n t e r 研究室关注数据库领域内的最新技术研究，在时空数据库 索引技术方面颇有成绩，提出了时间参数r t r e e 以及其他能有效管理历史、 当前和未来位置信息的索引结构。 1 3 研究内容 本课题将从索引结构设计、算法设计与优化，性能分析等方面对移动对象 在线数据索引技术进行深入研究，同时将扩展后的索引方案与同类的索引方案 进行比较，来体现应用价值。因此本课题研究的内容主要包括： 1 针对时空数据库理论进行概述，着重强调移动对象的属性特征，对时 空数据库的体系结构、时空对象表达、时空数据建模、时空数据索引、时空数 据查询等各个研究方向的研究现状和最新进展做简要说明。着重总结索引移动 对象的各种方法，并对它们进行比较详细的归类，找出一个或多个比较典型的 模型进行介绍。 哈尔滨理t 人学t 学硕i j 学化论文 2 以3 d r 树将时问看作一维，并与两个空间维共同构成三维的时空索引 方案为模型，根据其存储空i 日j 较低、时间间隔查询效率较高而时间片查询性能 较低的特征，提出扩展的3 d r 树索引模型，扩展索引在线数据的功能，设计 操作算法，并从时间效率和空间效率两个方面对性能进行分析。 1 4 本文的结构 本文主要针对移动对象的索引结构、查询方法以及性能进行深入研究，并 提出一种基于3 d r 树的索引结构实现对于在线数据的索引。移动对象数据库 在很多方面与空间数据库、时态数据库有着相同的特性。研究人员针对其提出 的索引模型都基于这两种数据库索引技术。我们将在第二章讨论移动对象的相 关知识，经典的索引结构。根据现有的移动对象索引特征，进行详细归类对 比。第三章将针对3 d r 树存在的问题提出扩展的索引结构，使之具备缩小数 据密度和索引在线数据的特性。第四章详细说明我们提出的索引结构的性能， 进行结构优化，并阐述其算法和操作实现方法。第五章通过虚拟数据对扩展的 3 d r 树的进行测试，并完成横向的性能分析及比较。 哈尔滨理t 人学t 学硕i j 学位论文 2 1 引言 第2 章时空数据库技术基础 在数据库管理系统中，针对数据库管理系统中存储数据的提取和访问称为 数据库检索或数据库查询。数据查询和数据检索是数据库最常用的功能之一。 根据其应用领域的不同，数据库的查询可以有多种形式。查询优化和求解的有 效性很大程度上取决于数据在物理上是如何存储的。数据库索引技术是研究数 据库文件在物理存储设备上的组织和存储方式，它属于数据库物理设计部分， 可以用于加速很多查询。事实上，为底层关系选择好的索引能加速每一个查 询。常用的数据库索引技术包括两大类：基于树的索引技术和基于哈希的索引 技术。本文中重点介绍的是前者。 2 2 时空数据库概述 时空数据库( s p a t i o ， 在二十世纪八十年代末开t e m p o r a l d a t a b a s e s t d b ) 始受到人们的重视。时空数据库是时态数据库( t e m p o r a l d a t a b a s e s ，t d b ) 与空 间数据库( s p “o d a t a b a s e s ，s d b ) 的统一体，即包括时间与空间要素，主要用 于存储与管理位置或形状随时间而变化的各类空问对象。时空数据库的研究内 容相当丰富，主要涉及时空对象表达、时空数据建模、时空数据索引、时空数 据查询、时空数据库体系结构等，同时时空数据库原型系统、时空推理、时空 查询代价模型等也为时空数据库的研究带来了一定的挑战。高云君3 等综述了 时空数据库方面的研究。 时空数据库主要是针对移动对象的时空信息进行分析处理，目前的研究热 点是时空对象表达、时空数据建模、时空数据库体系结构、时空数据查询和时 空数据索引等几个方面。 时空数据库的应用非常广泛，根据时空应用所处理数据类型的不同，将时 空数据库应用主要归纳为如下三类： 1 处理时空对象的应用，如导航系统。 2 涉及到空间对象定位的应用，对象的特征与位置可能随时间而变化， 但却不移动，如在土地信息系统中，土地随形状的变化而改变位置。 哈尔滨胖t 人学t 学硕f j 学位论文 3 结合上述两种情况的应用，如在生态环境应用中，污染既作为一个移 动现象而被测量，同时它的特性和形状又随时间而变化。 在以往的研究中，空间数据库和时态数据库作为各自独立的领域进行研 究。空间数据库的研究集中于如何对数据库中的几何对象建模和查询处理。研 究者们提出了用转换、重叠、裁减和分层处理等存取访问机制对多维几何对象 ( 如点、线、面和立方体) 进行存取访问。但在这些过程中，却没有考虑到时间 的因素。时态数据库则在保留当前现实世界状态的同时，还记录了对象的历史 信息。在时态数据库中有两种时间概念，即事务时问和有效时间。事务时间是 指当某个对象状态记录进入数据库的时间，而有效时间是指该对象状态在现实 世界中变为有效的实际时间。时态访问方法都没有特别考虑所访问对象的空间 属性。一个时态数据库系统至少应该支持两种时间概念中的一种。按照对时间 概念的支持程度划分，可将时态数据库分为事务时间数据库，有效时| 白j 数据库 和双时态数据库。 时态数据库和空间数据库是数据库研究的两个重要方向。随着对两个领域 研究的深入和成熟，二者的结合也就是必然的事情。许多应用如地理信息系统 ( 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 s ，g i s ) 【2 引，多媒体技术和环境信息系统等都需 要管理随时间变化的空问对象，这些都对时空数据库的深入研究提出了要求。 y a n n i st h e o d o r i d i s 等人将时空数据库定义为：时空数据库是一个包 含了时态数据，空间数据和时空数据【2 引，并能同时处理数据对象时间和空间属 性的数据库。 根据对象空间特征的不同，可以将时空数据库的应用分为三类： 1 应用中仅涉及到对象的运动例如对于一个交通监控系统来说，它只对 车辆运行情况，即车辆的位置关系感兴趣，而不关注车辆的形状，也就是说， 此类应用主要处理对象的位置随时间变化的情况。 2 应用中主要涉及到对象本身形态的变化例如在地籍管理中，土地的面 积随时间发生的变化；在g i s 系统中，河流、道路随时问发生的变化等。 3 应用中既涉及到对象的运动，又涉及到对象本身形态的变化这是最复 杂的一类情况。例如在环境信息系统中对风暴移动过程的描述，不仅涉及到风 暴的运动情况，而且其形态、密度等的不断变化也在考虑范围内。 哈尔演理t 人学t 学硕i ：学位论文 2 3 移动对象的相关知识 2 3 1 移动对象的分类 时空数据库中通常管理着两类空间对象，一类是静态的空间对象，另一类 则是移动对象。 移动对象有狭义和广义之分。狭义的移动对象是指对象的位置属性随时间 不断的发生改变，也就是指运动的对象，如车辆、飞机、轮船、洪水、飓风 等。广义的移动对象是指含有不断变化的属性的对象，不特指对象的运动。也 就是说，静止的对象如果含有不断变化的属性，也可以用移动对象的方法进行 管理。例如，房间的温度随着时间而发生变化这一现象，房间为静止对象，而 温度为静止对象不断变化的属性。本文的研究主要是针对狭义的移动对象而 一i 口o 按照对象的运动速率分，狭义移动对象可以进一步分为连续变化的移动对 象和离散变化的移动对象。高变化率的移动对象( 例如汽车、轮船、飞机等) 称 为连续变化的移动对象。低变化率的移动对象( nt h 办公室里的人) 称为离散变 化的移动对象1 2 引。本文的研究主要是针对离散变化的移动对象。 2 3 2 移动对象数据的空间属性 移动对象数据具有空间数据的特点，不同的是空间数据是静止的，而移动 对象数据是不断变化的。在移动对象数据中含有空间坐标信息，用来表示移动 对象的空间位置情况。移动对象的空间属性具有以下特点： 1 不可排序性对于多维空间中的移动对象数据来说，无法建立一个可以 反映它们相互之问邻近性的排序。 2 相关性个移动对象可能是点( 例如汽车) 或区域( 例如洪水) ，一个刀 维的移动对象至少在其中的一维上覆盖一个区间，而且一个时空数据库的数据 量通常是很庞大的，这使得在时空数据库中的移动对象之间有可能相互重叠， 也就是移动对象之间可能存在一定的相关性。 3 数据复杂性在现实世界中，移动对象的空f b j 分布是不均匀的，大小也 可以是多种多样的，所以移动对象在计算机中的表示比较复杂。由于移动对象 不断的运动，对其空间位置的判断也就相对复杂。总的来说，移动对象数据与 哈尔滨理t 人学t 学硕l j 学位论文 单纯的空间数据或单纯的时念数据相比要复杂的多。 2 3 3 移动对象的轨迹 定义2 1 移动对象的轨迹轨迹是对移动对象运动路线的描述，表示移动 对象空间位置的连续变化。 为了记录移动对象的运动，我们应随时都知道移动对象的位置，但是由于 目前的定位技术和无线通信技术的不完善，局限了我们对其的了解。例如：我 们只能在具有固定时间i 日j 隔的采样点上才可以得到相应的位置信息，而对于两 个采样点之间的位置信息却无法获得。为了改变这一局限，获得对象完整的运 动轨迹，必须进行插值。目前有线性插值和多项式曲线插值等方法。 1 线性内插和外推法陀7 1 按顺序用直线依次连接两个采样点，即可得到一 系列连接的线段，用这些线段表示移动对象的运动轨迹。通常，在表示移动对 象过去轨迹时，采用两个连续采样点i 日j 线性内插的方法；在表示移动对象将来 轨迹时，利用移动对象当前的位置和速度信息，通过线性外推的方法计算出移 动对象将来的位置。 2 曲线内插和外推法这种方法的基本思想同线性内插和外推法的思想相 近，不同之处是这种方法用一系列曲线段来表示移动对象的运动轨迹，通过减 少轨迹更新点和轨迹段的数目来提高查询性能。 2 4 移动对象的索引方法归类 移动对象索引模型性能主要由下面三个因素来决定： 1 结构大小由于时空数掘库内的数据量随着时间成指数级增长，如何减 少对象的重复存储是压缩存储空间的关键。目前使用多版本技术的索引模型所 占空间很大，但查询性能很好，如何在空间和查询性能之间找到最佳平衡参数 还需要做大量的工作。 2 历史信息查询效率历史信息的查询效率和索引模型如何管理信息的方 法相关，同时也和模型主要为何种查询类型优化有关。目前提出的可以管理历 史信息的索引模型主要分为两种：一种优化历史窗口查询，忽略线段所属的对 象；一种优化轨迹查询，忽略线段之间的空间位置相关性。实际应用需要同时 响应这两种查询，目前还没有能同时优化这两种查询的索引结构。 3 未来信息预测准确性未来位置信息预测的准确性，不仅与查询结构正 确率相关，和索引结构更新性能也有着很大的影响。准确率高的预测可大大减 哈尔演理t 大! 学t 学硕l j 学位论文 少索引结构更新次数，提高整体性能。目前最好的预测方法为线性化技术，它 也是最简单的方法。实际应用中，移动对象的运动模式在很短的时间段内是非 常随意的，使用线性化技术在移动对象频繁报告其最新位置的环境下性能很 差。数理统计，神经网络学习等复杂预测方法的引入使得准确率提高很多，但 由于算法需要大量的计算，大大消减了结构性能。如何平衡预测准确率和复杂 度，找到合适的方法也将是下一步研究的重点。 近几年不同的索引观点不断地被提出来，但是到现在为止由于还几乎没有 被商用化，现在提出的各种方法大部分还限制于理论阶段。对于时空数据库而 言，每种索引结构均有其优点和缺点，它们只是对某种特殊的情况和查询有比 较好的性能。对于静态的空间索引和查询，r t r e e 已经做到商用化，并且有比 较好的性能。但是对于动态移动对象的索引，我们必须结合多种索引结构才能 实现相对比较全面的查询和索引功能。多种索引结构的结合是时空数据库系统 实际设计的主要趋势，选择哪几种索引结构以及如何把它们有机地结合起来将 是系统设计所面临的主要难题。在这种需求下，移动对象的索引技术成为研究 的热点，相当多的移动对象索引方法被提了出来。如表2 1 给出了当前移动对 象索引研究的主要类别。 表2 - 1 索引移动对象归类表 t a b l e2 1 c l a s s e so fm o v i n go b j e c t si n d e x 轨迹索引坐标索弓 构造限制索引 限制轨迹索引索引现在和过去索引 网络限制索引 索引过去现在的轨迹 非限制轨迹索引 索引现在和将米索引 索引现侄将来的轨迹 2 4 1 轨迹索引 1 有限制的轨迹索引限制轨迹索引可以分为网络限制索引和构造 ( i n f r a s t r u c t u r e ) 【2 9 1 限制索引。前者主要针对的是道路上面的移动对象，如汽 车、火车等；后者针对的是陆地上的各种移动对象在实际运动中要受到的各种 限制，如湖泊、停车场等情况下的索引结构。 ( 1 ) 网络限制索引在陆地上运动的物体有相当大的一部分是有固定运动轨 迹的，这主要包括汽车、火车等各种车辆，它们的运动主要是沿着固定的道 路，人们查询它们的位置常常关心的不是其绝对物理位置，如经纬度坐标，而 是更关心它们的相对位置，如距离哪个车站比较近，大概在哪个大楼附近，在 哈尔滨删t 人学t 学硕l j 学位论文 哪个公路的多少公罩处等。对于索引可以把二维的平面坐标简化为一维的坐 标，比较常见的转换方法有z 曲线和h i l b e r t 曲线。它的优点是索引方便，可 以利用已有的索引结构，如b 树、哈希结构等，同时也可以对空间对象进行排 序。但是这样也存在一定的问题，无论现在使用最多的z 曲线还是h i l b e r t 旧0 】曲 线，它们均不可能完全反映空间的相邻状况，也就是说在实际空间中相邻物体 的物理存储位置是不相邻的，这样对于空i 旬邻居查询带来很大的开销。 这方面的研究主要有一些，其主要思想是将多维的道路转换为一维的对象 来存储，这样就可以利用现有的数据库管理系统，实现起来比较容易。 ( 2 ) 构造限制索引由于在现实世界中对象的移动要受到各种各样的限制， 如大的湖泊、巨大的建筑物，这样我们就可以把对象不可能到达的范围去掉来 减少查询的范围，提高查询的效率。对于这种情况索引的结构可以不作改变， 但对其一般的查询算法要进行相应的改进。提出了一个三步查询方法：1 ) 对原 始的查询窗口进行分割处理，把一个大的窗口分成几个小的窗口集合，分割的 依据是查询窗口中的构造物。2 ) 对第1 ) 步产生的小窗口集合进行查询，将查找 的结果作为下一步的查询对象。3 ) 在所有的结果中找出要查询的对象。如图2 1 中所示，外侧矩形为查询窗口，内部的黑色矩形为障碍物，为了减小查询的 矩形范围，把外侧的大矩形分为若干个小矩形，如图内的白色小矩形。按照上 面提到的三步查询方法，先分割查询窗口，就是上面提到的白色小矩形，然后 在每个白色小矩形中进行查询，返回一系列的查询结果，最后在查询结果集合 中查找满足条件的对象。我们会发现，虽然这种分割的方法会影响查询区域的 个数，使得查询区域个数出现成倍的增加，但是整体的查询面积却在大幅度缩 小，因此，对索引的整体效率影响不大。 图2 - 1 查询窗口的分割 f i g 2 1s p l i t i n go fq u e r i n gw i n d o w 哈尔滨理t 大学t 学硕i ? 学位论文 2 没有限制的轨迹索引( 1 ) 索引过去和现在的轨迹在这方面的研究主要 有s e t i 索引、s e b t r e e ( s t a r t e n d t i m es t a m pb t r e e ) 、x b rt r e e s ( s t r u c t u r e s o b e y i n gt h ee m b e d - d i n gs p a c eh i e r a r c h y ) ( x b rt r e e 是基于q u a d 树的结构) 、 t b - t r e e ( t r a j e c t o r y b u n d l et r e e ) 和s t r - t r e e ( s p a t i o t e m p o r a l r - t r e e ) 。如图2 2 所 示，t b t r e e 是一种基于r 树的索引结构。 图2 2t b t r e e 结构 f i g 2 2 t b t r e es t r u c t u r e c 6 在其叶子节点中存放对象的轨迹簇，节点的结构为( i d 号，轨迹号， m b b ，方向) 。由于最小边界矩形把同一个轨迹分成了很多字段，同一字段的 物体对象存放在相同的叶子节点中，为了有效地索引同一个对象的轨迹，把同 一个轨迹的节点用双向链表链接起来。这种方法有一个缺点就是在空间位置相 邻但是不在同一个轨迹的物体不能存放在同一个节点中；这种方法的优点是保 持了对象的轨迹特性，对于查询同一物体的轨迹非常方便。 另外有学者提出了一种与t b t r e e 相似索引结构，它的最大特点是抛弃了 r 树家族一直使用的m b b ，即最小边界矩形。它使用了八边形的最小边界方 法1 3 ，这样做的优点是提高查询的准确性，八边形的形状随着在其中的对象位 置作适当的调整，最大限度地减小包含的面积、减少了重叠，查询的次数也就 随之减少。还提出了一个三步的过滤查询2 1 步骤，即过滤( f i l t e r i n g ) 、求精 f r e f i n e m e n t ) 、跟踪( t r a c i n g ) 。 ( 2 ) 索引现在将来的轨迹f t - q u a d t r e e ( f u t u r et r a j e c t o r yq u a d t r e e ) 是最近提 出的一种索引结构，它可以索引将来的轨迹。它使用的是q u a d t r e e 索引结 构，最大的特点是使用了轨迹共享技术来最大限度地减少数据的存储数量，提 哈尔滨理- r j ( 学t 学硕l j 学位论文 高索引的更新效率。在这种树中的叶子节点结构表示为( o i d ，轨迹的数量，起 始坐标，结束坐标，起始时间，结束时间，其他信息) 。对于在同一时间内的 节点而言，如果它们的坐标位置相同或者接近，那么就可以采取共享策略，把 若干个节点的内容放入一个公共的节点内，这样就可以明显地减少存储的空 间。如图2 3 所示，左边是原始的q u a d t r e e ，最下面的节点内有五个相同轨迹 段，从x 1 x 5 的轨迹在同一时间内基本相同：右边的是f t - q u a d t r e e ，是对左 边结构的改进，采用共享轨迹技术使节点数大大减少。这样做的优点是减少了 存储的开销，简化了索引的结构，同时也减少了节点的更新操作等丌销。 x l x 2 | x 3 乡尹l 等；l x 4 x 5 图2 - 3 节点的变换 f i g 2 3e x c h a n g i n go fn o d e 时空数据库是时间和空间要素相结合而构成的数据库，时间维的存在极大 地丰富了数据库的内容。它一方面增加了数据库管理的复杂性，另一方面，海 量的数据为时间和空间数据分析提供了极为广阔的舞台。时空数据库的索引机 制是支持时空数据快速存取的关键技术，当前的时空数据库索引方法大致可以 分为对历史数据、当前位置和未来位置的索引。 2 4 2 坐标索引 用坐标索引方法索引物体的位置不考虑它们的轨迹，把空间运动的物体简 化为点，忽略其空间形状。在这方面的研究比较早，其中主要有r 树系列和 q u a d t r e e 系列，由于基于q u a d t r e e 的方法比较少，我们主要讨论基于r t r e e 的方法。根据索引移动对象信息的不同，可以将这些索引结构分为二类：对移 哈尔滨理t 人学t 学硕卜学位论义 动对象历史信息和当日i 信息的索引、对移动对象当前信息和未来信息的索引。 1 索引过去和现在r t - t r e e 和3 d r 树，3 d r 树，h r t r e e ，h r + t r e e ， m v 3 r t r e e 是索引过去对象位置的索引结构。 r t - t r e e 是在r t r e e 的基础上加