（管理科学与工程专业论文）面向时态查询的移动对象索引技术研究.pdf

国防科学技术大学研究生院硕士学位论文 摘要 随着定位技术与无线通信技术的迅速发展，跟踪与定位移动对象成为可能， 如何有效地对移动对象进行管理、查询及提供准确的基于位置的服务是移动对象 数据库研究面临的挑战。移动对象信息管理在交通监测、舰船导航、移动计算、 气象预测、电子战场等许多领域有着广泛的应用。移动对象索引技术具有重要的 理论和实际意义。目前移动对象数据库的研究处于初步阶段，理论和实际应用上 还不成熟，存在许多问题需要新技术来解决。 移动对象索引技术得到了国内外研究者的广泛关注。对现有相关工作的分析 与比较发现：越来越多的应用要求数据管理系统能够查询移动对象过去、现在和 将来信息。为了满足统一查询的需求，提出了一种面向时态查询的索引结构f t 树， 支持全时态信息的查询，适应频繁更新的环境。 本文首先综述了移动对象索引的演变与发展历史，全面地总结和对比分析了 国内外移动对象索引的研究工作。然后提出了面向时态查询的索引结构f t 树：将 多版本思想引入t p r 树中，对支持将来查询的t p r 树进行了改进，有效地保存 t p r 树的各个版本，支持全时态查询；同时，引入重叠技术，避免了结点的复制， 节省磁盘存储空间。为了适应频繁更新的环境，采用批量更新技术，有效地利用 不同对象位置更新之间的空间相关性，降低了更新代价。引入一个二级索引结构， 实现叶结点的直接存取。接着建立了代价模型和选择性估计的数学模型，从理论 角度评价f t 树的性能，模型的优点是只采用了树的基本属性和数据本身的特点， 实验证实了模型有较高的准确率。最后采用实验方法评价f t 树的性能，生成移动 对象数据，以索引大小、查询性能及更新性能等指标与其它的索引结构进行比较。 实验表明，f t 树索引占用磁盘空间较小，磁盘利用率较高，时间片查询性能很好， 时间段查询性能一般，更新性能有显著提高，在不同的数据集上表现稳定，从而 验证了索引技术的有效性。 主题词：移动对象索引；移动对象数据库；查询；代价模型；选择性估计 第i 页 国防科学技术大学研究生院硕士学位论文 a b s t p a c t w i t ht h er a p i dd e v e l o p m e n to f p o s i t i o n i n ga n dw i r e l e s sc o m m u n i c a t i o nt e c h n i q u e ， i ti sp o s s i b l et ot r a c ka n dp o s i t i o nm o v i n go b j e c t s w h a tt h ec h a l l e n g et h a tm o v i n g o b j e c td a t a b a s e s f a c ei sh o w t oe f f e c t i v e l ym a n a g ea n dq u e r ym o v i n go b j e c t sa n do f f e r e x a c tl o c a t i o nb a s e ds e r v i c e s m a n a g i n gm o v i n go b j e c t s i n f o r m a t i o ni sw i d e l yu s e di n m a n yf i e l d s ，s u c ha st r a f f i cm o n i t o r i n g ，s h i pn a v i g a t i o n , m o v i n gc o m p u t i n g ，w e a t h e r f o r e c a s t i n g ，e l e c t r o n i cb a t t l e ，e t c m o v i n go b j e c ti n d e x i n gt e c h n i q u eh a sv i t a lt h e o r e t i c a n dp r a c t i c a ls e n s e i ti si m m a t u r ea n dh a sm a n y p r o b l e m st os o l v e r e s e a r c h e r sp a ym u c ha t t e n t i o nt om o v i n go b j e c ti n d e x b a s e do nt h ea n a l y s i so f e x i s t i n gw o r k ，t h e r ea r ei n c r e a s i n gd e m a n d si nd a t am a n a g e m e n ts y s t e m st os u p p o r t q u e r y i n gt h ep a s t ，p r e s e n ta n df u t u r ei n f o r m a t i o no fm o v i n go b j e c t s t os a t i s f yt h e u n i f i e dq u e r yd e m a n d ，p r o p o s ea ni n d e xs t r u c t u r en a m e df t - t r e et o w a r d st e m p o r a l q u e r y ，w h i c hs u p p o r t sf u l lt e m p o r a li n f o r m a t i o nq u e r ya n di sa d a p t i v ei nf r e q u e n t l y u p d a t i n ge n v i r o n m e n t s u m m a r i z ea n da n a l y z et h ee v o l v e m e n ta n dp r o g r e s so fm o v i n go b j e c ti n d i c e s t h e np r o p o s ei n d e xt o w a r d st e m p o r a lq u e r y f t t r e ei n t r o d u c e st h em u l t i - v e r s i o ni d e a i n t ot p r - t r e e ，e f f e c t i v e l yp r e s e r v e se a c he d i t i o no ft p r - t r e ea n ds u p p o r t sf u l lt e m p o r a l q u e r y , w h i c hi n t r o d u c e st h eo v e r l a p p i n gt e c h n i q u e ，a v o i d sn o d er e p l i c a t i o na n ds a v e s d i s ks t o r a g e f t - t r e ea d o p t sb u l k l o a d i n gu p d a t i n gt e c h n i q u e ，w h i c he f f e c t i v e l yu s e st h e s p a c er e l a t i v i t yo fv a r i o u so b j e c t s ，r e d u c e su p d a t i n gc o s t ，a n di n t r o d u c e sas e c o n d a r y i n d e xf o rd i r e c t l yr e a d i n ga n dw r i t i n gl e a fn o d e s c o n s t r u c tc o s tm o d e la n ds e l e c t i v i t y e s t i m a t i o nf o rt h e o r e t i ca n a l y s i s 1 l 豫m o d e l sa d v a n t a g ei so n l yu s i n gt r e e sa t t r i b u t e a n dd a t a sp r o p e r t y g e n e r a t em o v i n go b j e c t sd a t aa n dc o m p a r et h ef t t r e ew i t ho t h e r i n d i c e sb yi n d e xs i z e ，q u e r ya n du p d a t i n gp e r f o r m a n c e e x p e r i m e n t ss h o wf t t r e e s v a l i d i t y i to c c u p i e sl e s sd i s ks p a c e ，u s e sh i g h e rd i s ks p a c e ，h a sb e t t e rt i m e s l i c eq u e r y , b u th a sc o m m o nt i m ei n t e r v a lq u e r y , r e m a r k a b l ye n h a n c e su p d a t i n gp e r f o r m a n c e ，a n d p e r f o r m sw e l lo nv a r i o u sd a t as e t k e yw o r d s ：m o v i n go b j e c t si n d e x ；m o v i n go b j e c t sd a t a b a s e ；q u e r y ；c o s t m o d e l ；s e l e c t i v i t ye s t i m a t i o n 第i i 页 国防科学技术大学研究生院硕士学位论文 表目录 表1 1 移动对象索引分类5 表2 1 移动对象过去信息索引比较18 表2 2 移动对象现在信息索引比较2 l 表2 - 3 移动对象将来信息索引比较2 5 表2 4 移动对象全时态信息索引比较2 6 表4 1 模型中的符号及其含义说明5 5 表4 2 实验的硬件与软件环境6 2 表4 3 实验参数含义及取值6 5 第1 i l 页 国防科学技术大学研究生院硕七学位论文 图目录 图1 1 基于位置服务的系统框架2 图1 2 移动对象查询的需求4 图1 3 移动对象索引演变与发展历史6 图3 1 移动对象与叶结点m b r 的组织方案3 0 图3 2c t p b r ( 虚线表示) 与m b r ( 实线表示) ：3 1 图3 3t p r 树中元素的表示：3 2 图3 4 在t l 时刻插入e 后，n 1 的m b r 紧缩，n 2 不变3 3 图3 5 查询与限定矩形的交叉3 3 图3 6f t 树的基本结构3 6 图3 7f t 树中间结点的插入过程3 7 图3 8 内部结点的版本分裂3 7 图3 9 内部结点的关键值分裂3 8 图3 1 0 结点m b r 的紧缩3 9 图3 1 1f t 树叶结点的插入过程4 l 图3 1 2 叶结点的广义关键值分裂4 1 图3 1 3 将叶结点的一条记录重插到另一叶结点中，腾出空间再插入4 3 图3 1 4 将记录插入到次优的叶结点中4 5 图3 1 5 叶结点的版本分裂4 6 图3 1 6 叶结点的关键值分裂4 6 图3 1 7 叶结点删除记录，借用另一个叶结点的记录4 8 图3 1 8 更新路径和缓冲区状态：5 1 。 图3 1 9 批量更新的系统框架5 1 图4 1 结点的演化过程5 8 图4 2g s t d 生成的移动对象数据6 3 图4 3 美国马里兰州蒙哥马利郡的道路一6 4 图4 4 以t i g e r 数据集为基础合成的移动对象数据：6 4 图4 5 索引大小比较。6 6 图4 6 树高与存储利用率比较6 6 图4 7 时间片查询时间比较6 7 图4 8 时间片查询的磁盘i o 次数比较6 7 图4 9 时间段查询时间比较6 8 图4 1 0 时间段查询的磁盘i o 次数比较。6 8 第1 v 页 国防科学技术大学研究生院硕士学位论文 图4 1 l 索引时l 日j 的影响6 9 图4 1 2 范围查询大小的影响6 9 图4 1 3 更新时间比较7 0 图4 1 4 更新的磁盘i o 次数比较7 0 图4 1 5 缓冲区大小的影响7 l 图4 1 6 代价模型与选择性估计的准确率7 1 图4 1 7 结点容量的影响7 2 图4 1 8 数据集分布类型的影响7 2 图4 1 9 道路数量的影响7 3 第v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 亘自吐奎查询煎整盈殖錾塞l 这查婴究 学位论文作者签名： 缢查k 日期：历形7 年，月牛日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅：可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文作者签名：猛盐 作者指导教师签名：监垫 日期：卅年月日 日期：加叩年 月垆日 国防科学技术大学研究生院硕士学位论文 第一章绪论 本文综述了移动对象索引演变与发展历史，在对比分析移动对象索引技术的 基础上，发现查询移动对象过去、现在和将来信息的需求日益重要，因此提出了 一种面向时态查询的索引结构f t 树。引入多版本思想和重叠技术改进了t p r 树， 从而支持全时态的信息查询；采用了批量更新技术，可以适应频繁更新的环境。 并从理论和实验角度证实了f t 树良好的性能。 1 1 研究背景 数据库技术诞生于2 0 世纪6 0 年代，经过约半个世纪的发展，形成了坚实的 理论基础、成熟的商业产品和广泛的应用领域，吸引了越来越多的研究人员加入。 随着信息管理内容的不断扩展和新技术的层出不穷，数据库技术面临前所未有的 挑战。特别是无线通讯技术、卫星全球定位系统g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 和地理信息系统g i s ( 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 ) 快速发展和普及，跟踪记录 移动对象位置成为可能，使应用程序管理移动对象的位置数据成为可能，也使得 人们可以随时随地访问信息的愿望成为可能i i 吲。 传统数据库技术主要是管理更新周期相对较长的数据，如果数据没有被修改 则认为是保持不变的。由于移动对象的位置信息不断变化，使数据库的更新过于 频繁导致系统资源枯竭，响应速度下降；或者数据库更新频率小于信息变化频率， 导致信息过时、系统准确率下降。移动对象数据库系统要求支持移动用户在多种 网络条件下都能够有效地访问所需要的数据，并完成数据查询和事务处理。移动 对象的连续运动对传统数据库技术提出新的要求和挑战，移动对象数据库的概念 应运而生，并迅速地成为一个新的研究热点【4 叫。 移动对象数据库( m o v i n go b j e c t sd a t a b a s e ，m o d ) 是指对移动对象的位置及 其它相关信息进行表示与存储管理，并提供移动对象进行查询的数据库，是时空 数据库研究领域最新发展起来的一个重要分支，研究内容包括位置的表示与建模、 位置更新及预测策略、移动对象索引技术、不确定性的表示及处理、移动对象的 查询处理、位置相关的持续查询及环境感知的查询处理等关键技术【_ 7 1 。本文研究的 正是移动对象索引技术，移动对象数据库通常管理着数量庞大的移动对象，查询 处理时如果逐个扫描所有的移动对象，会占用大量系统的资源，极大地影响系统 的性能。为了减小搜索空间，就必须对移动对象进行索引。 移动对象管理技术在许多领域有广阔的应用前景和良好的市场潜力，在许多 应用如交通调度控制、气象监控及个人位置服务等领域，往往需要对移动终端的 第1 页 国防科学技术 学研究生院硕十学位论文 位置进行追踪管理并提供相关查询服务。位冕服务叭l o c a t i o n b a s e d s e r v i c e ，l b s ) 是一种向移动用户提供位簧数据的技术，所提供的信息服务与用户当前位置相关。 l b s 融合了i n t e m e t 、无线通信移动定位和g i s 技术，将来用户可以在任何时间和 地点获得移动用户所在位置的相关服务，如获取其他移动用户的位置、导航服务、 查询附近的各种场所等。图11 显示了一个l b s 系统框架。 移自对氧盐据库 幽1l 基丁位置服务的系统框架 下面列举些应用实例： 例1 战场目标监挡 信息化条件下，网络化的信息系统将陆、海、空、灭、电构成多维一体战场， 夺取战场信息优势可以借助卫星、无人机、地面传感器等设备采集战场上的数据， 快速有效地实现信息的共享，战场信息资源成为整个战场的重要支掸【9 】。一个重要 的需求是对军事和战略目标进行实时监控和预测。例如重要的机场、军事基地和 核电站等战略目标，战争进程当中根据作战要求发现符合条件的军事打击目标， 一旦查找到结果必须采取进一步措施。战场管理系统位置服务平台负责管理战场 环境中的各种移动目标，实时回答作战单元的各种查询服务。战场环境中的移动 目标位置通过无线通信网络、传感器网络或卫星侦察定位等方式向位置服务平台 提交位置信息。一个典型例子是伊拉克战争，美军短时间内摧毁了一些关键军事 设施，使伊拉克陷入瘫痪状态。转化为移动数据管理中的问题即是对历史资料的 分析和基于范围的实时查询与预测查询，如查询“当前时刻伊拉克首都1 0 0 公里 内的军用机场有哪些”，“未来5 分钟内离我方最近的友军番号及方位”。为了 满足这些数字化战场上涌现出的新需求，就需要移动对象索引技术作为基础软件 模块集成在这一应用系统当中。 例2 城市变通调度与管理 随着城市化进程的进一步深化，城市各项基础设施向现化代发展，g p s 技术 薷2 页 国防科学技术大学研究生院硕士学位论文 不断成熟，各个国家也开发出交通管理系统。在上下班高峰期，出租车司机可以 查询“2 分钟后哪些路段比较拥堵 ；用户在驾车行驶过程中可以查询“距离当前 位置最近的加油站”；交通部门可以“预测某十字口十分钟内通过的汽车数量 。 为了满足这些交通中的需求，需要将移动对象索引作为基础模块。 例3 紧急救援服务 如美国的e 9 1 1 和欧洲的e l l 2 等。电信服务商基于移动电话网络或g p s 定位 为公众用户提供紧急救援服务。例如，出现交通事故或野外事故后，用户可以用 移动电话呼叫救援，救护者也可以查询“离当前位置最近的医院的地址”，从而 将病人以最快速度送到医院救治。移动对象索引也给这些系统提供了支持。 例4 移动传感器网络 传感器网络可在危险或不方便人为探测的环境中工作，通过装备在传感器上 的收发器，使远程用户能够收集检索到环境信息。在移动传感器网络中，传感器 结点自身具备移动和定位的能力，能够动态分布于监控区域，结合环境变化自主 做出位置调整。例如在地震救援中，救援人员可以从空中投放传感器到受灾地区， 通过传感器搜集“是否有生命迹象”等信息，然后查询“在离震源5 公里范围内 哪些位置可能有人存活，“6 号救援小分队5 分钟内需要前往的救援地点等。 这样的传感器网络系统中还是需要移动对象索引基础模块的支持。 例5 导航服务 无线用户可以随时随地知道自己的准确位置，提供的信息可以是文字、声音、 图片的方式。位置服务系统可以处理用户的各种导航需求，例如用户可以查询“离 当前位置最近的饭店和宾馆，相关的交通行驶路线，甚至是最优的路径查询等。 这些请求可以看作是“被动的 请求，从另外一个角度看也可以“主动的 提供 信息，商业企业的关注点在于此，当顾客经过某个运动品牌商店的商业圈范围时， 顾客的移动电话中可能出现相应的广告，甚至提供电子优惠券。为了快速准确地 响应用户请求，也要用到移动对象索引技术。 例6 智能物流配送 现代的商业活动中，大量产品的需要从生产地运送到销售地，在运输过程中 需要监控运输的情况。商家可以查询“托运货物a 运输过程中的动态位置信息 。 美国高通公司已经开发出了车辆跟踪和高度系统全线通( o 删们黜惦s ) 系统【l 引， 将g p s 、g i s 、计算机、物流技术融为一体，实现了物流管理一体化和全面自动化。 为了更有效地配送产品，智能物流系统也离不开移动对象索引技术。 总之，上面所提到的一些应用是已经或即将出现的，发出查询请求的可能是 正在移动的对象，也可能是静态的用户，这些应用是传统数据库技术难以支持的。 移动对象索引技术是移动对象数据库技术的重要组成和核心技术之一。 第3 页 国防科学技术大学研究生院硕+ 学位论文 移动对象数据库记录了移动对象在不同时刻的信息，用户可以查询移动对象 过去、现在和将来的位置及相关信息。移动对象数据库不同于空间数据库，它的 每一个数据项的时间戳是单调递增的，由于数据随时间不断积累，数据量将十分 庞大。如果把时间当作另一维，再用空间索引的方法进行管理，其查询效率较低， 如果将时间维独立出来，并同时保存每一时间戳的空间数据，存储的开销会很大。 因此，建立有效的索引结构来实现对时空数据的管理是非常重要的。 现有的移动对象索引主要是单独支持过去、现在、或将来信息查询，应用上 侧重于某一方面。为了满足统一查询的需求，移动对象索引应该支持过去、现在 和将来的全时态查询，这引起了研究人员的重视，需要提出新的索引结构。 全时态( f u l lt e m p o r a l ) 信息索引定义为对移动对象过去、现在和将来的信息 进行存储管理，可以在整个时态域上支持移动对象的查询。若使用单独支持过去、 现在和将来查询的索引来分别索引过去、现在和将来的信息，虽然也能达到目的， 但是会占用大量的空间，还可能对相同的数据进行重复的索引，浪费存储空间， 另外，不同的索引间转换花费时间，效率比较低。而全时态索引能够只采用一个 索引结构就将三种查询需求统一起来，索引移动对象过去、现在和将来的信息， 节省了存储空间，也提高了查询的效率。图1 2 对四种查询进行了区别。 图1 2 移动对象查询的需求 如图1 2 所示，显示了两个移动对象在一维空间上的运动轨迹，实线表示移动 对象过去的运动轨迹，虚线表示预测的将来对象的运动轨迹，矩形框表示查询的 时间和空间范围。现有的移动对象索引主要支持过去信息查询，如图中的时间段 查询；支持现在信息查询，如图中的时间片查询；支持将来信息查询， 如图中的时间段查询q 触。最近几年引起关注的全时态( 过去、现在和将来) 的 查询，如图中的时间段查询q 枷。 第4 页 国防科学技术大学研究生院硕十学位论文 1 2 国内外研究现状 索引技术可以极大地提高数据检索或查询的效率。传统数据库中主要的索引 结构为线性索引、h a s h 索引和树形索引。线性索引结构简单，但是针对大量无序 数据的存取效率较低；h a s h 索引有较高的查询效率，但对时态的支持较弱。因此， 不能直接用于移动对象的索引。空间数据库和时空数据库中主要采用树形结构。 因为它对基于磁盘的海量数据而言，具有较高的查询效率。 移动对象索引通常是借鉴空间数据索引技术【l ，不同在于时空数据中必然有 一维是时间维。空间索引方法主要适用于静态的空间对象，更新数量较少，更多 考虑查询效率，在移动对象数据库应用中，移动对象的位置频繁地改变，除了要 考虑查询效率，还必须重点考虑更新代价问题。传统索引方法不适用于频繁更新 的移动对象，需要专门的移动对象索引技术来进行存储和管理。 移动对象数据库通常管理着数量庞大的移动对象，为了减少搜索空间，提高 查询的性能，必须对移动对象进行索引。由于移动对象不断地产生大量时空信息， 如何有效地管理这些动态信息一直是被广泛关注的研究课题。近年来，移动对象 索引的研究是一个热点，数据库领域的国际著名学术会议，例如a c ms i g m o d 、 a c mp o d s 、v l d b 、i c d e 和c i k m 等，都有大量关于移动对象索引的研究成果 发表，同时国际上专门的时空数据库会议，如s s t d 、m m d 和a c mg i s 等也把 移动对象索引的研究作为重点之一。 表1 1 移动对象索引分类 淤： 移动点 移动区域 时间窗口 s t r - t r e e ，t b - t r e er t - t r e e ，m r - t r e e ，3 d r - t r e e 过去 s e t i ，s e b - t r e eh r - t r e e ，h r + 一t r e e ，m v 3 r - t r e e f n r - t r e e ，m o n - t r e e p p r - t r e ew i t hl i n e a rg r e e d y 信息索引 v t r e e ，t b - t r e e ，p a t r e e p p r t r e ew i t hp o l y n o m i a lg r e e d y i m t f n d 盯i r s t - t r e e ，a p r - t r e e ，s e s t - i n d e x 现在 h a s h i n g 2 + 3 r - t r e e ，l u r - t r e e ，a i m i m o r s b o t t o m u pu p d a t e s 信息索引 2 3 t r t r e e q + r - t r e e ，c o v e t , l g u p m r - q u a d t r e et p r - t r e e ，s t a r - t r e e ，p r - t r e e 将来 d u a l i t yt r a n s f o r m a t i o n v c i ，t p r t r e e ，h t p r - t r e e 信息索引s v - m o d e l f t q u a d t r e en s i ，s t r i p e s ，r e x l t r e e p s i ，b x - t r e e ，s t p - t r e es t 2 b t r e e ，b 血a - t r e e 全时态 p c f i + ，r p p f _ t r e e ，t e b x 信息索引 q h i n d e x ，m v t p r - t r e e 第5 页 国防科学技术人学研究生院硕士学位论文 从时悯和空刚两个角度埘移动对象索引进行了分类如表l l 所示。第二章对 这牡移动对象索引结构进行全面的综述，图13 描绘了移动对象索引技术的演化与 发展历史。罔巾箭线表示新的移动对致索引与原有索引结构的联系。 从空问角度来看，已经提出的各种移动对象索引处理的时空数据类型有两种： 移动点和移动区域。建立索引的思路主要有两条：一是自下而上，从局部到整体， 先拒索引中存储单个移动对象的信息，然后由单个移动对象的信息获得某个区域 中的移动对象信息：是自顶向下，从整体到局部，先在索引中存储区域的信息 然后通过区域信息取得单个移动对象的信息。 从时问维度来看，现有大部分移动索引方法主要支持某一个侧面的信息有询： 支持过去信息、支持现在信息、支持将柬信息的查询。然而支持全时忐( 过去、 现在、将柬) 信息处理的索引方法较少，不能满足更加丰富的查询需求；提出的 少量全时态索引力法也柏不足，如查咖效率低等，存在改进之处。 国防科学技术大学研究生院硕士学位论文 与本文研究工作最相似的是在文献【1 2 q b 提出的m v t p r 树( m u l t i p l ev e r s i o n t p r t r e e ) ，m v t p r 树综合了t r 树【1 3 1 和t p r 树【1 4 】索引结构，m v t p r 树的数据 结构和操作算法与t r 树基本类似，主要改进了搜索算法。m v t p r 树虽然也支持 全时态查询，但是存在几点不足： 1 m v t p r 树虽然使用t r 树的多版本思想，但没有进行优化，容易发生版本 分裂，存在大量的版本复制，造成索引过大。 2 m v t p r 树有较多的冗余，因为没有考虑重叠，对于没有改变的数据也进行 复制，相同的信息被多次存储，浪费存储空间。 3 m v t p r 树的搜索算法存在多路查找，查询的结果存在大量的重复。 4 m v t p r 树的插入算法考虑了范围矩形的扩展最小，对范围矩形重叠的影响 考虑不够，可能导致范围矩形的组织不合理。 5 m v t p r 树的删除算法只是考虑修改存储的数据，没有进行相应的调整，如 分裂，来优化树的结构。 6 m v t p r 树的更新算法是采用简单的删除重插机制，删除和重插过程都需 要对整棵树进行自顶向下的搜索，代价比较高。 1 3 论文的主要研究内容 本文针对目前移动对象数据库领域中的研究热点，在全面总结和分析国内外 移动对象索引技术的基础上，提出了一种面向时态查询的移动对象索引，从理论 和实验角度对索引的性能进行了分析。本文的具体工作如下： 1 划分移动对象索引：根据时间和空间两个角度对移动对象索引技术进行划 分：空间角度分为支持移动点和移动区域的索引；时间角度分为过去信息索引、 当前信息索引、将来信息索引和全时态信息索引。全面详细地描述各类移动对象 索引的演变与发展情况，并进行了对比分析。 2 提出移动对象索引结构f r 树：将多版本与重叠技术引入t p r 树，有效保 存t p r 树的各个版本，节省磁盘存储空间，支持过去、现在和将来的时态查询。 采用批量更新技术，将相似的更新聚集到一起进行更新，提高更新的效率，适应 频繁更新的环境。详细地阐述了f t 树的插入、删除、查询和批量更新算法。 3 f t 树的理论分析：建立起数学模型，从理论上对f t 树的性能进行分析， 包括代价模型和选择性估计，并在实验中证实了模型有较高的准确率。 4 f t 树的实验对比：生成移动对象数据，包括基态数据为模拟数据和基态数 据为真实数据的数据集，然后建立索引，以索引大小、查询性能以及更新性能等 指标与其它索引结构进行比较，从实验角度证实了f t 树的有效性。 第7 页 国防科学技术大学研究生院硕士学位论文 1 4 论文的整体结构 论文包括五章，各章内容具体安排如下： 第一章，绪论。简单介绍了论文的研究背景和意义，简要总结了国内外相关 研究工作，提出了论文主要的研究内容及取得的成果。 第二章，移动对象索引技术。首先介绍了移动对象索引基本概念和相关理论， 接着根据时间和空间两个角度对移动对象索引技术进行了划分，并详细地描述及 对比分析各类移动对象索引，从而全面地了解移动对象索引的演变与发展情况。 第三章，f t 树：一种面向时态查询的移动对象索引。提出一种面向时态查询 的移动对象索引结构f t 树，将多版本和重叠技术引入t p r 树中，可以支持过去、 现在和将来的时态查询。采用批量更新方法，优化f t 树的更新性能。 第四章，f t 树的性能分析与实验评估。建立数学模型对f t 树进行理论分析， 然后进行了对比实验，最后给出了性能分析的结果。 第五章，结论。总结了本文的研究成果，并对未来研究工作进行了展望。 最后是致谢、参考文献列表、作者在攻读硕士学位期间取得的学术成果。 第8 页 国防科学技术大学研究生院硕士学位论文 第二章移动对象索引技术 本文重点研究移动对象数据库中移动对象索引技术，这一领域是目前数据库 研究的前沿领域，也是移动对象数据库的研究热点和难点。本章首先介绍了移动 对象的基本概念和相关理论，接着从时态角度将移动对象索引技术划分为四大类， 进行了全面的综述和详细的对比分析。 2 1 移动对象的基本概念与相关理论 本节首先给出了移动对象的定义、特点、表示和存储方法，接着总结了移动 对象的查询技术，最后归纳了移动对象索引的分类指标。 2 1 1 移动对象的定义 移动对象是位置不断随着时间变化而改变的空间对象，其变化可以是离散的， 也可以是连续的f 7 1 。移动对象有狭义和广义之分。狭义移动对象是指对象位置属性 随时间不断地发生变化，如轮船、洪水、飓风等。广义的移动对象是指含有不断 变化的属性的数据对象，不特指对象的运动，也就是说静止的对象如果含有不断 变化的属性，也可以用移动对象的方法进行管理，比如房间本身是静止对象，但 房间的温度可以随时问变化。本文的研究是针对狭义的移动对象。 按照对象的运动速率，可以将狭义的移动对象进一步划分为连续变化的移动 对象和离散变化的移动对象。高变化率的移动对象，如汽车、轮船、飞机等称为 连续变化的移动对象。低变化率的移动对象，如办公室里的人等称为离散变化的 移动对象。本文的研究是针对连续变化的移动对象。 2 1 2 移动对象的特点 移动对象具有下面的特点5 1 ： 1 移动对象信息内容的多样性和复杂性。移动对象除了自身的属性信息以及 不断变化的位置信息外，还与周边的地理环境，如街区、商业点、居民住宅区等， 密切相关。其数据量大，数据覆盖面广，语义及拓扑关系复杂。 2 移动对象的随机性和规律性。移动对象的移动具有随机性，如出租车根据 乘客的需要到达指定的地点，不同的乘客目的地会不同，出租车的行驶路线不同； 而公交车却有着固定的线路和运行时刻表。但是根据交通需求的特点和大数法则， 较长的时间如数周、数月，出租车的行驶轨迹可能会呈现出某种统计规律，这也 是交通预测和规划等的重要依据。 第9 页 国防科学技术大学研究生院硕十学位论文 3 移动对象的静态性和动念性。任何移动对象都有起点和终点，有两种基本 状态：静止和运动。一方面我们关心其静止状态，如车辆停车的原因、是否出现 拥堵或者出现故障等；另一方面我们关心其运动状态，如运动的速度、方向等。 4 移动对象的不精确性和不确定。移动对象运动是连续的，但计算机只能按 离散方式进行存储和计算。由于采集设备精度限制，移动对象的位置信息空间上 与实际位置也可能存在一定的偏差。另外，由于传输的延时和处理的开销等影响， 移动对象存储的具体信息与实际位置在时间上总是存在滞后。 5 移动对象的查询是与查询时间和查询对象所处的位置相关的。不同的时刻 得到的回答是不同的，这取决于用户在不同时刻所处的空间位置。例如用户查询 “当前离我最近的公交车站，随着我的移动，位置发生变化，周围的公交车站 也会发生变化；或者查询“在a 街区上的公交车 ，由于公交车是移动的，不同 时间出现在a 街区的公交车也会不同。 2 1 3 移动对象的表示 目前，主要使用移动点( m o v i n gp o i n t s ) 和移动区域( m o v i n gr e g i o n s ) 两种 基本空间对象来近似地表示移动对象，由于线( 曲线) 本身就是运动的抽象或者 投影，可以转换为对移动点轨迹( t r a j e c t o r y ) 的描述【l6 1 。轨迹可看作是点的集合， 反映了移动对象一段时间内的移动过程。根据移动对象时间维递增的特点，时空 立方体中的移动轨迹始终呈向上的趋势。 仅需要管理随时间变化的位置信息的移动对象，称为移动点对象，如行驶的 汽车、动物、移动手机用户等。而需要管理随时间变化的形状信息的移动对象， 称为移动区域对象，如迁徙的种群、沙漠、军队、疾病传播的区域等。二维空间 中的点对象随时间变化情况，可以用三维空间的曲线表示；区域对象的变化不仅 包括空间位置的变化，还包括形状的变化，如扩张、收缩等。本文讨论的是二维 空间中的空间对象，同样的讨论也可以扩展到三维或更高维的空间中。 2 1 4 移动对象的存储方法 目前使用的移动对象的数据存储方法主要有以下三种【1 5 】： 1 空间位置点存储：使用关系数据库将移动对象移动过程中采样的每个位置 信息依次存储起来，包括x y 坐标、运动方向、速度和时间信息等。这种方法的 特点是存储了所有不断变化的位置序列数据，由于对原始数据进行存储，灵活性 较好，可以满足多种需求。缺点是如果移动对象数量很大，系统需要存储的数量 会非常大。另外，不同的移动对象采样的频率可能会不同。移动位置点信息用于 移动对象位置的实时显示，也可以用于过去某时间段移动轨迹的历史回放。 第l o 页 国防科学技术大学研究生院硕十学位论文 2 移动函数存储：通过构造移动对象的运动函数来表示移动对象的运动轨迹。 运动函数采用普通的函数方法，在有效的时间内推算出对象的位置和相应的运动 类型。运动参数描述了运动的特性，如移动对象的起始位置、运动的速度和方向。 其特点是对于运动比较规律的移动对象如飞机、轮船等只需存储比较少的运动的 参数就能满足历史轨迹查询的需求，同时也便于预测移动对象将来的位置。 3 移动轨迹存储：移动对象地各个空间位置点的数据组成了一条移动轨迹。 为了分析移动轨迹各时间段的情况，可以将移动轨迹分成很多段，分段的依据是 移动对象方向的改变或者状态的变化，也可以是某一固定的时间间隔。因为移动 轨迹能比较好地反映移动对象的运动规律，所以常常作为移动对象查询等的基本 单位，而且存储的数据量要比空间点位置方法要小，可以节省很大存储的空间。 2 1 5 移动对象的查询技术 移动对象索引的目的是有效支持各种移动对象查询，所支持的查询种类越多， 存取方法就越有价值。下面从时态和时空数据属性角度划分了查询技术。 2 1 5 1 根据时态划分 时间可以划分为三种：有效时间、事务时间和双时态时间【l 7 1 。不同的应用对 时间的关注重点存在着差异，从而产生多种多样的查询需求。目前针对移动对象 数据库的查询，从时态角度来划分，移动对象索引可以分为以下四类： 1 过去信息查询，索引移动对象的历史位置，并查询移动对象的过去信息。 例如查询“过去一个小时内经过长沙市五一大道的出租车 。 2 现在信息查询，索引移动对象当前的位置，并查询移动对象现在的信息。 例如查询“当前时刻行驶在长沙市五一大道上的出租车 。 3 将来信息查询，索引移动对象当前的位置，并查询移动对象将来的信息， 往往涉及到预测技术。例如查询“下一个小时内经过长沙市五一大道的出租车。 4 全时态信息查询，索引移动对象的历史位置和当前位置，并查询移动对象 在整个时态域的信息。例如查询“过去一个小时内经过长沙市五一大道的出租车， 在下一个小时后会出现在哪些地方。 2 1 5 2 根据时空数据的属性划分 根据时空数据的特定属性，移动对象索引大体可以分为以下三类【1 8 】： 1 基于坐标的查询( c o o r d i n a t e b a s e dq u e r y ) ( 1 ) 点查询( p o i n tq u e r y ) ：一是查询在某时刻位于某地的移动对象，例如 查询“上午9 点整长沙市五一大道上的出租车 ；二是查询移动对象在某时刻的 位置，例如查询“车牌号为湘a 2 0 0 9 的出租车，上午9 点整所在的位置 。 第11 页 国防科学技术大学研究生院硕士学位论文 ( 2 ) 范围查询( r a n g eq u e r y ) ：查询某时刻或某段时间内在或小在某个地理 范围内的移动对象，例如查询“上午9 点到l o 点车祸事故发生地5 0 米内的所有 车辆 。范围查询是最基本的移动对象查询类型，可以分为三种，一