（计算机软件与理论专业论文）基于kdtree的移动对象索引研究.pdf

中山大学硕士学位论文基于k d - t r e e 的移动索引索引研究 基于k d t r e e 的移动对象索引研究 专业：计算机软件与理论 硕士生：石敏 指导老师：叶小平副教授 摘要 长期以来，时态数据库和空间数据库作为数据库中两个重要的研究领域是相 互分离的，然而现实世界中许多实体都同时具有时问特性和空间特性，因此时空 数据库在时态数据库和空间数据库的基础上发展起来了。 时空数据库可以处理带有时间和空间特性的数据，相对于传统关系数据库的 一个突出特点就是数据量大，数据更新频繁。而随着移动计算、全球定位系统等 相关技术的发展，时空数据库得到了进一步发展，出现了移动对象数据库。移动 对象数据库需要存储和管理大量现实世界中的带有时空信息的对象，即形状和位 置随时间变化而变化的空间对象信息。为了快速有效地对数据进行查询和更新， 这就需要通过索引机制来管理数据，而这一技术已成为时空数据库研究的焦点。 在现有的索引方法中很多方法都是将时间维看作空间维，以便利用比较成熟的空 间数据库索引技术。但时间和空间有着不同的特性，进而可能对系统性能产生较 大的影响。 本文研究并总结了当前移动对象索引技术的优缺点，并在此基础上，研究基 于时间和空间有效整合的移动对象索引技术。即通过将时间和空间分别进行处 理，然后将分别处理后得到的时态索引和空间索引进行有效的整合，进而实现对 移动对象数据的索引。本文首先介绍了移动对象数据库的相关概念和理论，并对 现有的主要的移动对象索引方法进行系统归类。其次在移动对象数据特点的基础 上讨论并提出了有效时间的拟序关系概念，研究了时间线序分枝算法。在此基础 上研究了基于k d - t r e e 的移动对象索引模型k m o i m ，同时，研究了基于k m o i m 的数据查询以及索引更新算法；最后通过仿真实验和比较评估，检验了k m o i m 的可行性和有效性。 关键词：时间拟序关系，空间平面划分，时空整合，移动对象索引 中山大学硕士学位论文基于k d - t r c e 的移动索引索引研究 r e s e a r c ho i lm o v i n go b je c t si n d e xb a s e do nk d - t r e e m a j o r ： n a m e ： c o m p u t e rs o f t w a r ea n dt h e o r y s h im i l l s u p e r v i s o r ：a s s o c i a t e p r o f e s s o rx i a o p i n gy e a b s t r a c t f o ral o n gt i m e ，t e m p o r a ld a t a b a s ea n d s p a t i a ld a t a b a s ea r es e p a r a t e df r o me a c h o t h e r 弱t w oi m p o r t a n tr e s e a r c ha r e a s ，h o w e v e r , t h e r ea r er m n ye n t i t i e sb o t hh a v i n g t h et i m ec h a r a c t e r i s t i ca n ds p a t i a lc h a r a c t e r i s t i ci nt h er e a lw o r l d ，t h e r e f o r e s p a t i o t e m p o r a ld a t a b a s ed e v e l o p so nt h eb a s i so ft e m p o r a ld a t a b a s ea n ds p a t i a l d a t a b a s e s p a t i o - t e m p o r a l d a t a b a s ec a nh a n d l ew i t hd a t a h a v i n gt i m ea n ds p a t i a l c h a r a c t e r i s t i c s , a so p p o s e dt oat r a d i t i o n a lr e l a t i o nd a t a b a s ew i c hap r o m i n e n tf e a t u r e o fl a r g ev o l u m e so fd a t a , f r e q u e n t l yu p d a t i n g w i t ht h ed e v e l o p m e n to fm o b i l e c o m p u t i n g ，g l o b a ll o c a t i o ns y s t e m sa n do t h e rr e l a t e dt e c h n o b g i e s ，s p a t i o t e m p o r a l d a t a b a s eh a sb e e nf u r t h e rd e v e b p e da n dt h e r eh a v eb e e nm o v i n go b j e c t sd a t a b a s e m o v i n go b j e c t sd a t a b a s en e e d st os t o r ea n dm a n a g eal a r g en u m b e ro fr e a l - w o r l d o b j e c t sw i t ht h es p a t i o - t e m p o r a li n f o r m a t i o n , n a m e l y , t h es p a c eo b j e c ti n f o r m a t i o n w i t ht h es h a p ea n dp o s i t i o nc h a n g i n gw i t ht i m e i no r d e rt oq u e r ya n du p d a t ed a t a q u i c k l ya n de f f i c i e n t l y , i tn e e d st h ei n d e xm e c h a n i s m st om a n a g ed a t a , a n dt h i s t e c h n o l o g yh a sb e c o m i n gt h ef o c u so ft h er e s e a r c ho fs p a t i o q e r n p o m ld a t a b a s e a m o n gt h ee x i s t i n gi n d e xm e t h o d s ，m o s to ft h em e t h o d st a k et e m p o r a ld i m e n s i o na s o n eh i g h e rs p a t i a ld i m e m i o ni no r d e rt ot a k ea d v a n t a g eo f t h er e l a t i v e l ym a t u r es p a t i a l i n d e x i n gt e c h n o l o g i e s b u tt i m ea n ds p a c eh a v ei n t r i n s i cd i f f e r e n c e s ，a n dt h u sh a v ea g r e a ti m p a c to i ls y s t e mp e r f o r m a n c e t h i sp a p e rs t u d i e sm o v i n go b j e c t si n d e xw i t ho r g a n i c a l l yi n t e g r a t e st h es p a c e a n dt i m eo i lt h eb a s i so f s t u d y i n ga n ds u m m a r i z i n gt h ea d v a n t a g e sa n dd i s a d v a n t a g e s m 中山大学硕士学位论文 基于k d - t r e c 的移动索引索引研究 o fc u r r e n ti n d e x i n gm e t h o d so fm o v i n go b j e c t s b y p r o c e s s i n gt i m ea n ds p a c e r e s p e c t i v e l y , t h e ni n t e g r a t et h et i m ei n d e xa n ds p a t i a li n d e xe f f i c i e n t l ya n dr e a l i z et h e i n d e xo fm o v i n go b j e c t sd a t a f i r s t l y , t h ep a p e rd e s c r i b e st h er e l a t e dc o n c e p t sa n d t h e o r i e so f m o v i n go b j e c t sd a t a b a s e ，p r e s e n t st h ep r o p o s e di n d e xt e c h n o l o g i e so ft h e m o v i n go b j e c t s ，p r o p o s e st h e c o n c e p to ft e m p o r a lq u a s i o r d e r i n ga n ds t u d i e s 如n d a m e n t a la l g o r i t h mo ft e m p o r a ll i n e a rb r a n c h e s a n dt h e n , t h ep a p e rs t u d i e st h e m o v i n go b j e c ti n d e x i n gm o d e lk m o i mb a s e do nk d t r e e ，a tt h es a m et i m e ，s t u d i e s t h ed a t aq u e r ya n du p d a t em e t h o d so f k m o i m f i n a l l y , b yd e s i g n i n gs o m es i m u l a t i o n t oe v a l u a t et h ei n d e xs t r u c t u r ea n dt h er e s u l t so ft h ee x p e r i m e n ts h o wt h ew o r ki s f e a s i b l ea n de f f i c i e n t k e yw o r d s ：t e m p o r a lq u a s i o r d e r , s p a t i a lp l a n ep a r t i t i o n , i n t e g r a t i n go ft i m e a n ds p a c e ，m o v i n go b j e c t si n d e x i v 本人郑重声明： 论文原创性声明 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表 或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以 明确方式标明。本人完全意识到本声明的法律结果由本人承担。 论文作者签名：屉鲰 日期：加f o 年石月弓日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：乃镯曼 日期：c j 。d 年6 月弓日 导师签名：计j 孚 日期：埘。年易月弓日 中山大学硕士学位论文基于k d t r e c 的移动索引索引研究 第1 章绪论 在本章中，主要介绍本研究课题的研究背景及理论与实际意义。首先介绍了 移动对象数据库的产生与发展，然后指出将索引结构引入到数据库中的必要性， 并介绍了移动对象索引结构的研究现状，最后给出本文的研究思路和组织结构。 1 1 研究背景 上世纪六十年代以来，数据库技术在经历了几十年的发展过程中，其理论和 技术不断成熟并得到了广泛的应用。随着互联网的快速发展和普及，人们可以通 过计算机轻易地获取到大量的数据，如何有效地存储和检索这些有用的数据，就 成了目前计算机应用的一个主要问题，而传统的关系型数据库已经不能满足人们 的这些需求，所以如何进一步改进现有的数据库已成为人们关注的问题。每隔几 年，国际上一些资深的数据库专家就会聚集一堂，探讨数据库的研究现状、存在 的问题和未来需要关注的新技术焦点【t 1 。 1 1 1 移动对象数据库的产生和发展 时间和空间是现实世界中客观实体的基本因素，管理对象时间和空间属性的 数据库分别称为时态数据库和空间数据库。时态数据库是一种能够记录对象变化 历史，维护数据变化经历的数据库系统。时态数据库支持用户自定义时间，有效 时间和事务时i 司t 2 j 。空间数据库是描述、存储和处理空间数据及其属性的数据库 系统。空间数据是某个空间框架中对象的位置信息，常用于表示空间物体的位置、 形状、大小和分布特征等诸方面信息。而同时包含了时态数据和空间数据，并能 同时处理时空对象的时间和空间属性的数据库称为时空数据库( s t d b ) ，然而， 随着移动计算、无线通讯技术和地理信息系统的快速发展和普及，人们迫切需要 能在任何时间、任何地点，通过任何方式来接收、查询和处理所需要的信息。因 此，这引发了一类新的应用移动对象数据的管理和应用。在移动计算环境下， 移动对象是运动的主体，其位置信息不断在更新，然而现存的数据库管理系统不 能够处理连续变化的数据，因为在传统的数据库中数据如果不被修改，它是一直 中山大学硕士学位论文 基于k d - t r e e 的移动索引索引研究 保持不变的，而移动对象的位置随着时间变化而不断地变化。显然，移动对象位 置的频繁更新在传统数据库中是无法实现的。因此，为了实现对移动对象的位置 信息进行有效的管理，处理与移动对象有关的查询，“移动对象数据库( m o v i n g o b j e c t sd a t a b a s e s ，m o d ) 技术 的概念应运而生，并且成为一个新兴的研究热 点【3 4 5 1 。 空间位置或范围随着时间的变化而变化的空间对象称为时空对象 ( s p a t i a l t e m p o r a lo b j e c t ) ，又称移动对象。移动对象数据库是对移动对象的位置 及其他相关信息表示和管理，并提供对移动对象进行查询的数据库【1 ，6 ，7 1 。它是时 空数据库研究领域近年来发展起来的一个重要分支。 移动对象数据库记录了移动对象在不同时刻的位置信息，用户可以在移动对 象数据库中查询移动对象的过去、现在的位置信息并且可以预测将来某一时刻的 位置信息。它广泛地应用在地理信息系统、智能交通系统、军事指挥等众多领域 当中【引。例如，移动运营商可以向用户提供基于位置的广告或电子优惠券，出租 汽车可以根据5 分钟后车辆可能出现的位置进行车辆调度，交通管理机构可以根 据当地道路交通状况给车辆提供相应的道路拥挤状况来避免交通堵塞。 总之，移动对象数据库具有广阔的发展前景，但目前对移动对象数据库的研 究还只处于理论阶段，离具体的实际应用还存在一定的差距。 1 1 2 问题的提出 移动对象数据库管理系统的一个主要功能是支持对移动对象数据的高效查 询操作，如：查找2 0 分钟以前通过北京路的车辆，查找在明天中午1 2 点到达中 山大学的校车等。在移动对象数据库系统中，通常管理着极其庞大的移动对象数 据。在查询处理移动对象的位置信息时，如果逐个遍历所有的移动对象数据显然 会极大地影响系统的性能，为了减小搜索空间，有效地实现对移动对象的查询操 作，就必须引入索引结构。移动对象数据的索引技术研究已经成为移动对象数据 库领域的一个研究热点，到目前为止，已经提出大量的索引方法，其中有三种主 流的移动对象索引方法，即r - t r e e 9 1 及其变形树、q u a d t r e e 1 0 】及其变形树、 g r i d f i l e 】及其变形树。成熟的索引方法都是以这三种主流方法为基础进行不 断地扩展。下一节将对移动对象数据索引的相关基础及现有的一些索引技术作简 2 中山大学硕士学位论文 基于k d - t r e e 的移动索引索引研究 要阐述。 索引机制是保证对移动对象数据进行有效存取的关键技术，通过索引结构可 以快速查询到所需要的信息，移动对象索引技术是一个充满挑战性的研究领域。 索引机制对移动对象数据库模型的设计与建立、移动对象数据库管理系统的开 发，以及真正的移动对象数据库管理系统层次的研究等方面都具有重要的影响。 1 2 研究现状 1 2 1 移动对象轨迹的建模 在移动对象数据库m o d 中，移动对象轨迹线是m o d 中数据管理的基本单 元。而目前，具有代表性的移动对象轨迹模型有两类：移动对象时空( m o s t , m o v i n go b j e c t ss p a t i o - t e m p o r a l ) 模型【1 2 】和移动对象离散数据模型，在m o s t 模 型中提出了动态属性的概念，动态属性将移动对象的位置表示为时间的函数，其 属性值随着时间进行变化。表示为l o c a t i o n = 坟t ) ，系统根据该函数计算出移动 对象在将来某一时刻的位置。m o s t 模型介绍了瞬时、连续、持续查询的思想， 它降低了数据库的更新开销，减轻了网络负担，然而此模型有一定的局限性，由 于简单函数的表达能力有限，因此它只能处理移动对象的当前及不久将来的运动 轨迹，而对较长时间的运动轨迹的表示就显得无能为力了。为了克服这一缺陷， 德国哈根大学g u t i n grh 等提出了移动对象离散数据模型 1 3 , 1 4 , 1 5 】。它通过将复 杂的空间对象及移动轨迹分割为相对简单的离散片段来表示和处理复杂的移动 对象，同时也可以处理连续变化的移动点、线、区域。它能够很好地支持历史查 询，然而对将来查询支持不足。 1 2 2 移动对象索引技术 在移动对象数据库中，存储着大量的数据，如果进行遍历扫描所有的移动对 象数据将会加重系统的负担，为了提高查询性能，有效地实现对移动对象数据的 管理，就必须对移动对象建立索引结构，到目前为止，对移动对象索引方法的研 究仍处于初步的阶段，还需要进一步深入。 在所提出的移动对象索引方法中，根据所支持的查询时间窗口的范围可以分 3 中山大学硕士学位论文基于k d - t r e e 的移动索引索引研究 为三类【1 6 】：移动对象历史轨迹的索引技术、移动对象当前位置的索引技术以及移 动对象当前和将来轨迹的预测索引技术。 移动对象的历史轨迹随着时间变化不断延伸，所以每当移动对象的位置发生 变化，都需要在数据库中记录移动对象的具体位置，这样必然会导致数据库的数 据随着时间的变化线性增长，系统性能下降。为了解决这个问题，人们提出了两 种方法来减少数据库中历史数据的存储【1 2 】：( 1 ) 采样，对移动对象的历史轨迹在 特定时间点上进行采样，然后采用线性插值计算出相邻采样点间的线性轨迹。( 2 ) 函数描述，在数据库中存储移动对象运动轨迹的参数信息( 比如速度、方向等) ， 只有当这些参数发生变化时才对数据库进行更新。基于这两种方案，移动对象历 史轨迹的索引机制可分为三类。 第一类是在现存的空间索引方法加入时间属性。在这类基于传统空间索引的 时空索引技术中，主要处理空间维的索引，其次处理时间维的索引。主要的索引 技术有r t - t r e e 17 1 ，3 dr - t r e e 18 1 ，s t r t r e e 19 1 。其中，r t - t r e e 使用r - t r e e 进行空 间存取，使用t s b - t r e e 2 0 】进行相应的时间存取。在r t - t r e e 中，时间和空间信息 是分开维护的。r t - t r e e 对空间维的查询提供良好的性能，但对时间的查询可能 会延伸到整棵r t - t r e e ，因此性能低下。3 dr - t r e e 把时间看作除了空间维以外的 另一维。它可以支持空间和时间的查询，但是随着移动对象轨迹从某个历史时刻 开始一直延伸到当前时刻，显然移动对象轨迹的m b r 将会非常巨大，造成空间 区域的大量重叠，严重影响查询性能。s t 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 。该类索引方法主要有m r - t r e e 1 7 】、 h r - t r e e t 2 1 1 、h r + - t r e e 2 2 】和m v 3 r - t r e e 2 3 1 。其中，m r - t r e e 采用了在r - t r e e 的背景 下可重叠b t r e e 的思想，它在每个采样时间点上都有独立的r - t r e e ，通过在连续 的r - t r e e 中存储不相同的对象来实现减少存储量。h r - t r e e 与m r - t r e e 非常相似， 它是一种采用重叠技术、将单一版本的结构转换为部分固定结构的高效时空索引 结构。该结构有两级索引，分别是1 ) 用h r - t r e e 对事务时间进行索引，2 ) 用r - t r e e 对每个时间点的空间对象建立索引，并且相邻的时刻只复制位置发生变化的对象 4 中山大学硕士学位论文基于k d - t r e e 的移动索引索引研究 以减少对空间的消耗。h r + - t r e e 则是对h r - t r e e 的存储策略的优化，三种方法都 能有效支持时间片查询，但对时间窗口的查询支持不足，因为在对时间窗口查询 时可能要同时查询多棵相邻的r - t r e e ，因此性能较低。m v 3 r - t r e e 是将多版本的 r - t r e e 和3 dr - t r e e 相结合来索引移动对象的历史轨迹，用m v r - t r e e 处理时间点 查询，用3 dr - t r e e 处理长时间间隔查询。 第三类是主要考虑时间维索引，其次考虑空间维索引。这类方法主要考虑的 是移动对象的轨迹线。主要的索引方法有t b - t r e e t l9 1 、s e t i t 2 4 】和s e b - t r e e t 2 5 】等。 其中，t b - t r e e 完整地保存了轨迹线，其结构类似子r - t r e e 。要求每个叶子结点仅 包含属于同一轨迹的线段，具有良好的查询性能和更新效率。s e t i 基于时间维 无限变化而移动对象的轨迹受限于空间范围的考虑，把受限的空间区域分割成静 态且不重叠的区域，在每个分区下将移动对象的轨迹线段存储在不同分区的 r - t r e e 中。s e b - t r e e 设计思想与s e t i 类似，但具有快速的查询与插入算法。 随着时间的向前推移，移动对象当前位置也在不断地更新，相对来说，检索 移动对象当前位置关键在于如何提高传统空间索引的频繁更新动态性能以满足 动态环境下的应用要求，因此对当前位置信息建立索引更具有挑战性。近年来提 出的方法包括2 + 3r - t r e e l 2 6 1 、2 - 3t r t r e e t 2 r l 、l u r - t r e e t 2 引、b o t t o m - u pu p d a t e s l 2 9 1 和h a s h i n g | 3 0 j 等。2 + 3r - t r e e 和2 3t r - t r e e 的思想类似，都是通过两棵r - t r e e 来 分别索引移动对象的历史和当前轨迹，其中2 dr - t r e e 用来索引当前位置，而3 d r - t r e e 用来索引历史位置。l u r - t r c c 提出了一种延迟更新的策略。而b o t t o m - u p u p d a t e s 的自底向上法扩展了l u r - t r e e 的思想，它比较适合处理移动对象的连续 更新。h a s h i n g 则是基于空间划分的思想，首先静态地将空间划分为可以互相重 叠的区域，然后根据当前位置将移动对象哈希映射到不同区域当中。 在移动计算、位置服务等新兴应用中，需要对移动对象当前及未来位置预测 以提供服务，针对移动对象当前位置查询和未来位置预测的索引是移动对象数据 库领域研究的热点。预测移动对象未来运动轨迹需要存储额外信息( 如当前速度、 运动方向等) ，并使用线性方程来描述移动对象的运动特性。主要的索引方法有 p m r - q u a d t r e e t 3 1 1 、f t - q u a d t r e e l 3 2 1 、t p r - t r e e l 3 3 1 、t p r * - t r e e l 3 4 1 、n s i 3 5 】和p s i t 3 5 1 等。其中，p m r q u a d t r e e 是基于四叉树并且引入了动态属性，其关键在于当移 动对象发生更新时，原来的索引结构被破坏，然后根据新的信息重新建立索引结 5 中山大学硕士学位论文 基于k d 4 r e e 的移动索引索引研究 构。f t - q u a d t r e e 使用轨迹共享技术来最大限度地减少数据的存储量，提高索引 的更新效率。t p r - t r e e 主要是基于r 事t r e e t 3 6 1 ，使用时间参数化包围框来包含移 动对象，它可以有效索引移动对象的当前位置并对将来某时刻位置做出预测。 t p r * t r e e 修改了t p r - t r e e 的动态操作算法，它是目前最好的参数化空间访问方 法。随后人们对t p r - t r e e 进行各种改进，如s t a r - t r e e 3 7 1 和r e x a _ t r e e 3 8 】等。 1 3 本文的研究思路 在现有的移动对象索引方法中，通常将时间维看作新增空间维，将时空数据 作为比原有空间维更高一维的空间数据来处理。在理论上将时间维看作空间维符 合当代观念中时空连续体的思想，而且在技术上可使用空间数据索引技术如r 树，来进行相关研究与应用开发。但这种将时间“等同 于空间的模式存在着一 些问题，例如，从概念表述上看，空间概念相对简单，而时间概念表述较为复杂 且不够成熟，将时间等同于空间，难以反映时间概念的复杂性；从概念分类上看， 时间分为有效时间、事务时间和用户自定义时间，而各空间维在本质上没有区别； 从相互关系上看，时间注重顺序关系，而空间注重拓扑关系，两者在理论分析上 方式各异，在实际应用过程中效率不同。因此本文从将时间和空间分别进行处理 的基础上进而研究将两者进行有效整合出发，提出了基于k d t r e e 的移动对象索 引模型k m o i m ，其特点是先进行时态索引t i m ，然后在时态索引结果的基础上 进行空间索引s i m ，最后根据两者的特点进行有效整合。此外，t i m 和s i m 具 有基本数学支撑，本身也可单独用于时态数据和空间数据查询索引。最后，本文 设计仿真实验，实现了k m o i m 查询和更新算法，通过和其他移动对象索引方法 ( t b t r e e 、m o d i m t 3 9 1 和遍历) 进行比较，证明了本论文提出的索引模型k m o i m 具有良好的可行性和有效性。 1 4 本文的组织结构 本文共有6 章内容，其安排如下： 第1 章是绪论部分，介绍了本文的研究背景、研究的出发点和意义，分析了 本文研究涉及的相关领域的研究现状，并介绍了本文的组织结构。 第2 章介绍移动对象数据库以及移动对象索引的相关概念及理论。 6 巾山大学硕士学位论文 基予k d q r e e 的移动索引索引研究 第3 章提出并研究移动对象的数据模型和索引模型。讨论了时间拟序和空间 平面划分的概念，为本文所建立的索引模型提供基本的数学框架。 第4 章介绍了基于本文提出的索引模型的数据查询、更新等操作。 第5 章通过仿真实验实现基于索引的时间区域查询、时间片查询以及轨迹线 和轨迹线段的插入，通过对实验结果数据的分析进行可行性评估。 第6 章对本论文的主要内容进行总结，并阐述下步的研究工作。 1 5 本章小结 本章首先介绍了移动对象数据库的产生和发展，接着说明了随着数据库的广 泛应用，索引结构对有效管理数据库的重要性日益提出，然后介绍了移动对象索 引技术的研究现状，进而提出了本论文的出发点和研究思路。最后给出了本论文 的组织结构。 7 中山大学硕士学位论文基于k d 4 r e e 的移动索引索引研究 第2 章移动对象数据库基础 本章将对移动对象技术的基础理论做一个简单的介绍，这有利于对本论文提 出的移动对象索引模型k m o i m 的建立、分析和实现。本章内容主要包括：移动 对象基础、移动对象数据模型、主流移动对象基础索引技术以及移动对象数据查 询的分类。 2 1 移动对象基础 移动对象是位置不断随着时间变化的空间对象，其位置变化可以是离散的， 也可以是连续的。移动对象数据库就是专门管理移动对象及其位置的数据库，其 目的是为了有效的存储不断变化的移动对象的相关信息，并提供了对这些信息的 有效查询。移动对象数据库所管理的移动对象可以是各种行驶的汽车、飞机、轮 船、也可以是沙漠、油田、军队等。对于这些对象可以分为两大类 4 0 l ，移动点对 象( m o v i n gp 0 硫) 与移动区域对象( m o v i n gr e g i o n ) 。随着时间变化对象的位置不 断改变而其形状保持不变，这类对象抽象为移动点对象，如汽车、飞机、轮船、 移动手机用户等；随着时间不断变化对象的位置不断改变而且具有一定的范围， 形状也不断变化，将这类对象抽象为移动区域对象，如沙漠、油田等。本论文的 研究对象是针对移动点对象，因此以下章节，在不引起歧义的前提下，移动对象 是指移动点对象。 与传统数据库中存储的对象不同，移动对象具有以下特点】： ( 1 ) 移动对象具有多样性和复杂性。移动对象的信息内容覆盖面广，语义及 拓扑关系复杂。 ( 2 ) 移动对象具有随机性和规律性。移动对象的移动分为两类，一类具有随 机性，如出租汽车。它根据乘客的需要到达指定的地点，不同乘客要去的地方不 同，因此出租车司机并不知道他将到达哪里；另一类具有规律性，如公共汽车， 每一辆公交车都有它指定的行驶路线和运行的时间表，因此它具有规律性。 ( 3 ) 移动对象具有不精确性和不确定性。移动对象的运动具有连续性，但计 算机却只能按离散的方式对数据进行存储和计算。由于数据采集设备的精度限制 以及数据源与数据库之间传输的延时和处理的开销，移动对象存储的位置信息与 o 中山大学硕士学位论文 基于k d - t r e e 的移动索引索引研究 其实际的位置会存在一定的偏差。因此，不管采用何种存储及更新策略，移动对 象数据库中保存的移动对象的位置信息与移动对象实际的位置总会有一定的偏 差，即不精确性。由于位置函数只能近似描述实际位置的变化，因此将移动对象 的位置表示为时间的函数同样也存在着位置的不确定性。 ( 4 ) 移动对象的查询与查询给出的时问和对象所处的位置相关。即移动对象 的位置随着时间不断变化，因此在不同的时刻给出的同一条查询可能返回不同的 结果集。 2 2 移动对象数据模型 移动对象在空间的位置随时间而不断变化，如果用传统的数据库管理系统来 管理移动对象数据，就需要对数据库进行不断更新。频繁的更新不仅严重影响数 据库系统的性能，还会加重无线带宽的开销。如果降低更新的频度，可以降低系 统的更新负担以及无线带宽的开销，但又会造成对象位置的不准确性。因此，需 要采用一种全新的移动对象轨迹建模方法来解决当前的问题。目前，在移动对象 数据库的轨迹建模领域中，存在着两个并行发展的方向：基于位置服务的管理和 时空数据库。对应着两种典型的数据模型，首先是a ps i s t l a 等人提出的 m o s t ( m o v i n go b j e c t ss p a t i o t e m p o r a l ) 模型，其次是移动对象离散数据模型。 下面分别介绍这两种移动对象数据模型。 l 、m o s t 模型 在m o s t 模型中，引入了动态属性的概念，动态属性将移动对象的位置表 示为时间的函数，移动对象的动态属性是指其属性值随着时间变化的属性，如移 动对象的位置的坐标。通常，动态属性彳由三个子属性组成：a f u n c t i o n 、 a u p d a t e v a l u e 、a u p d a t e t i m e 。其中，a f u n c t i o n 是时间，的函数，当，= 0 时， a f u n c t i o n ( r ) = 0 ：当时间，= a u p d a t e t i m e ，a 的值为a u p d a t e v a l u e ；当时间 ，a u p d a t e t i m e ，a 的值通过a u p d a t e v a l u e + a f u n c t i o n ( t - a u p d a t e t i m e ) 计算得 到。在移动对象正常运动时，不需要对其位置信息反复更新，仅在发生异常情况 下才进行数据库的更新。 2 、移动对象离散数据模型 l o 中山大学硕士学位论文 基于k d - - t r e e 的移动索引索引研究 移动对象离散数据模型的目标是管理随着时间变化的几何体，与m o s t 模 型不同，移动对象离散数据模型不仅要存储移动对象的当前状态，而且也存储移 动对象的所有历史状态，以便能够查询移动对象的历史状态信息。它的局限性在 于不能支持移动对象的将来查询。 为了有效存储和管理移动对象及移动轨迹，通常将复杂的移动对象及运动轨 迹分割成相对简单的离散片段。由于计算机不能存储和处理抽象的数据模型，但 可以存储和处理离散的数据模型。因此要利用计算机来处理信息必须将抽象数据 模型离散化。对于移动对象的运动轨迹，采取在离散时间点对移动对象的位置进 行抽样的方法，通过一系列直线段将抽样位置连接形成折线段以表示一个移动对 象轨迹。移动对象的运动轨迹被抽象为三维空间的折线，其中，两维表示移动对 象所在空间平面，第三维用来表示时间【3 9 1 。 定义2 1 ( 移动对象轨迹) 在三维x y x t 空间里，一个移动对象的轨迹t r a j 是由序列点o i ，y l ，f 1 ) ，沁，见，2 ) ，似，弘，铀( f i f 2 ，。) 构成的折线，其 中折线中的每一段是直线段。给定一条轨迹t r a j ，在二维x y 平面上的投影叫 做t r a j 的路径，如图2 1 所示。 图2 - l 移动对象轨迹 轨迹把移动对象的位置定义为时间的函数，移动对象在时间t i 的位置坐标为 ，蝴，在时间区间【，：f ，“l 】内，移动对象从点到点帆l ，n 1 ) 以速度 ，做匀速 中山大学硕士学位论文基于k d - t r e e 的移动索引索引研究 直线运动。速度1 ，的值可由公式_ =堑三王三夏至互丑计算得到。因此在 时间区间“1 1 ( 1 s ，刀) 内，移动对象在轨迹t r a j 的位置可以通过线性插值的方 法得到。 2 3 移动对象索引技术 在移动对象数据库系统中，存储着大量的数据。在查询处理时如果逐个遍历 所有的移动对象数据显然会严重影响系统的性能，为了有效地实现对移动对象的 查询操作，就必须引入索引技术。移动对象数据的索引技术研究已经成为移动对 象数据库领域的一个研究热点，到目前为止，已经提出大量的索引方法，其中有 三种主流的方法，即r - t r e e 及其变形树、q u a d t r e e 及其变形树、g r i d f i l e 及其 变形树。成熟的索引方法都是以这三种主流方法为基础进行了扩展。对移动对象 而言，已提出的各种索引方法还处于理论研究阶段，离实际应用还有一定的差距， 每种索引结构都有其优点和缺点，只是在某种情况下的查询有比较好的性能。在 今后，多种索引结构的整合将是移动对象数据库系统设计的主要趋势。 本节简单介绍了三种主流基础索引结构，并对本论文所借鉴的k d t r e e 4 2 l 以 及实验对比用到的t b t r e e 等索引结构做了简要的阐述。 2 3 1r t r e e 索引模型 r - t r e e 9 】最早是由g u t m a n 在1 9 8 4 年提出的，主要用于空间数据的索引。随 后众多研究者针对不同的应用需求对r - t r e e 进行了各种改进，如r + t r e e 4 引、 r * - t r e e 、3 d r - t r e e 、s t r - t r e e 等，形成了r - t r e e 系列空间索引技术。r - t r e e 是b 树的扩展，也是一种高度平衡树，其结点分为叶子节点和目录结点，叶子节点均 出现在同一层。r - t r e e 的节点s 用( 所，m b g ) 表示。若节点s 是叶子节点，则所 为指向特定对象存储位置的指针，m b r 为该特定对象的最小外包矩形( m i n i m u m b o u n d i n gr e c t a n g l e ，m b r ) ；若节点s 为目录节点，则所为指向下一层节点的指 针，m b r 为包含节点s 以及s 指向的所有结点的最小外包矩形。如图2 2 所示。 r - t r e e 具有b t r e e 的优点，如自动保持平衡、空间利用率高、有效减少磁盘 访问次数等优点。r - t r e e 的不足之处在于：由于中间结点目录矩形允许且可能重 1 2 中山大学硕士学位论文 基于k d - t r e e 的移动索引索引研究 叠，这就导致某些查找路径不包含查找结果，影响查找性能。随着索引空间维数 的增加，r - t r e e 目录结点的m b r 重叠迅速增加，就会严重影响查找性能。 幽鱼鬲 图2 - 2 空间对象m b r 及其对应r - t r e e 2 3 2 四叉树( q u a d t r e e ) 索引模型 四叉树【1 0 】在1 9 7 4 年提出，是建立在对平面区域循环分解思想上的一种层次 数据结构。它是基于空间划分组织索引结构的索引机制。首先在平面内选取一点， 根据这点的横纵坐标将平面划分为四个区域，在每个区域再选取一点进行划分， 以此类推，如图2 - 3 ( a ) 所示。相应的四叉树中每个结点代表平面的一个点，每个 结点至多有4 个孩子结点，代表平面内的四个区域，如图2 - 3 ( b ) 所示。 由于四叉树具有表示空间目标以及聚集空间目标的能力，可以改善空间检索 的性能，因此四叉树被广泛应用在空间索引之中。其不足之处在于，当索引数据 量较大时，如果四叉树层次过多，则使得空间开销增加，而且查询最坏情况下需 要比较每个结点，从而使查询性能急剧下降。因此，在选取结点划分时，需要采 取一定的优化策略使得所建立的四叉树尽可能保持平衡。 1 3 中山大学硕士学位论文 基于k d - t r e e 的移动索引索引研究 ： ： ：b i ：；g 卜。，一：f 卜t jl ；| e e i 一i 三卜! j j ；d 一 ：? 一t 一。 ：a ： ：n ii 一一一一一一? - - - - - 了 ! i i ( a ) a 图2 3 平面划分及对应的四叉树 2 3 3 网格文件( g r i d f i l e ) 索引模型 网格文件索t i t 】是一种针对点对象的h a s h 索引。它将目标空间划分成固定 网格，移动对象按照位置信息被投影到不同的网格。在通过网格索引查询某个对 象时，首先找到该对象所对应的存储网格，然后在网格内进行搜索。根据对象的 位置寻找对应的存储网格是一个h a s h 过程。网格文件的优点在于当索引低维空 间点目标时，由于访问外存页面比较少，因此效率较高，但是当索引非点状空间 目标时，查询效率较差。 2 3 4k d t r e e 索引模型 k d t r e e 4 2 1 是由b e n t l y 在1 9 7 5 年提出的，主要用于索引多属性的数据或多维 点数据。与二叉检索树不同的是，k d t r e e 的每个结点表示k 维空间的一个点，并 且树的每一层都根据这层的分辨器( d i s c r i m i n a t o r ) 来做出分枝判断。k d t r e e 第f 层的分辨器定义为：fm o dk ，在这里，假设树的根结点所在层为0 层，根结点的 孩子为第一层，依次递增。 k d t r e e 或者是一棵空树，或者是一