（控制理论与控制工程专业论文）面向港口调度管理的时空数据库索引技术研究.pdf

u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：刘利早 日期：2 - 0 f o 年弓月，日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 醯授予学位后即可口在授予学位1 2 个月后口解密 后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：刘剁罕 日期：2 0 ，d 年；月，日 导师( 签字) ：铀 a 啦 o 年；月，日 一 - u 哈尔滨t 程大学硕十学伶论文 摘要 随着全球经济的发展，世界水运量迅速增长，大量船舶频繁来往于各大 港口，给调度管理工作带来了一定的问题，如港口服务质量不高，海损事故 增多，事故救助效率低下等。因此信息化管理是港口现代化建设与发展的必 然趋势。时空数据库技术是计算机科学的新兴领域，用于处理海量的具有时 态和空间属性的数据。当前，国内外对时空数据库技术的研究应用到工程上 的实例还比较少，将时空数据库相关技术应用到港口调度管理是港口信息化 建设的需求，也是将时空数据库技术理论应用到工程的实践。 论文首先针对在港作业的船舶与拖轮构成的系统，考虑了船舶作业过程 相互间影响的基本条件及参数，对时空数据生成仿真算法进行了相应的改进 及设计，实现了调度过程的船舶运动时空数据生成算法。 随后，论文提出了一种信息分离混合索引( i s h i ) 算法用于索引作业船舶相 关的时空信息。该算法主要由哈希表，改进的四叉树森林及t p r * t r e e 三部 分构成，分别用于索引作业船舶的静态信息、动态历史时空信息、当前及未 来时空信息。在改进的四叉树森林中，每棵树索引一个时间段上的动态历史 时空信息。同一个作业船舶连续时刻信息使用双向链表进行链接，实现了不 同时刻信息的快速过渡。对于提出的i s h i 算法，研究了各部分索引及数据 的存储机制，针对信息记录类型设计了等长及变长的数据存储方案。 最后设计并实现了港口船舶管理时空可视化系统，该系统是一个基于位 置服务应用的以电子海图为平台的应用系统，用于港口调度管理。 关键词：港口调度管理；时空数据库索引；改进的四叉树；t p r * - t r e e 哈尔滨下程大学硕十学何论文 a bs t r a c t w i t ht h ed e v e l o p m e n to fg l o b a le c o n o m y , t h es h i p p i n gi n d u s t r yi sd e v e l o p i n g r a p i d l y ag r e a tl o to fs h i p sf r e q u e n t l yw o r kb e t w e e nt h el a r g en u m b e ro fm a j o r p o r t sw h i c hh a st a k e ns o m ep r o b l e m st ot h em a n a g e m e n to ft h ep o r ts c h e d u l i n g ， s u c ha sl o ws e r v i c eq u a l i t yo fp o r t s ，m a r i t i m et r a f f i ca c c i d e n t si n c r e a s i n g ，l o w e f f i c i e n c yo fr e s c u ei n c i d e n t s ，a n ds oo n t h et r e n do ft h ep o r tm o d e m c o n s r u c t i o n a n dd e v e l o p m e n ti si n f o r m a t i o n - b a s e dm a n a g e m e n t s p a t i o t e m p o r a ld a t a b a s e ( s t d b ) i san e wf i e l di nc o m p u t e rs c i e n c ei no r d e rt od e a lw i t hl a r g en u m b e r so f d a t aw i t ht i m ea n ds p a c ea t t r i b u t e s n o wt h e r ea r eo n l yaf e wa p p l i c a t i o n sh a s c o m b i n e dw i t hs t d bt h e o r yi nt h ew o r l d c o m b i n i n gs t d ba n dt h em a n a g e m e n t o ft h ep o r ts c h e d u l i n gi st h er e q u i r e m e n to ft h ep o r tm o d e mc o n s t r u c t i n ga n da n e wp r a c t i c eo fs t d bf r o mt h et h e o r yt ot h ea p p l i c a t i o n f i r s t l y , a m ia tt h es y s t e mo ft h ew o r k i n gs h i pa n dt u g si nt h ep o r t ，t h i st h e s i s i m p r o v e st h es p a t i o - t e m p o r a ld a t a s e t sg e n e r a t i n ga l g o r i t h mb yc o n s i d e r i n gb a s i c c o n d i t i o n sa n da f f e c t i o n sb e t w e e nw o r k i n gs h i p sa n dr e a l i z e st h es p a t i o - t e m p o r a l d a t ag e n e r a t i n ga l g o r i t h mo ft h em o v i n gs h i p sa tt h ep o r t s e c o n d l y , t h i st h e s i sp r o p o s e sa ni n d e xa l g o r i t h mc a l l e di n f o r m a t i o ns e p a r a t e f o rh y b r i di n d e x i n gt od e a lw i t hs p a t i o t e m p o r a li n f o r m a t i o no fw o r k i n gs h i p s t h ea l g o r i t h mi s c o m p o s e db yh a s ht a b l e ，i m p r o v e dq u a d t r e e f o r e s ta n d t p r * - t r e e h a s ht a b l ei su s e dt od e a lw i t hs t a t i ci n f o r m a t i o n e a c hi m p r o v e d q u a d t r e ei su s e dt om a n a g ed y n a m i ci n f o r m a t i o nw i t hh i s t o r i c a lt i m ei n t e r v a l t p r * - t r e ei su s e dt ot r e a tw i t hd y n a m i ci n f o r m a t i o nw i t hc u r r e n ta n df u t u r et i m e a t t r i b u t e t h ec o n t i n u o u ss h i ps p a t i o t e m p o r a li n f o r m a t i o ni sl i n k e db yd o u b l e l i n k e dl i s tb e t w e e nn o d e so ft r e e s ，s oi tc a ns h i f tq u i c k l yb e t w e e nd i f f e r e n t t i m e s t a m p s t ot h ei s h ia l g o r i t h m ，t h ep a p e ra l s od e s i g n sf i x e da n dv a r i a t i o n a l d a t as e g m e n t sm e m o r ym e t h o db yt h ei n f o r m a t i o nt y p et ot h ei n d e xa n dt h ed a t a a tt h el a s t ，t h i st h e s i sd e s i g n sa n da c c o m p l i s h e sas y s t e mo fv i s u a l i z a t i o nt o t h es h i p so ns p a t i o t e m p o r a lt ot h ep o r t t h es y s t e mi sa na p p l i c a t i o no fl b s 一 l 产 哈尔滨t 程大学硕十学何论文 b a s e do i le c d i sa n di su s e dt ot h em a n a g e m e n to ft h ep o r ts c h e d u l i n g k e yw o r d s ：t h em a n a g e m e n to ft h ep o r ts c h e d u l i n g ；s t d b ；i n d e x ；i m p r o v e d q u a d t r e e ；t p r * - t r e e 哈尔滨t 程大学硕十学位论文 目录 第1 章绪论1 1 1 选题背景、目的和意义1 1 2 国内外研究现状2 1 2 1 港口调度管理国内外发展现状2 1 2 2 时空数据库技术研究现状”2 1 3 课题的主要研究内容3 第2 章时空索引技术分析5 2 1 时空索引技术概述5 2 1 1 索引过去”6 2 1 2 索引当前9 2 1 3 索引未来9 2 2 空间索引结构r t r e e 及r 宰t r e e 1 0 2 3 时空索引结构t p r t r e e 1 2 2 4 空间索引结构q u a d t r e e 及其改进结构1 9 2 5 本章小结2 l 第3 章港口调度管理时空索引算法设计2 2 3 1 船舶调度过程时空数据集仿真算法- 2 2 3 1 1 船舶入出港运动数学模型2 2 3 1 2 时空数据集生成算法设计2 3 3 1 3 数据生成算法仿真结果2 9 3 2 信息分离混合索引i s h i 结构3 0 3 3 港口调度管理i s h i 算法3 6 3 3 1 静态信息索引算法3 6 3 3 2 动态信息索引算法3 7 3 4 算法性能分析“4 1 3 4 1 插入操作代价4 1 3 4 2 查询操作代价4 2 哈尔滨t 稃大学硕+ 学何论文 3 5 本章小结”4 3 第4 章港口调度管理时空数据物理存储机制研究4 4 4 1 时空数据文件类型4 4 4 2 数据文件的存储机制4 5 4 3 索引文件存储机制4 6 4 4 本章小结5 0 第5 章港口船舶管理时空可视化系统设计与实现5 1 5 1 系统工作模式及设计目标51 5 2 目标系统可视化表示设计5 3 5 3 电子海图显示模块设计与实现5 5 5 3 1 电子海图显示模块设计5 5 5 3 2 电子海图显示模块实现5 8 5 4 网络通信模块设计与实现6 1 5 4 1 网络通信协议分析6 1 5 4 2 通信模块应用协议设计6 2 5 4 3 通信模块的实现- 6 3 5 5 可视化原型系统应用6 5 5 6 本章小结6 7 结 仑“6 8 参考文献7 0 攻读硕士学位期间发表的论文和取得的科研成果7 4 致谢7 5 ， 哈尔滨t 程大学硕十学位论文 第1 章绪论 1 1 选题背景、目的和意义 随着全球经济一体化和信息技术的发展，水运在世界经济运行中的地位 日益突出【l 】。传统意义上港口代表水陆交通枢纽，而现代港口远超越了其传 统意义，成为了连接世界范围的生产、交换、分配和消费的中心环节以及支 持世界经济发展、国际贸易发展的国际流通体系的重要组成部分。 当前，一个港口的信息化管理程度表明港口的现代化建设以及发展水平。 信息技术巧妙结合、综合运用，对未来港口的发展和走向市场化能起到至关 重要的作用，不但可以改善港口服务质量、提高港口生产率、优化港口资源 配置，还可以为港口生产提供更为可靠的安全保障【2 】。因而，管理现代化、 信息化已经成为港口发展的重要指标之一。随着全球经济一体化与信息技术 的发展，以及现代物流业的发展，世界各大港口之间的竞争将会十分激烈， 除了硬件建设方面的竞争，同样也会体现在港口信息化建设与应用水平方面。 落后的港口建设现状已成为制约我国积极参与全球经济活动及经济发展 的瓶颈。“十一五 规划明确提出“十一五 期间将加强沿海主枢纽港口的建 设，调整码头布局结构；通过新建、技术改造和资源整合，使沿海港口适应 货物的结构性变化和专业化、大型化、集约化的运输发展要求，推动部分老 港区的功能调整；相应发展地区性重要港口。据了解，近年国际海运及物流 业的高度信息化，要求港口及其相关配套服务也实现电子信息化【3 1 。在当今 强劲发展的互联网时代，无线技术与定位技术相互结合共同发展下，港口智 能调度管理的实现将成为可能。 针对港口智能调度管理需处理大量船舶动态信息的问题，可以通过时空 数据库相关技术进行解决。时空数据库( s p a t i o t e m p o r a ld a t e b a s e ，简称 s t d b ) 及其索引技术是融合了现代通信、计算机应用以及无线网络技术而产 生的一个新兴技术领域。时空数据库是一个包含了时态数据和空间数据，并 能同时处理时空对象的时间和空间属性的数据库【4 】。时空索引技术是对时空 对象数据进行的数据逻辑排序机制，在时空数据库的查询、修改、删除、插 入等过程中对特定数据的快速查找起着重要的作用。对时空数据索引的研究 哈尔滨t 程大学硕士学位论文 i i 主要包括建立索引、插入、删除、更新等操作及其性能研究【5 j 。 1 2 国内外研究现状 时空数据库技术是一个比较新的研究领域，对其研究开始于二十世纪末。 当前，国内外对时空数据库技术的研究应用到工程上的实例还比较少，现有 的应用主要是在基于位置服务的陆地智能交通系统中，可检索的文献表明还 没有将时空数据库相关技术应用到水运及港口调度管理方面构建系统。 1 2 1 港口调度管理国内外发展现状 目前，世界各大港口都积极努力提高管理水平和运作效率。它们通过引 进先进技术和设备，如e d i ( 电子数据交换) 、v t s ( 船舶交通服务系统) 以 及堆场智能化管理等，使自己的业务逐步向专业化、规范化、标准化迈进。 自2 0 0 3 年以来，我国一些大型沿海港口建立了一流的生产调度指挥中j 心。 相关生产调度指挥中心融合了软件技术、g p s 卫星定位、无线通讯、a i s ( 自 动识别系统) 以及航海地理学等多种技术，涵盖了引航、拖轮、码头生产调 度等多个业务流程，使港口生产管理达到了自动化水平。然而，这些也仅在 大型发达港口存在，如上海港生产管理系统，南京港口信息管理系统等，其 他许多中小型海运港口仍采用传统调度方式，致使调度管理效率低下，资源 利用率不高。传统的港口调度管理以调度电话会议为形式指挥港口生产，以 调度日志、单船报表为载体体现调度动态管理，以电话、电报、传真、无线 高频电话为主要通讯联络手段，处理日常调度工作，实施逐级垂直管理【6 j 。 从当前国内相关文献和资料可以分析得到，港口硬件资源方面的建设相 对以前有了很大提高，然而港口调度管理信息化建设整体还处于刚刚起步阶 段。随着全球经济的发展，对于现代港口如需获得良好的经济效益，必然需 要将信息化建设水平更进一步提高。 1 2 2 时空数据库技术研究现状 当前，对时空数据库的研究主要集中在时空数据表达与数据建模、时空 数据索引、时空数据查询语言等方面。总体上，国内外对时空数据库的研究 都不够成熟，在各研究领域都出现了多种理论方法，各种方法都有一定的优 2 哈尔滨 ：程大学硕+ 学f 7 ：论文 缺点，致使当前对时空数据库的研究处于原型研究阶段，很少有大规模应用 产品。针对时空数据库的研究，国外起步相对较早，取得的相关理论成果也 比较多，尤其是欧洲。1 9 9 6 年欧洲启动了c h o r o c h r o n o s 项目，将一批在时态 数据库和空间数据库相关领域的青年科学家联合起来，研究时空结合问题【7 1 。 自该项目启动以来，其在时空数据库方面取得了令人瞩目的成果。国内对时 空数据库的研究机构及部门主要有香港城市大学时空数据库实验室，华中科 技大学的数据库研究组，武汉大学空间信息与数字工程研究中心以及中国科 技大学等，相应学者的研究也取得了一定的成果，提出了一些有创新的想法， 推进了相应理论的发展。 1 3 课题的主要研究内容 现代港口的建设应紧跟现代信息技术的发展，建立一个完善的调度管理 信息系统是港口软件建设方面的发展趋势。本课题主要研究时空数据库索引 技术，并以工程实际应用为背景，将时空数据库技术应用到港口调度管理过 程，利用计算机应用技术，对调度过程的信息进行存储、处理以及实时分析， 同时开发了一个以电子海图为应用平台的港口船舶管理时空可视化系统。 论文的组织结构如下： 第一章首先介绍了课题的背景、目的和意义，然后分析了课题的所属领 域及应用技术的发展现状，最后给出了课题研究的主要内容以及论文的组织 形式。 第二章简要介绍了时空索引技术概况，给出了用于空间数据库的两个主 要系列索引结构一- t r e e 及四叉树( q u a d t r e e ) ，并深入研究了以上两种索 引结构的主要变体，以作为本文研究应用的技术基础。 第三章首先设计了船舶调度过程时空数据集仿真生成算法，然后应用哈 希表及第二章介绍的索引结构，设计了用于港口调度管理的信息分离混合索 引算法，最后从算法对动态信息处理的插入代价及查询代价方面进行了性能 分析。 第四章研究了索引算法的索引及数据物理存储机制，设计了适当的文件 结构类型，分别给出了数据文件及索引文件的物理存储方案。 第五章针对课题工程应用，设计了港口船舶管理时空可视化系统。首先 哈尔滨t 稗大学硕十学位论文 分析了系统工作模式及设计目标，然后分别对客户端、网络通信相应模块进 行设计，最后结合本文设计的时空索引算法构建服务器端移动对象数据库并 给出港口船舶管理时空可视化原型系统的应用状况。 4 哈尔滨t 稃大学硕十学何论文 第2 章时空索引技术分析 2 1 时空索引技术概述 索引是用来提供快速、有选择性的存取数据库的一种机制，它相当于一 个映射机构，将属性的值转换为相应记录的地址或地址集1 8 j 。一个数据库系 统需要一种索引机制帮助它迅速地检索到数据项目。 时空索引技术是集时态索引技术与空间索引技术于一体的索引技术。时 空索引通常需要借鉴空间索引技术，只是时空索引相对空间索引增加了时间 维度。当前已经成熟并且常用的空间索引算法通常不能直接用于时空索引。 传统的索引方法通常考虑的只是查询效率性能，比较适合静态索引，而对于 移动对象因时间变化引起的频繁信息更新，构建动态变化的索引结构，除了 需要考虑查询效率以外，还必须考虑更新代价问题。对此，研究人员已提出 一系列相应时空索引。图2 1 为时空索引技术演变过程图。 从时空索引技术演变过程图中，可以看出对时空索引结构的研究首先起 步于单纯对空间索引、时间索引以及其他基本索引结构。在空间索引结构中， r - t r e e 和q u a d t r e e 索引结构是研究最早的空间索引结构，从这两个索引结构产 生的变体索引结构相对来说也比较多，尤其是r - t r e e ，从该索引结构变体后的 索引结构逐渐深入的融合了时间属性，将空间索引引向了时空索引的方向。 同时，针对各种索引的思想和处理能力，出现了多种混合索引结构用于处理 时空信息，其中将r t r e e 及q u a d t r e e 结构组成的混合索引结构就是一个典型的 应用。 时间特征属性的引入，增加了索引的复杂性以及动态性，而在传统的空 间索引方面相关学者取得了大量的研究成果，很多索引算法也已经投入到了 实践应用之中。对于时空数据库的索引，通常的研究方法是在空间数据库索 引中融入时间属性，通过改进原索引算法解决因时间属性的引入带来的新问 题，从而达到时空索引的目的。从这方面来看，可以根据时间属性特征将时 空数据库索引技术具体划分为索引历史、索引当前和索引未来三类。 哈尔滨工稃大学硕七学位论文 空间索引时间索弓 一口 历史索弓 o j e 他 当前索引当前及未来索引历史、当前及未来索弓 o illi i：in u l ii u r cg e l d ：p a t r i 1 - y n o r i l l l l a lc o y1 - - e eii liil 厂、l 厂、l上厂、 ：。i ：璀r g u r e e l 丑y j 彬 i n e ：f 矗t r e e p p r t r e e i 上厂、l 厂、 i- o h i r + 一t 屺9 一、 一一，r 、， r u t4 t r e e 惯“。畔 h r t 一：e 一， l u r t r e e i 。八 i 一 l 上 m v 3 r - t r e e l k m v ei - t r e e i ：ei 一刚i h 口 甲0 1 厂、r - - - - - - - 丙l 厂、 _ i ；一3俩r跨12-tre(i |i 川权i 毗 t p p e ar t r ee 3dr - r e e2 + i 1仫；t 鼍剐! s e t i 厂、 j | j ? ￥i 一y ： ：jr v ： 狰叶t r e e 工h ! a 厂、s h i n g 乃 ；e b t c e e 。，一、： r 蜊 srr； t r i ；in s ；r r x，a引tree t p r ：j ：l 八 嗡也乙f o 罴：，iv r k 。；t r e e p c f 】1 1 n d e )小i ，黼 r a r 蕾e e d ： 二j t s b t r e e ： i i p r - t 把ec i ： i 。n “d ： i 一-、c 1：f ： 0 v q, t l a p p i珂q ua d t r e e 厂、 i丁v s t r i p s i il i r - i 眵 柙 q u a d t r e e f u t u r eq u a d t 僦 么 i r t i ： j - d e l i 一i 夏i t i b + 蕊! i d 妇时： m b ；l n d e x b b n x1k a v ! - 一里欠m 7 - 7v b - t r c c i b “t r e e i 1 9 8 91 9 9 01 9 9 l1 9 9 21 9 9 31 9 9 41 9 9 51 9 9 6 1 9 9 71 9 9 81 9 9 92 0 0 02 0 0 l2 0 0 22 0 0 32 0 0 42 0 0 52 0 0 6 2 1 1 索引过去 图2 1 时空索引技术演变过程图 索引过去关注的是移动对象历史的时空数据。 随着现代通信技术和定位技术的迅速发展，跟踪并存储记录移动对象的 6 哈尔滨t 程大学硕十学位论文 空间位置成为可能。随着时间的推移，对移动对象相应信息采样后必将产生 海量的历史数据。按照对时态数据处理的方式可以把对历史数据的索引分为 以下三类。 2 1 1 1 空间附加时间 索引参照空间分布进行存储组织并将时态数据作为附加的重要信息，这 类索引的主要目的是对空间数据的高效检索。 r t t r e e 结合了r - t r e e 的空间索引方法和t s b t r e e 的时态索引方法，在每个 索引项中存放移动对象的空间状态和时间区剐9 】【l o 】【1 。r t t r e e 是在r t r e e 0 0 加入了一个新的单元用来表示当前对象的开始时间以及结束时间。r t - t r e e 在 空间查询效率上与r t r e e 等同，然而在时间片查询及时间段查询上则可能要跨 越整个树结构。 3 dr t r e e 把时间作为空间的另一维进行处理【1 2 】。其主要思想是对时间维 查询和空间维查询不进行严格区分。该索引可以支持时态和空间查询，但是 在性能上存在一定的缺陷，主要是时间片查询依赖于历史数据中的所有单元 而并不是依赖于在查询时间上的单元。 s t r t r e e 是对r t r e e 的扩展，其使用了不同的插入、删除算法【1 引。s t r - t r e e 的主要思想是保证空间紧密性，并通过尽量保持属于同一对象的轨迹线段在 一起来保存部分轨迹。 2 1 1 2 重叠和多版本结构 将时间维和空间维区别对待，其主要目标是将一个时间片的空间数据集 中存储到一个索引结构，最终结果是在每一个时间片产生一个独立的索引部 分。因此，此类索引结构需要极大的存储空间。 m r - t r e e 使用了重叠b t r e e 思想f 9 j 。主要思想是为避免将每个时间片的 r t r e e 进行分开存储导致存储复杂过大的问题，采用不存储相同的对象到连续 的r - t r e e 中的方式来节省存储空间。 h r t r e e 类似于m r - t r e e ，采用r t r e e 组织每个时刻的空间信息，在实现时 使用子树重叠的方法保存了不同时刻移动对象的空间分布【1 4 】。进行时间片查 询时，首先找到对应时刻的r t r e e 根结点，然后在r t r e e 中进行空间查询。因 7 哈尔滨t 程大学硕十学位论文 此h r t r e e 对时间片查询方面有很好的性能。然而时间段的查询效率却很低， 并且同一数据项可能被多次检索出来，导致数据冗余较多以及存储空间较大。 m v 3 r t r e e 是一个基于多版本b t r e e 的索引结构5 。它由一个m v r t r e e 和 一个3 dr - t r e e 组成，其中m v r - t r e e 提供时间片查询，而3 dr t r e e 提供时间段 查询。在离散的事件模型方面，m v 3 r t r e e 的性能超过了其他索引结构( 如： 3 dr t r e e 和h r t r e e ) ，其缺点是不能支持对象的位置逐步发生变化。 2 1 1 3 面向轨迹的索引方法 对象的历史时空数据可以看作是各条轨迹的集合，如果针对轨迹自身的 特性对时空数据进行组织，就可以提高对象的轨迹检索效率。对于同一条轨 迹的线段需要进行轨迹保护，轨迹保护的思想主要是考虑线段的时空分布以 及将这些线段集中存放，以提高查询检索效率。 s t r t r e e 是对r t r e e 的扩展，主要思想是同时考虑轨迹保护的两个方面， 它是部分的轨迹保护。t b t r e e 是一个类似r t r e e 的索引结构，做到了严格的 轨迹保护，一个叶子结点只允许存放属于同一条轨迹的线段，其缺陷是空间 上邻近的不同轨迹的线段将被存储在不同结点中【1 3 】。t b t r e e 是s t r - t r e e 在轨 迹处理上的扩展。 s e t i 采用两级索引结构分别存取空间以及时间信息【l6 。该索引方法将空 间划分为静态不重叠的区域，如果移动对象从一个区域运动到另一个区域， 则在区域交界处进行轨迹线段分裂，并将分裂后的两条线段独立加入到所在 区域。划分后的每个区域将对应多个数据页面，每个页面只允许存放该区域 的轨迹线段。在此基础上，将会对每个区域建立一个相应的r - t r e e 时态索引， 叶子结点的索引项代表数据页面的生命周期( 数据页面包含的所有线段的最 小时间间隔值) 。不同的划分方法可以把一条轨迹的线段存储到同一个区域。 该索引方法实际上会降低时空分布的紧密程度，但是却做到了轨迹保护。 s e b t r e e 将空间划分为若干个允许重叠的区域1 1 7 1 。每个区域建立一个 s e b t r e e 索引，针对经过该区域对象的开始时间以及结束时间进行索引处理。 该索引方法和s e t i 关键不同点在于它没有轨迹，记录的是移动对象在各个区 域的二维空间点。 8 哈尔滨t 程大学硕七学何论文 2 1 2 索引当前 索引当前关注的是对象历史和当前的时空数据。 对移动对象当前的位置进行索引，必须及时更新对象的位置。当移动对 象的数量非常大时，频繁的插入和删除操作会急剧增加索引的维护成本。当 前位置的索引方法必须采取某种策略降低对索引的操作频率，这类索引方法 主要有2 + 3r t r e e 、2 3t r t r e e 及l u r t r e e ( 延迟更新r - t r e e ) 等。 2 + 3r - t r e e 索引方法用来索引移动对象当前和过去的信息1 18 1 。该方法的主 要思想是建立两棵独立的r t r e e ，其中一棵用于索引当前的二维点，另一棵用 于索引历史的三维轨迹。若当前对象发生更新，则利用三维m b r ( 最小边界 矩形) 构建对象轨迹，并将其插入到三维的r t r e e 中，同时对二维的r t r e e 进 行删除操作。根据查询时间不同，两个树可能都会被遍历查询。 2 3t r t r e e 与2 + 3r - t r e e 的思想相似，同样利用了两棵独立的r t r e e ，一棵 二维的r t r e e 索引当前对象，另一棵三维的r t r e e 索引历史数据1 1 9 j 。两种索 引的区别是：( 1 ) 在2 3t r - t r e e 中，三维r - t r e e 不保存轨迹而是多维点，从 而避免了浪费大量空间的问题。 ( 2 ) 2 3t r t r e e 禾u 用了t b t r e e 为底层结构， 能够响应面向轨迹的查询。 l u r t r e e 只关注索引时空对象当前位置，它不保存历史数据1 2 。一旦对 象更新它的位置，旧值将被删除，并插入新值。l u r - t r e e 索引结构的目的是 在不考虑r t r e e 索引结构的性能情况下处理频繁更新的移动对象。其主要思 想是只要对象新的位置没有在它原来所在的m b r 外，就不更新索引结构。一 旦对象从m b r 移出，将采用两种方法来更新索引：( 1 ) 如果有必要的合并 与分裂操作，先删除对象，然后重新插入；( 2 ) 如果对象移动后距离m b r 在一定范围内，那么m b r 可以扩展到包含更新的位置。 2 1 3 索引未来 索引未来关注的是对象当前和未来的时空数据。 未来位置的索引通常存储移动对象的最新更新信息，通过存储的信息进 行预测位置的各种查询。目前，在相关索引方面影响力比较高的索引结构是 t p r - t r e e 及其变体t p r * t r e e 等。 t p r t r e e 增加速度矢量对r t r e e 索引结构进行参数化1 2 。索引树中的非叶 9 哈尔滨t 程大学硕十学f 7 ：论文 子结点是时间参数边界矩形，随着时间的改变，这一边界矩形需要跟随变化， 达到始终包含其内部所有的移动对象边界矩形。该索引能够推算出对象在未 来任意时刻的位置，在某个特定的时刻可以将t p r t r e e 看作是一棵r - t r e e 。因 此，通过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 采用相同的索引结构，只是它采用一个更优的代价 模型，使用适当的插入删除策略从而提高了索引的舯i l t _ 厶匕b 匕【2 2 1 。 2 2 空间索引结构r - t r e e 及r * - t r e e r t r e e 系列索引结构中r - t r e e 索引最早是由a n t o m ng u t t m a n 于1 9 8 4 年提出 的，其后许多学者提出了多种改进结构【10 1 。r t r e e 是一种层次数据结构，它 是在b t r e e 基础上发展而来的，是一个类似于b t r e e 的高度平衡树，其插入、 删除等操作是完全动态的。 若把空间数据库定义为t u p l e 的集合，每个t u p l e 中存放有一个空间对象及 其唯一的标识符，则每个r - t r e e 的叶子结点被定义为包含有一个索引项 ( t u p l e 。i d ，i ) ，其q h t u p l e i d 指向数据库中的一条记录，在g i s 中表示一个空间对 象的标识符，i 是一个d 维的包含该空间对象的最小边界矩形。 任意一个非叶子结点中包含这样的实体：( c h i l d p o i n t e r ，i ) ，其中， c h i l d p o i n t e r 是一个指i 句r - t r e e 当前结点下一层结点的指针，而i 是可以覆盖 其下一层所有结点的最小边界矩形，也称为目录矩形。 设m 为每个结点的最大索引项个数，m 为每个结点的最小索引项个数，并 且2smsm 2 ，r 树有以下特性： ( 1 ) 每个叶子结点的索引项数目都在m 到m 之间，除非它同时是根结点。 ( 2 ) 在每个叶子结点的索引项( t u p l e i d ，i ) 中，i 是包含眭t t u p l e i d 决定的d 维空间对象的最小边界矩形。 ( 3 ) 每个非叶子结点的子结点个数都介于m 至l j m 之间，除非它同时是根 结点。 ( 4 ) 在每个非叶子结点的索引项( c h i l d p o i n t e r ，i ) 中，i 是包含所有子结点 的最小边界矩形。 ( 5 ) 根结点最少包含2 个子结点，除非它同时是叶子结点。 1 0 哈尔滨1 j 程大学硕+ 学何论文 ( 6 ) 所有叶子结点都在同一层上。 当插入一个新对象时，从根结点到叶子结点对树进行遍历，选择每次都 能够符合最小放大以包含新对象的子结点。如果那里还有空间，对象将被存 储在该叶子结点中。否则，该叶子结点将被分成两个树叶结点。入口沿着两 个叶子结点分布，尽量使得两个叶子结点的总面积最小。一个新的叶子结点 可能导致父结点过饱和，所以它也可能不得不被拆分。这个过程可能将重复， 直到一直向上到达根结点。在相反的操作过程即删除过程中，一个结点可能 会变得不饱和。在这种情况下，结点将被移开，这将可能又一次导致父结点 不饱和，致使上述同样的操作向上传递。这样的过程可能循环进行，直到向 上到达根结点。 图2 2 展示了一个r - t r e e 的结构，它有两个层次，m = 4 。最低层次有三个 叶子结点，最高层次有一个结点，包括指向叶子结点的指针和最小边界矩形。 把r - t r e e 树叶和结点的最小边界矩形的总面积定义为覆盖，交叠就是两个或更 多树叶的最小边界矩形重叠部分所包含的总面积【2 3 】【2 4 】。在图中，覆盖是aub u c ，交叠是a n b 。很明显，有效的查询需要低覆盖和低交叠。 a p = 一一一亩一目b o i ! l ui i ( 1 。 ：囤：q 由一目田i 匝一 p i l ：回i i - 由c m = 4 图2 2r - t r e e 结构 1 9 9 0 年n o b e r tb e c k m a n n 等人提出了基于r t r e e 的变体索引结构r 事t r e e ，并 研究y r - t r e e 算法的不足，分析了非叶子结点最小边界矩形的面积、周长及相 互重叠这些影响检索效率相关参数的依赖及优化原则1 2 引。 r 宰t r e e 仍采用与r t r e e 相同的结构，在树的构建、插入、删除及检索算法 上基本没有多大变化，主要区别为以下三种操作： ( 1 ) 插入路径的选择 哈尔滨t 稃大学硕+ 学何论文 在选取插入路径方面，r t r e e 只以最小边界矩形面积为参数进行选取，而 r 宰t r e e 在对叶子结点选取时同时考虑索引项目录矩形的重叠与面积，对非叶 子结点的选取保持r t r e e 选取算法。 ( 2 ) 结点分裂 设d 维空间的最小边界矩形i 为( i l ，1 2 ，i d ) ，其中i i = ( i i ，i i + ) ，i i d i s t ( 3 2 ) 关系式( 3 2 ) 中，s l ”s l ”s 2 x 及s 2 y 分别为t l 时刻。一i d l 和。一i d 2 的空间信 息沿坐标轴的分量，d i s t 为两个目标系统最小边界矩形不相重叠时在某一坐 标轴向的最小间隔距离。 3 1 2 时空数据集生成算法设计 本文实验数据的生成参考了g s t d 数据生成仿真算法，并针对调度过程 的工程应用进行了相应改进。生成时空数据集的基本观点是定义一套完备的 用于控制空间对象运动的参数【3 。本文研究的目标系统是非点状，遵循连续 时间戳的时态退化( 时态退化是指有效时间及事务处理时间是同一时间) ， 且在数据集迁移率方面主要考虑具有运动属性的空间对象。研究过程将港口 工作区域理想化为带有边界的矩形区域。 哈尔滨丁程大学硕十学佛论文 3 1 2 1 时空数据处理算法基本操作 时空数据处理算法的基本操作有( 1 ) 对象的持续时间，它涉及到连续对 象实例在时间戳方面的变化：( 2 ) 对象的转移，它涉及对象空间位置的变化； ( 3 ) 对象尺寸范围的变化，它主要指对象最小边界矩形的变化。 基于以上操作时空演进对象连续实例及其投影如图3 2 所示。从图中可 以看出，对象运动过程的实质是其时间信息及空间信息的变化更新。 x x 图3 2 时空演进对象连续实例及其投影 设计有效