（计算机软件与理论专业论文）一种高效的移动对象位置索引机制的研究.pdf

山东大学硕士学位论文 摘要 随着3 g 时代的到来和众多具有定位功能的无线手持设备的大量普及，促使一 类基于位置的服务，称为位置相关服务( 1 0 c a t i o nb 嚣e ds e r v i c e ，l b s ) 成为可能。 相应的移动对象的位置追踪也变得越来越可行和必需，这就需要有一种高效的索 引结构来定位移动对象的位置。然而传统的移动对象时空索引技术不能同时有效 地支持对移动对象的过去、现在和将来位置的查询，这是由空间数据的复杂性和 移动对象的动态易变属性造成的。 本文提出的t e b 2 ( 1 n m ee 咖p yb x ) 混合索引结构，在b 。树索引结构的基础上 进行了改进，并且增加了建立在叶结点之上的h a s h 辅助索引表来支持对象的频繁 更新操作，能够有效地解决上述问题。它简化了索引关键字来增大索引的时间跨 度，通过使用线性时间函数来表征移动对象的位置，可以索引移动对象从过去到 将来的位置：该索引结构同时引入时间熵，用来表征数据库中移动对象的位置信 息随时间增长的衰减度量，故能定期剪除那些存储超过一定期限的对象信息，维 持索引结构处于某个稳定的规模以提高系统的索引效率。 该索引结构将移动对象的位置存储在一个b + 树森林中，它可以有效地支持对 移动对象的过去、现在和将来位置的查询；同时它也有效地支持时间跨度较大的 时空范围查询和基于时间地点受限的集合查询，例如查询那些在一个时间间隔集 合内都位于一个特定的空间区域内的移动对象；并且与b 1 树索引结构相比，由于 t e b i 混合索引结构引入的h a s h 辅助索引表能够有效地支持自底向上的局部更新策 略，所以它也具有较高的插入、删除及更新效率。 关键词：移动对象：t e b 。混合索引；时间熵；h a s h 辅助索引表 山东大学硕士学位论文 a b s t r a c t 晰t ht i l e 删v a lo f 3 ga r i dt h ep o p u i 撕t yo f s u b s t a n t i v e 谢r e l e s sd e “c e s 血a th a v e m e1 0 c a 廿n gf 岫c l i o n ，a 】o c 撕o n - b 髂e ds e l c e ( l b s ，f o r 出o n ) b e c o m e sp o s s i b l e a c c o r 凼n d y ，仃a c k i n gm 嘶n go b j e c 馏i i lm ec o n 璐p o n d i i l gp o s i 石0 nh 髂b e c o m e i l l c r e 罄i l l g l yf e 嚣i b l ea n dn e c e s s a 彤s ow en e e ds o m em d e 五n gs t m 弧鹏1 a th 鹬h i 曲 娟c l e n c y t ol o c a t em ep o s 衔o n so fi i l o v i n g o b j e c t s h o w e v e l d i et m d i t i o n a l s p 积鑫【t e m p o r a li n d e x i n g 圭e c h n i q u 髓奴r n o v i n go b j e c t sc a nn 。ts i m 越t 缸e o u s i y 硒d 嘶c ，e n t l ys u p p o r tt l l eq u e f yd b o u t 血ep 峨p r e s e n ta l l d 缸u r ep o s i 6 0 n so fm o 、五n g o b j e c 忸，t l l i si si i l d u c e db yt l l ec o m p l e ) 【i 够o ft l es p a l i a ld 砒a 锄dt l l ec 呻痂ca t m b u t e o f t h em o “n go b j e c t s t h et e b x ( 面姗e n 仃0 p yb x ) r n i x e di n d e ) ( 1 n gs t r u c t u r ep r o p o s c di nt 量l i s p a p e r ， w i l i c hb e i n gi 哪p r a v e db a s e do nm eb 巾i i l d e x i n gs 臼1 l c t e 跚da d d i n gt h eh a s h 砌l l a 巧i n d e x t a b l et os u p p o nt 量l e 丘_ e q u tu p d a ：t eo fm o v i n go b j e c 协，c a i le m d e n n y s o | v et l l ep r o b l e mp r e s e f i t e da b o v e ns i m p l i 丘e st l l e 访d e ) d n gk e ”o r di i lo r d 盯幻 i l l c r e 勰em ei l l d e ，d n gt e ：m 1 砷r a ls p a i l ，趾d 唧r s 舒t h ep o s i t i o n so f 册v i j n go b j e c 协b y l i s l n g 血el i n e a rf i m c 曲no fn m e ，i tc 觚岫d 麟吐l ep o s m o 船o f 【n o 讥n go b j e c t s 缸吼 p a s tt dm t l l r e ；a tm es 锄eb m e ，m ei l l d e x i l l gs 仃u c t i i r ei i l n 硼u c e st l l e6 m ee n 仃d p yf b r d 髓。血gt h ed e c r e 船i 1 1 9m e 投i r e n l e i l to fm ep o s i t i o n a li n f 0 珊a l i o no fm o 、，i l l go b j e c 协 i i ld a t a b 鹊e 罄矗m ei n c r e a s i n 吕i tc 趾t e r i i l l yp 砌et i l o s ep o s i 石o l l a li 1 1 白m l a t i o no f m o v l n go b j e c 忸w 量l i c hb e i l l gs c o r e db e y o n da 出f i r i i t ep e i j o d ，a i l dn l a i n t a i nt 1 1 ei i l d e ) 【i l n g 咖l c 眦o na s t e a d ys i z e 幻i i n p f o v em e 访d e 妇c a l 缅c i e n c yo f 也es y s 锄n t h et e b - i i l i x e dj n d e ) ( i n g 蛐n j c t i l r es 幻r 血ep o s 协。邺o f 诟n go b j e c 姆i na b + 一缸e ef o 嘲，i tc 觚e 伍c l e n t l ys 印p o r tt l l eq u e 叮a b o l i tm ep 鹪t p r e s e n t 锄df l l m r e p o s i 乜0 n so fm o v i n go b j e c t s ；i ta l s os u p p o r t s 吐l es p a l i a l 一把m p o r a l 聊培q u e r y 谢血t 量i e l a r g e rn e t r i p o r a l 印a l l 锄dt h eq m d 嚣t l l a ts e i e c to b j e c t sb 勰e d 伽t e m p o f a j 缸ds p a t i a l 1 1 s t r a i n t s ，s u c ha sq u e r i e st h 砒r e 岫e v ea l lo b j e c t sw h o s ep o s i d o n s 纠l 埘d 妇as p 撕a l f 锄g ed 埘n gas e to f 在m ei n 钯a l sa tt l l es a m e 五m e ；c o n l p a r e dm mt l l eb 。m e e i n d 两n gs t 】1 咖r e ，b e c a u s et l l eh a s ha i 】) 【i l i a r yi n d e x - t a _ b l ei l l t r o d u c e db ym e 山东大学硕士学位论文 t e b x i i l i x e di l l d e 妯gs t n l c t t l r ec 锄e m c i ys u p p o r tt i l eb o t t o m 加印p 矾a li l p d a t e s 仃a 主e 窖孔i ta l h 罄h i g h e ri l l s e n i o i l ，d e l e d 锄di l p d a l i l l ge f f i c i e n c y h o v i n g0 b j e c t s ：t e b 。一m i x e di n d e x ：t i 咐e n t r o p y ：h a s h u x j ii a r y i n d e x t a b l e i i i 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究所取得的成果。除文中已经注明引用的 内容外，本论文不包含任何其他个人或集体已经发表或撰写 过的科研成果。对本文的研究做出重要贡献的个人和集体， 均己在文中以明确方式标明。本声明的法律责任由本人承担。 论文作者签名：型垫车 日期： 竺1 2 ：# 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定， 同意学校保留或向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅；本人授权山东大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其他复制手段保存论文和汇编本学位论 文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：兰l 监导师签名日期：幽：f 牛 山东大学硕士学位论文 1 1 研究背景及意义 第1 章绪论 自上个世纪9 0 年代以来，越来越多的用户开始拥有各种便携的计算设 备，小一点的如掌上型的个人数字助理( p e r s o n a ld i 西t a l a s s i s t 融t ) 或者个人通 讯器( p e r s o n a lc o m m u n i c a t o r ) ，大一点的如装备较大内存和较强处理能力的笔 记本电脑等，统称为移动计算机( m o b i l ec o m p u t e r ) 。据有关资料介绍， 1 9 9 3 年大约4 0 的美国商用p c 机销售量都是移动计算机。随着便携计算设备的日 益普遍，人们迫切需求能在任何时候、任何地点、通过任何方式来接收信息， 查询和处理数据，而此时迅速发展的无线通信技术和空间定位技术为之提供 了手段。目前笔记本电脑可以通过安装无线网卡来实现移动上网，随着全球 定位系统( g l o b a lp o 鳓o i ls y s 钯m ，简称g p s ) 定位精度的提高和成本的下降， g p s 设备也得到了广泛的应用。可以预见，移动计算即将成为趋势和现实。 在移动计算环境下，计算机不再有固定的位置和网络地址。更重要的是，它 同时引发了一类新的应用一一移动对象数据的管理和应用。在移动计算环境 下，移动对象是运动的主体。为了实现对移动对象的位置信息进行有效的管 理，处理与移动对象有关的查询，“移动对象数据库”的概念应运而生，并 且成为一个新兴的热点研究领域1 1 0 j 。 空间位置或范围随着时间的变化而变化的空间对象称为时空对象 ( s p 瓶a l - t e m p o r a lo b j e ，又称为移动对象，在本文里特指那些具有自定位功 能对象( 如装备g p s 的汽车，移动通讯工具等) 。移动对象数据库【4 “1 ( m o v i n g o b j e c td a t a b 嬲e ，简称m o d ) 是对移动对象的位置及其相关信息进行表示和管 理的，它是数据库研究领域近年来发展起来的一个分支。 移动对象数据库记录了不同的移动目标在不同时刻的位置，用户可以在 数据库中查询移动目标的过去、现在和将来某一时刻的位置信息。移动对象 数据库可以用于民航管制、交通管理、军事指挥、物流调配、基于位置的信 息服务等众多领域。例如，出租汽车公司可以根据5 分钟后车辆可能的位置 山东大学硕士学位论文 进行车辆调度，移动运营商可以向用户提供基于位置的广告或电子优惠券， 交通管理机构可以根据本地道路状况给车辆提供道路拥挤状况来避免交通 堵塞。 上面所提的是己经或是将要出现的典型的移动对象数据库应用，应用的 查询发出者可以是正在移动的对象，也可以是处于静态的用户，这些应用都 是传统数据库技术难以有效支持的，因此研究移动对象数据库是非常必要 的。对移动对象数据库进行开发时，不仅需要考虑移动对象的运动模型，还 要考虑移动对象的位置更新频率、移动对象数据库索引、移动对象数据位置 的管理和查询等众多问题n 引。 移动对象数据库管理系统的一个主要功能是支持对时空对象的高效查 询操作，如：查找3 0 分钟以前通过某地段的车辆，查找在未来l o 分钟内客车 能到达的最近的餐馆等。在移动对象数据库系统中，通常管理着数量非常庞 大的移动对象数据。在查询处理移动对象的位置信息时，如果逐个扫描所有 的移动对象数据显然会极大地影响系统的性能，为了减小搜索空间，就必须 对移动对象数据建立索引。 索引机制是保证对移动对象数据进行有效存取的关键技术，移动对象的 索引技术1 4 ，”是一个充满挑战性的研究领域。它对移动对象数据库模型的设计 与建立、移动对象数据库管理系统的开发研制，特别是对移动对象数据库查 询语言以及真正的移动对象数据库管理系统层次的研究等方面都具有重要 的影响。 1 2 国内外研究现状 1 2 1 移动对象位置建模的研究 目前广泛采用的位置建模方法是由美国1 1 1 i n o i s 大学芝加哥分校的 o i l r iw o l f s o n 及其研究小组提出的m o s t ( m 0 v i n g0 b j e c ts p a t i a 卜t e m p o r a l ) 模型“1 。它引入了动态属性的概念，动态属性将移动对象的位置表示为时间 的函数，即l o c a t i o n = f ( t ) ，系统可根据该函数计算出移动对象在将来任一 时刻的位置，移动对象无需周期性地报告当前位置，只在实际位置与计算位 2 山东大学硕士学位论文 置的偏差达到或超过一定阈值时，才对对数据库进行更新。这种方法降低了 数据库的更新开销，减轻了网络负担。 1 2 2 移动对象索引技术研究现状 对于一个数据库系统而言，一项根本任务就是信息的检索查询，移动对 象数据库也不例外，能否快速的检索信息是评价移动对象数据库性能高低的 一个主要的标志，而检索性能主要取决于数据库系统的索引机制。移动对象 数据库于1 9 9 7 年被提出，至今为止，国内外对其索引技术的研究还处于初级 阶段，提出的几种索引结构主要表现为基于传统时间索引方法的扩展，或者 基于空间索引方法的扩展f 9 】，也有少数的索引结构综合了空间索引技术和时 间索引技术。 现有的移动对象数据库索引方法，一类是针对移动对象历史信息数据库 建立索引，也就是移动对象历史信息的索引方法：另一类是针对移动对象当前 信息数据库建立索引，也就是移动对象当前和未来信息的索引方法。 对于移动对象历史信息的索引，主要有两类方法。一类是把对象在d 维 空间中的运动，加上时间维，转换成( ( 1 + 1 ) 维空间中的轨迹来描述，对象的移 动变化意味着在原来轨迹的末端插入新的线段。另一类方法是对移动对象按 区域索引，空间被划分成若干区域，索引中记录的是对象在某个区域的起始 时间，从索引中可以快速找到某时刻或某时间段位于某区域的对象，如果需 要得知对象的确切位置，再进一步细查。 下面是前人提出的几种有关移动对象历史信息索引的方法： ( 1 ) s 1 r 树和t b 树2 0 0 0 年d p f b r ，c s j e l l s 锄和y t h e o d o r i d i s 提出两种 存取方法s t r 树( s p 撕o t e r n p o r a lr - 仃e e ) 和t b 树( t r a j e c t d r y b i l d l e 仃e e ) 1 1 1 。 在这两种树的索引结构中，忽略了空间对象的空间临近性，把属于同一个移 动对象的轨迹信息放在同一个叶子结点当中，因而在移动对象轨迹的查询方 面其性能要优于传统的r 树系列，但在空间范围查询方面的性能却下降了。 ( 2 ) m v 3 r 树2 0 0 1 年y 1 幻和d ，p 印a d i 觞提出了一种树的复合结构多版本 3 d r 树m v 3 r - 订e e l l 2 1 ，这种树结构将多版本的r 树和3 d r 树相结合，可以 较好地索引移动对象的历史轨迹。 山东大学硕士学位论文 ( 3 ) 自适应的索引方法人民大学的孟小峰等人在文献【1 3 ，1 4 】中对移动 对象数据库的模型和索引方法进行了深入的研究，提出了一种自适应的索引 方法，实现了提供动态导航服务的模拟系统，并对采用的道路网络索引进行 了性能分析。 ( 4 ) s e l i 索引结构2 0 0 3 年：c h a l 【k 瘌ae v e r s p a u 曲提出了一种新的移 动对象轨迹索引机制s e l l ( s c a l a b l e 锄de m c i e n tt r 匈e 咖h i d e x ) ，这种索 引机制可以减少空间索引和时间索引的搜索次数和更新代价，并通过实验证 明s e l l 在时间区间和时间片方面的查询性能胜过3 d r 树和t b 树。 对移动对象当前和未来信息的索引。主要有三类方法。第一类方法是用 时空轨迹来表示移动对象的运动。时空轨迹是时空中的一条曲线，以在二维 平面( x ，的上运动的一个移动对象为例，它的轨迹就是( ) ( y ：t ) 空间里的一条 曲线或直线，其中t 是时间轴。这条曲线上的点( 墨y t ) 表示在t 时刻，该对象的 位置是( ) 【，y ) 。如果这条轨迹可以用一个曲线方程来表示，那么只要记住曲线 方程，就可以知道对象在任意时刻的位置。如果无法得知曲线方程，通常用 折线近似的代替曲线来表示对象的轨迹，如图l 所示。这样，一条轨迹可以 被划分成若干直线段，每段( 称为“轨迹片段”) 都对应一个简单的直线方程， 对轨迹的索引就转化成对所有轨迹片段的索引。 y x 图1 时空轨迹 第二类方法是基于i i o u 曲变换的表示方法。对于一个沿x 方向匀速运动 的移动对象，其轨迹是( t x ) 平面上的一条直线，可以表示为x = 卅a ，其中v 是斜率，也就是该对象运动的速度，a 是x 轴上的截距：这条线在( 、a ) 平面( 其 中v 表示斜率，a 表示截距) 中用一个点( v ，a ) 就可以表示，如图2 所示。( t x ) 被称为“初始空间( p r i m a l ys p e ) ”，而( v a ) 被称为“对偶空间( d u 8 ls p a c e ) ”。 将初始空间中的一条直线转化成对偶空间中的一个点，就是壬五o u g h 变换。通 过这种变换，对移动对象轨迹的索引就转变成对二维空间中点的索引。 山东大学硕士学位论文 x a 0 a a 0 vy ( a ) 初始空间 c b ) 对儡空间 图2h 0 u 曲变换 第三类方法是将移动对象看作d 维空间中的移动点，借鉴空间索引技术 对移动对象当前位置建立索引，对象的将来位置通过运动函数计算得到。 目前。在对移动对象的当前和未来信息建立索引这一领域中。主要有以 下几种方法被提出： ( 1 ) p m r 四叉树索引结构【1 6 11 9 9 8 年j 1 匆曲和o u l u s o y 首次提出了移动 对象的索引方法，可以对移动对象的未来位置进行索引。这种方法将索引空 间分割成四部分，采用p m r ( p o i r i tt om 铭hr e n d e 渤g ) 四叉树来索引移动对象。 假设移动对象在d 维空间运动，通过加入一个时间维，将移动对象的未来轨 迹转化为d + l 维空间的线来索引，然后通过移动对象动态属性的时间函数有效 地进行未来位置的预测。然而这种方法需要不断的存储线信息，从而可能会 导致过量的存储，造成存储空间的浪费。 ( 2 ) h o u 曲转换和髓树索引1 9 9 9 年g ，k o l l i o s 和d g u l l o p l l l o l l s 提出了在 一维和二维空间中索引移动对象未来位置的方法”，此方法采用h o u 曲转换 将移动对象的轨迹在更高维空间中映射成点，然后采用m 树的点存取 方法和多个b + 树脚川的方法进行索引。但是这种索引结构不能够扩展到高维 空间，具有很大的局限性。 ( 3 ) 像树 2 0 0 0 年s s a l t e l l is c s 翩和s t l e u t e g g e r 提出了一种r 树 唧的扩展树：t p r ( t i m e p a r 锄e t e r i z e dr - t r e e ) 树吲，它是一种以时间为参数 并且能够存储动态目标的索引结构，可以将所有基于m o s t 模型的移动对象 进行存储，树中的各个结点都是一个以时间为参数的表达式，可以有效地表 示移动物体的方向和速度。这种方法在原始空间索引数据，采用速度矢量将 索引结构参数化，使得未来任何时刻的索引结构都能被得出，是一种非常直 观的索引技术，适合于对一维、二维、三维空间的数据进行索引，不需要对 山东大学硕士学位论文 其进行频繁的索引重建，与目前提出的其他方法相比，具有较为突出的优越 性。 ( 4 ) r 树改进型 2 0 0 1 年s s a l t e l l i s ，c s j s 髓对t p r 树这种索引结构作 了改进，在此基础上专门针对过期数据的处理提出一种r e ，树索引结构， 更好地改善了这种索引结构的查询性能。2 0 0 3 年彭大芹栅r 树又做了一些 改进，提出了保守的时参范围矩形幽，实现了对活动在( 或可能活动在) 某区 域内的移动对象的快速查询。 f 5 ) b 树索引结构2 0 0 4 年c h r i 如缸s j e i l s 等人提出的b 。树索引结构 使用b + 树存储移动对象的位置相关信息，通过空间填充曲线和时间划分技术 将多维空间中离散的点连接起来，确保在多维空间中邻近的点映射到一维空 间中也邻近。该索引结构具有很高的查询和更新性能，能较好地解决移动对 象的当前、将来位置查询，并支持有效的范围查询和k n n 查询。 但以上索引结构要么只能有效地索引移动对象的现在、将来的位置，要 么就是主要用来索引移动对象的过去、历史的位置。还没有一种时空索引技 术能同时有效地支持对移动对象的过去、现在及将来位置的索引，这将不能 很好地满足现实生活中的某些具体需求，例如：“查询某一辆出租车在三个 小时以前去过什么地方；现在又处在哪里：在接下来的一个小时将会去哪儿” 等等。 1 3 论文的主要研究内容 上文提到的c l l r i s t i 锄s j e n s e r i 等人提出的b x 树索引结构由于引入了空间 填充曲线和时间段划分技术，能较好地解决移动对象的当前、将来位置查询， 并且有较高的查询与更新效率，但是它却不能有效支持对移动对象历史信息 的索引。 为了能够有效地支持对移动对象的过去、现在及将来位置的索引和提高 移动对象数据库查询与更新效率，本文在对大量中外文献进行研究分析的基 础上，针对上述问题，我们在b x 树的基础上提出了一种改进的移动对象索引 结构一一t e b 混合索引结构。它继承了b 5 树索引移动对象当前和将来位置的 能力，同时扩展了对移动对象历史位置的索引能力：它较好地降低了对象的 山东大学硕士学位论文 更新和维护代价，提高了查询效率。本文重点探讨了t e b 混合索引结构的数 据结构以及相应的查询和更新算法；同时引入了一种新型的时空查询一一时 间和地点受限的集合查询及其算法；最后通过实验x 寸1 _ e b x 混合索引结构进行 了性能分析和评价。 本文主要从以下几个方面进行了理论创新和研究： 扩展了b x 树索引结构，提出了包含有h a s h 辅助索引表的混合索引结构； 吲入时间熵的概念，可定期清除过期的对象信息，维持索引结构的规模 稳定； 弓i 入了新型的移动对象查询类型( 时间地点受限的集合查询) 及其算法。 1 4 论文的整体结构 全文共分五章。 第2 章主要介绍了一些有关移动对象的基础理论，包括移动对象的分 类与表征、移动对象数据的相关属性特点、移动对象数据库查询的类型以及 一种空间数据映射的技术一一基于空间填充曲线的z 、w u e 技术。 第3 章首先介绍了当前存在的一种具有较高查询和更新效率的移动对 象索引结构b 树，并且指出了它的不足之处：接着在此基础之上，重点论述 了我们提出的一种改进的高效移动对象索引结构一一t e b 混合索引结构，它 可以有效地索引移动对象的过去、当前和将来某时刻的位置信息，同时它 也具有很高的查询和更新效率。然后详细介绍了基于t e b l 混合索引结构的各 种查询算法，包括历史查询、未来预测查询、当前的时空范围查询及本文新 提出的时间地点受限的集合查询。最后阐述了基于! b 。混合索引结构的插 入、删除及更新算法和他们的优点。 第4 章首先就t e b 索引结构和州3 r 树对于移动对象历史位置信息的索 引性能迸行了对比分析：接下来对比分析了t e b l 索引结构与b 1 树对于移动对 象的当前和将来位置信息的索引性能；最后，通过实验具体地验证了t e b l 索 引结构对移动对象的历史查询、预测查询、时间地点受限的集合查询和更新 的性能代价，并对相应的情况进行了理论分析。 第5 章总结全文工作并提出进一步研究的方向。 山东大学硕士学位论文 第2 章基础理论与相关技术 2 1 移动对象的分类与表征 移动对象有狭义和广义之分。狭义移动对象是指对象的位置或范围随时 间不断的发生改变的空间对象，也就是指运动的对象，如在飞行的飞机、高 速公路上行驶的小汽车、随着时间的变化其边界范围在扩大或缩小的森林等 等。广义的移动对象是指含有不断变化的属性的数据对象，不特指对象的运 动。也就是说，静止的对象如果含有不断变化的属性，也可以用移动对象的 方法进行管理。比如，房间的温度随着时间而发生变化，房间为静止对象， 而温度为静止对象不断变化的属性。本文的研究是针对狭义移动对象进行 的。 按照对象的运动速率分，狭义移动对象可以进一步分为连续变化的移动 对象和离散变化的移动对象。高变化率的移动对象，如汽车、轮船、飞机等 称为连续变化的移动对象。低变化率的移动对象，如办公室里的人称为离散 变化的移动对象。本文的研究是针对连续变化的移动对象。 移动对象数据库存储的是随时间变化的空间对象。在空间数据库中定义 了的三种基本空间对象：点i i l t s ) 、线( 1 i n 器) 和区域( r 画o n s ) 。点表示空间 范围为零或只关心其空间位置，而不是它的大小的空间对象，例如在一张大 比例的地图中的一个城市；线即空间曲线，可描述在空间中移动的设施或者 空间连线，例如道路、河流、电话线、电线等；具有一定空间范围的对象称 为区域，例如一个国家行政区、一片湖泊等。因此，目前对移动对象的表征 主要使用移动点( n l o v i n gp o i n t s ) 和移动区域( n l o v i r i gf e 画o n s ) 这两种基本空间 对象类型，由于线( 曲线) 本身就是运动的抽象或者投影，可转换为对移动点 轨迹( 打a i e c t o r y ) 的描述。 2 2 移动对象环境的特点 移动对象诞生于移动计算的环境下，与传统的基于固定网络的分布计算 环境相比，移动计算环境具有其自身的一些特点矧。本文这里只阐述与移动 山东大学硕士学位论文 对象管理相关的一些主要特点： ( 1 ) 移动性在移动计算环境下，移动对象可以随意移动，并在移动的同 时保持网络连接。 ( 2 ) 大规模性许多移动应用环境，如交通运输系统和移动电子商务系统 等，都要求系统管理数目较多的移动用户，同时支持大量的移动用户并发访 问，这就要求移动对象管理系统具有查询和维护的高效性。 ( 3 ) 频繁断接性由于无线网络的不稳定性、移动设备的电源能力、无线 通信费用昂贵等因素的限制，移动用户一般不采用持续连接入网的方式，而 是采用间断性的入网，然后主动断接。 ( 4 ) 网络条件多样性在整个移动环境下，不同区域的网络条件是变化多 端的，网络的多样性决定了移动数据管理方式和数据通信方式的多样性。 ( 5 ) 网络通信的非对称性物理通信媒介的限制决定了无线网络通信下 行链路和上行链路之间在带宽和代价方面的巨大差别，这就决定了在进行移 动数据管理时需要采用移动的通信和管理机制。 + ( 6 ) 不可靠性无线网络与固定网络相比，可靠性较低，更容易受到干扰 而出现网络故障。这就决定了移动数据管理需要对此有相应的处理。 2 3 移动对象数据的特点 2 3 1 移动对象时间维的特点 移动对象数据库可看成是空间数据库在时间维度上的扩展，在分析移动 对象数据时应考虑到其时间维的特点： ( 1 ) 时间信息的变化总是单调递增的； ( 2 ) 在时间数据库中，定义了有效时间和事务时间两个时间维度，移动对 象数据库应有效支持有效时间、事务时间或双时间： ( 3 ) 数据库的主要目标是准确反映现实世界，空间对象随时间的递增，其 变化频率的快慢决定了数据库表示移动对象数据的方式，可分为离散和连续 两种情况。 9 山东大学硕士学位论文 2 3 2 移动对象数据的空间属性 移动对象数据具有空间数据的特点，不同的是空间数据是静止的而移动 对象数据是不断变化的。移动对象数据中包含带有空间坐标信息的数据，这 些数据用来表示移动对象的空间位置和与空间的相对关系。移动对象的空间 属性具有以下特点： ( 1 ) 不可排序性对于多维空间中的移动对象数据无法建立一个可以反 映其邻近性的排序，即无法找到一个从多维空间到一维空间的映射f ，使得多 维空间的任意两点v l 、v 幺满足f 1 ) 、f ( 、，2 ) 相邻当且仅当v l 、v 2 在空间上相 邻。 ( 2 ) 相关性一个移动对象可能是点( 如汽车) 或区域( 如洪水) ，一个n 维的 移动对象至少在其中的一维上覆盖一个区间，而且一个移动对象数据库里的 数据量通常是很庞大的，这使得移动对象问有可能相互重叠，也就是移动对 象间存在一定的相关性。 ( 3 ) 数据复杂性在现实世界中，移动对象的空间分布是不均匀的，大小 也可以是多种多样的，所以移动对象在计算机中的表示比较复杂。由于移动 对象不断的运动，它的空间位置的判断也较复杂。 研究移动对象数据的特点主要是研究如何建立移动对象的索引。移动对 象数据含有空间数据的特点，因此目前建立的移动对象索引主要借鉴空间索 引技术，如r - 树明。四叉树口”，网格索引【矧，k - d 树o ”，k d b 树0 1 1 等。空间 索引技术结合上时间因素可以完成对移动对象的索引。 2 4 移动对象数据库的分类 只管理对象历史信息的数据库称为移动对象历史信息数据库。移动对象 历史信息数据库中存放移动对象的历史数据，如对象在过去任意时刻所在的 位置，通常移动对象历史数据库中可以不必存储对象的运动函数。对移动对 象历史数据建立的索引称为移动对象历史信息的索引方法。移动对象历史信 息数据库通常用于需要查询对象过去位置的领域，如公安、交通部门等。 只管理对象当前信息的数据库称为移动对象当前信息数据库。移动对象 山东大学硕士学位论文 当前信息数据库中存放移动对象的当前数据，其中包含对象当前所在的位置 及对象的运动函数，根据运动函数可以预测对象将来的位置。对移动对象当 前数据建立的索引称为移动对象当前和未来信息的索引方法。移动对象当前 信息数据库通常用于对移动对象当前和未来位置较为关心的领域，如人们生 活中需要这样的信息：在车辆行驶到前方某路口时，该路口是否会出现堵车。 有的应用中既需要查询对象当前和将来信息，又需要查询对象的历史信 息，也就是移动对象数据库中既需要存放对象的历史数据，又需要存放对象 的当前数据，本文称这样的数据库为移动对象双时态信息数据库。对移动对 象双时态信息数据库建立的索引称为移动对象双时态信息的索引方法。本文 中我们提出的新的索引方法则可以有效地支持对移动对象双时态信息的相 关索引。 2 5 移动对象数据库查询类型 对移动对象数据建立索引的目的是为了有效支持各种移动对象查询，所 支持的查询集越宽，移动对象存取方法就越有价值。目前针对移动对象的查 询，大体可以分为以下四类。 ( 1 ) 点查询( p o i mq u e r y ) 点查询可分为两种：查询某时刻位于某地的移 动对象和查询移动对象在某时刻的位置。 ( 2 ) 范围查询( r a l l g eq u e i y ) 查询某时刻或某段时间内在或者不在某个 地理范围内的移动对象。范围查询是最基本的移动对象查询类型，包括时间 范围查询，空间范围查询和时空范围查询。 ( 3 ) 最近邻居查询( n e a 贼t - n e l 班b o rq u e r y ) 查询某时刻或者某段时间内 距离某地最近的移动对象，或者查询距离某移动对象最近的静态对象( 如加油 站、医院1 。 ( 4 ) 连接查询( j o i i lq u e r y )查询某时刻或者某段时间内满足定连接条 件的一对移动对象。例如：查找某时刻距离在l 公里之内的两辆警车。连接 查询往往涉及两个或两个以上的表之间的连接操作，它往往将某一范围中的 所有实体与另范围中的所有实体进行比较。这点与范围查询不同，范围查 询中，只是通过一个查询窗口来与某一范围中的所有实体作比较。 山东大学硕士学位论文 另外，还有历史查询、时间片查询、综合查询等等其他一些查询类型， 复杂的移动查询一般是上面四种基本移动对象查询类型中的一种或者几种 的组合。针对移动对象的查询有以下两个特点： ( 1 ) 查询结果取决于被查询对象自身的运动如果某个对象( 对于连接查 询，则是某两个对象) 的运动满足查询条件，这个对象就属于查询结果，而不 受其它对象运动的影响。 ( 2 ) 查询条件包含空间和时间两方面的约束由于移动对象的位置随时 间不断变化，因此基于位置的查询结果根据查询条件中不同的时间约束而有 所不同。 2 8 空间填充曲线( s p a c ef i li n gc u r v e ) 和z _ v a l u e 技术 2 。6 。1 空间填充曲线 空间填充曲线旧的设计思想是希望找到某种方法对多维空间中的数据 进行近似的排序，使得原来在空间中较为接近的数据能在排序后以比较高的 概率靠在一起，再使用一维数据索引方法进行存取。根据这样的思路，人们 提出了几种将多维空间中的点数据映射到一维空间并进行排序的方法，如z 排序、琢l b e f t 码排序等。 空间填充曲线具有如下的拓扑性质例：能够且仅访问k 维栅格中的所有 的点一次。而且不与其本身交叉。空间填充曲线所经过的路径对空间中的点做 了线性排序，空间中的点既可以由它的三个空间坐标来表示，也可以通过测量 从一个端点开始的线长度确定。通过对各种填充曲线的实验比较，巧l b e r t 曲线 可以获得最佳的聚类效果【3 4 】。基本硒l b e r t 曲线是一个大小为2 2 、阶数为l 的栅格曲线，用h 1 表示，如图3 所示。为了获得i 阶碰l b e n 曲线，则将基本碰l b e r t 曲线的每个顶点由“l 阶碰l b e r t 曲线所代替，同时i 1 阶碰l b e n 曲线可以进行必 要旋转或反射来适应新曲线p 扪。图3 也示例了2 阶和3 阶碰1 b e r t 曲线。 山东大学硕士学位论文 兀驰嚣 砒舷 图31 阶、2 阶和3 阶毗l b e r t 曲线 在曲线h 2 中，点( o ，o ) 的毗l b e r t 值为o ，点( 1 ，1 ) 的h i l b e r t 值为2 ，而矩形 h i l b e r t 值需要自定义。根据实验比较结果，一个比较好的矩形h i l b e r t 值定 义为：矩形h i l b e r t 值设定为矩形中点的h i l b e r t 值。下面给出二维坐标点的 h i l b e r t 值的计算方法。 阶数为n 的碰i b e n 值算法实现步骤如下： ( 1 ) 将坐标( ) ( ，y ) 转化为长度为n 的二进制表达形式； ( 2 ) 将二进制形式x 、y 按位相互交叉，构成一个长度为2 n 的二进制串s ； ( 3 ) 将串s 从左到右按每两位分开，形成二进制串s i ( i = l ，柚： ( 4 ) 按照如下的形式，给出每两位二进制所对应的十进制数值 o o o o l l l o 2 l l 3 将十进制数值d i 以与二进制数组s i 相同的顺序存到一个数组d 中； ( 5 ) 对应十进制数组d 中的每一位d i ，如果d i ：o ，则将在此位后出现的所 有的l 转换为3 ，所有的3 转换为l ：如果d i = 3 ，则将在此位后出现的所有的0 转 换为2 ，所有的2 转换为o ： ( 6 ) 将改变后十进制数组d 中的每一位转化为二进制形式，然后计算该 二进制串的数值，即为对应坐标( x ，y ) 的h i1 b e r t 值 山东大学硕士学位论文 2 6 2z - v a i u e 技术 对于一个任意复杂的空间对象，如多边形，一般用它的最小包围矩形 耶r ( m i n i m 岫b o u l l d i n gr e c t a n 9 1 e ) 来近似，如图4 所示。然而，船r 是一种较 为粗略的近似，一个对象往往还需要被近似到比尬r 更为精细的程度。例如， 对于穿越整个数据空间的一条长路来说，它的船r 显然是一种不太合适的近 似。z v a l u e 技术就是基于空间填充曲线，通过将数据空间循环分解到更小的 子空间( 被称为p e a n oc e l l ) 来获得对于给定对象形状的近似。作为一种空 间索引技术，它已经被用于几个商业化的空间数据库系统，例如o r a c l e ”1 。 用z v a l u e 技术将数据空间循环分解到更小的子空间后，让每个子空间 根据分解步骤依次得到一组数字，称为该子空间的z v a l u e 。求解z v a l u e 的 分解过程为：整个数据空间被分为4 个相同大小的子空间，这4 个子空间依照 一定的次序被编号为1 4 。这些子空间能够进一步循环分解和编号。一个子 空间由下列步骤确定其z v a l u e ： ( 1 ) 初始空间的z v a l u e 为1 ； ( 2 ) 一个z v a l u e 为z ( z = z 1 z n ，1 z i 4 ，1 i n ) 的子空间，其4 个子 空间的z v a l u e 分别为z 1 z n l ，z 1 - z n 2 ，z l z n 3 ，z l z n 4 。 由于一个空间对象能够用与它重叠的一组子空间来近似。因此也得到惟 一的一组z v a l u e 。这样，空间对象能够被表示为一组数字( z v a l u e ) ，并能够 从该组数字中得到相应的近似空间信息。子空间有不同的大小，z v a l u e 有不 同的长度，显然，子空间越大，相应的z v a l u e 越短。这里，分辨率( r e s o l u t i o n ) 是指最大的分解层次，它决定了z v a l u e 的最大长度。图5 中的多边形可以由7 个子空间近似，其分辨率是4 。这样，通过z v a l u e 我们可以将一个两维对象转 换为一组一维点( z v a l u e ) ，并且能确保在多维空间中邻近的空间对象映射 到一维空间后也邻近，因此可以用常见的一维访问方法，如b + 树来维持。 山东大学硕士学位论文 图4 最小包围矩形她r 2 7 本章小结 图5z v a l u e 对多边形韵近似 移动对象可以分为狭义移动对象和广义移动对象，本文的研究工作是针 对狭义移动对象。按照变化速率分，狭义移动对象还可以进一步分为连续变 化的移动对象和离散变化的移动对象，本文的研究工作针对的是连续变化的 移动对象。移动对象数据含有空间数据的特点，因此目前建立的移动对象索 引主要借鉴空间索引技术；同时，移动对象数据还具有时间维上的一些特点。 根据不同的应用需求和管理的数据特点，移动对象数据库可以分为移动对象 历史信息数据库、移动对象当前信息数据库、移动对象双时态信息数据库。 移动对象数据库的查询，可以分为点查询、范围查询、最近邻居查询和连接 查询四种类型。最后介绍了空间填充曲线及基于它的z v a l u e 技术，为下一 章介绍b 树索引结构及本文提出的改进的移动对象索引结构打下基础。 山东大学硕士学位论文 第3 章改进的移动对象索引结构一t e b i 当前已存在的时空索引技术p 1 】要么只能索引移动对象的当前、将来的 位置，要么主要用来索引移动对象的过去、历史的位置，但还没有一种索引 技术能同时有效地支持对移动对象过去、当前及将来位置的索引。本文提出 的t e b x 混合索引结构能有效解决上述问题，并且具有