（计算机软件与理论专业论文）动态环境下移动对象连续最近邻查询研究.pdf

哈尔滨理t 大学t 学硕十学位论文 动态环境下移动对象连续最近邻查询研究 摘要 随着科学技术的快速发展，卫星全球定位系统和无线通讯技术已经能够 跟踪并记录移动对象的位置。同时，移动对象的连续运动也对数据库技术提 出了新的要求和挑战，能够描述移动对象及其位置信息的移动对象数据库应 运而生。在移动对象数据库中，移动对象的最近邻查询问题一直是其中的研 究热点。然而，过去的研究工作大部分都集中于静态环境下的最近邻查询， 如何将静态环境下的最近邻查询方法扩展到动态环境下成为研究中的重点和 难点。 本文对动态环境下的最近邻查询方法进行了研究，提出了以t p r 树为 索引结构、引入分界时间的最近邻查询算法，并将这种算法扩展到了动态环 境下的k 个连续最近邻查询。 首先通过对移动对象索引技术的分析与比较，详细研究了一种适合于进 行未来最近邻查询、可以提高查询的质量和效率的索引方法：t p r 树，并 在这一索引结构的基础上进行查询算法的研究。 其次通过对最近邻查询问题的特征分析，提出了一种通过计算分界时间 完成动态环境下最近邻查询的解决方案，并给出了分界时间的计算公式和方 法。与此同时，将一种近似计算距离的算法进行改进，提出了能够精确计算 距离的算法。 然后将现有的静态环境下的最近邻查询算法与本文提出的分界时间相结 合，提出了两种分别通过深度和宽度优先遍历t p r 树利用剪枝技术找到移 动对象最近邻的查询算法，不但适用于高维空间而且具有很强的扩展性。 最后进一步将这两种算法扩展到动态环境下的k 个最近邻查询和连续最 近邻查询，并通过实验验证了算法的可行性和正确性。 关键词移动对象；连续最近邻查询；t p r 树；剪枝技术 哈尔滨理工大学t 学硕。卜学位论文 c o n t i n u o u sn e a r e s t n e i g h b o ro r e s e a r c ho fm o b i l e0 b je c ti nm e n v i r o n m e n t a b s t r a c t u e r v ， o b i l e w i t ht h er a p i dd e v e l o p m e n to ft e c h n o l o g y ，g l o b a lp o s i t i o n i n gs y s t e ma n d c o m m u n i c a t i o nt e c h n o l o g yc a nr e c o r dt h ep o s i t i o n so fm o v i n go b j e c t s t h e c o n t i n u o u sm o v e m e n to fm o v i n go b j e c t sr e s u l t si nn e wc h a l l e n g e st od a t a b a s e t e c h n o l o g y ，a n dm o v i n go b j e c t sd a t a b a s ea p p e a r e d i nm o v i n go b j e c t sd a t a b a s e ， n e a r e s tn e i g h b o rq u e r i e sa t t r a c tm u c ha t t e n t i o n h o w e v e r ，t h ep a s tr e s e a r c h m o s t l yf o c u s e so nt h en e a r e s tn e i g h b o rq u e r i e si ns t a t i ce n v i r o n m e n t ，a n dh o w t o e x p a n di tt om o b i l ee n v i r o n m e n tb e c o m e se m p h a s i sa n dd i f f i c u l t y t h i sp a p e rs t u d i e so nn e a r e s tn e i g h b o rq u e r i e si nam o b i l ee n v i r o n m e n t t h e a l g o r i t h m sb a s e do nt p r t r e ea n ds p l i tt i m ea r ei n t r o d u c e d ，a n da r ee x p a n d e dt o kn e a r e s tn e i g h b o rq u e r i e sa n dc o n t i n u o u sn e a r e s tn e i g h b o rq u e r i e si nam o b i l e e n v i r o n m e n t f i r s t l y ，t h ei n d e x i n gt e c h n i q u e sa r ed i s c u s s e da n dt p r t r e ei sa d o p t e d t h e s t r u c t u r ei ss u i t a b l ef o rf u t u r en e a r e s tn e i g h b o rq u e r i e sa n dc a ni m p r o v et h e q u a l i t ya n de f f i c i e n c yo ft h eq u e r i e s s e c o n d l y ，t h ec h a r a c t e r so fn e a r e s tn e i g h b o rq u e r i e sa r ea n a l y z e d t h es p l i t t i m ei si n t r o d u c e da n dt h ed e t a i l e dc o m p u t i n gf o r m u l a sa r ep r e s e n t e d f o rt h e d i s t a n c ec o m p u t i n g ，t h ea p p r o x i m a t ea l g o r i t h mi sa m e l i o r a t e da n da na c c u r a t e a l g o r i t h mi sp r e s e n t e d t h i r d l y ，t h es p l i tt i m ei su s e di nt h en e a r e s tn e i g h b o rq u e r i e sa l g o r i t h m s t h ea l g o r i t h m st r a v e r s et p r t r e ei nad e p t h f i r s ta n dw i d t h - f i r s tm a n n e rt of i n d t h en e a r e s tn e i g h b o rb yp r u n i n gt e c h n i q u e t h ea l g o r i t h m sa r es u i t a b l ef o rt h e n e a r e s tn e i g h b o rq u e r i e si nh i g hd i m e n s i o na n dh a v es t r o n ge x p a n s i b i l i t y a tl a s t ，t h ea l g o r i t h m sa l e e x p a n d e dt o kc o n t i n u o u sn e a r e s tn e i g h b o r i i 哈尔滨理t 大学t 学硕j 二学位论文 = 目e | 目p l i e j 目! 目目= 阜 q u e r i e si nam o b i l ee n v i r o n m e n t e x p e r i m e n t sa r ed o n et ov a l i d a t et h ef e a s i b i l i t y a n dv a l i d i t yo ft h ea l g o r i t h m s k e y w o r d sm o v i n go b je c t s ，c o n t i n u o u s n e a r e s tn e i g h b o rq u e r y ，t p rt r e e ， p r u n i n gt e c h n i q u e i i i - 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文动态环境下移动对象连 续最近邻查询研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学 位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分 外不包含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人 和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承 担。 作者签名：盏葫l 艮 日期：腓岁月力日 哈尔滨理工大学硕士学位论文使用授权书 动态环境下移动对象连续最近邻查询研究系本人在哈尔滨理工大 学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果 归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本 人完全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留 并向有关部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔 滨理工大学可以采用影印、缩印或其他复制手段保存论文，可以公布论文的 全部或部分内容。 本学位论文属于 保密 口， 在年解密后适用授权书。 不保密囹。 ( 请在以上相应方框内打4 ) 作者签名：璜敬让 导师签名：椭 日期：少豸年刁月1 0 日 日期：硝年弓月p 日 哈尔滨理工火学1 = 学硕i 二学位论文 1 1 研究目的及意义 第1 章绪论 静态环境下的最近邻查询问题一直是地理信息系统“1 中研究的热点。例 如：用户指定某一位置或屏幕上的某一物体，要求系统从数据库中找到距离其 最近的物体。由于空间物体数量众多，这就导致空间数据量十分庞大，所以计 算出已知点和所有空间物体的距离，找出距离已知点最近的物体是不切实际 的。特别在多维空间里，这样的查询会更费时。因此，需要研究高效快速的查 询算法解决这类问题。至今为止，对于静态环境下的最近邻查询问题，已有多 种方法被提出并运用，技术较为成熟。 近年来，随着跟踪连续运动目标位置技术的快速发展，最近邻查询问题扩 展到动态环境这一领域，成为移动对象数据库中重要的研究方向之一，例如： 找到从现在开始的十分钟内，距离当前移动物体最近的移动目标。由于动态环 境下所有物体都是连续运动的，在此基础上的最近邻查询非常复杂。因此如何 将静态环境下的最近邻查询扩展到动态环境下成为研究中的重点和难点，能够 有效地处理大量移动对象的最近邻查询算法显得尤为重要。 动态环境下的最近邻查询可以处理移动对象发出的查询请求，找到其运动 过程中的最近邻，对于交通预测、交通管理、智能导航等有着重要的意义，在 智能交通系统、地理信息系统、军事中有着广泛的应用前景。 1 2 移动对象数据库的发展状况 随着卫星全球定位系统和无线通讯技术的快速发展，跟踪并记录移动对象 的位置成为可能。同时，移动对象的连续运动也对数据库技术提出了新的要求 和挑战，并已经迅速成为一个新的研究热点。 现存的数据库管理系统不能够处理连续变化的数据，如移动对象的位置。 这是因为，在传统数据库中，如果数据不被修改，数据是一直保持不变的。而 要在数据库中表示移动对象并回答关于位置的查询，移动对象的位置需要连续 更新。显而易见，移动对象位置的频繁更新是不现实的，为了解决这一问题， 能够描述移动对象及其位置信息的移动对象数据库应运而生扭1 。 哈尔滨理t 大学t 学硕：i 二学位论文 1 9 9 7 年p s i s t l a 、0 w o l f s o n 和s c h a m b e r l a i n 提出了移动对象数据库的 基本数据模型：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 模型。这个模型的关 键在于动态属性的提出，这一属性将移动对象的位置用一个时间函数表示，解 决了移动对象位置不断更新的难题。一个动态属性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 f u n c t i o n 来表示。其中，a f u n c t i o n 是一个 以时间为变量的函数，在t - - 0 时刻，值为o 。动态属性a 的值定义如下：在 a u p d a t e t i m e 时刻，a 的值为a u p d a t e v a h e ，那么a u p d a t e t i m e + t o 时刻，a 的 值为a u p d a t e v a l u e + a f u n c t i o n ( to ) 。与此同时，还提出了适用于m o s t 数据模 型的查询语言f t l ( f u t u r et e m p o r a ll o g i c ) ，可以查询移动对象当前和未来的位 置。 将动态属性加入到现存的数据库数据模型中提出的m o s t 模型，可以有 效地对移动对象的位置信息进行描述，是移动对象数据库的基本模型。随着科 学技术的进步，动态环境的不断发展，移动对象数据库将变得越来越重要，在 此基础上的移动对象索引技术和移动对象查询研究成为移动对象数据库的核心 问题h 一一1 。 1 3 索引技术的研究现状 数据库系统所要完成的基本功能就是对数据进行有效地存储、查询和更 新。其中，一个关键的问题就是面对大量的存储在计算机硬件媒介内的数据， 数据库系统如何按照用户提出的特定查询要求，有效、合理、快速和正确地将 对应的数据查询出来。目前解决上述问题的主要技术就是索引技术，它是快速 高效查询，检索和显示数据的前提。不管数据库技术如何发展，从关系数据 库、空间数据库和时序数据库，到时空数据库、移动对象数据库，它们对数据 的查询要求越来越高，所需的索引技术越来越具有挑战性，也受到了越来越多 的重视。有效地解决数据库的索引问题，是数据库研究者所共同关注的1 。 1 3 1 空间索引技术 空间数据库是用来存储、管理各种空间或非空间信息的计算机信息应用系 统| 8 ：其管理带有空间属性信息的能力是一般关系型数据库所不具备的。传统 关系型数据库用b + 树为数据建立索引，来提高检索的效率。但b + 树是一维索 引，无法处理空间数据库中的二维和多维空间数据，必须另外为空问数据建立 专门的索引机制。由于空间索引在整个空间数据库中的重要地位，一直是研究 哈尔滨理丁人学t 学硕 ：学位论文 中的重点。 目前，已经研究出许多高效的空间索引方法悖“们，大致分为如下四类，其 中主流方法都是采用树索引结构： ( 1 ) 基于二叉树的索引技术基于二叉树索引结构的典型范例包括k d 树 “、m k d 树n 2 1 、s k d 树3 1 等。这种索引结构的典型k d 树是一种二分索引树 结构，主要用于索引多维数据点，但对复杂的空间目标的索引却必须采用近似 方法和空间映射技术。因此针对空间关系的查询效率非常低，索引树非常庞 大，需要存储在外存的缺点，同时为了能够索引复杂的空间目标，提出了适合 索引二维空间目标的基于实体标志重复存储技术的m k d 树。s k d 树的提出避 免了空间目标的重复存储和空间映射，用空间目标的中心点来对空间目标集进 行二分索引。但是所有这些方法对非点状空间目标的索引效率都较低。 ( 2 ) 基于b 树的索引技术b 树及其变体n 引，被广泛应用于常规的数据库管 理系统之中，实践证明其对大型数据库的索引具有出色表现。目前的空间数据 索引技术，很多都基于b 树，如r 树n 引。r 树的思想是将空间目标及索引空 间用其最小包含矩形来近似表示，可以简化计算、减少存储空间，而且，将空 间上邻近的目标组织在同一结点或同一分枝，可以减少外存访问次数。然而由 于允许区间重叠，导致了搜索路径的平均数量的增加，每一维的区间都要储 存，需要较多的存储空间。尤其在维数增高时很可能会导致索引次数和存储空 间的大量增加，严重影响查询效率。为了避免索引空间重叠的问题，r + 树n 刚被 提出，这一方法采用强制重新插入来调整r 树的结构。 从r 树的结构上可以看出，让空间上靠近的空间对象拥有尽可能近的共 同祖先，能提高r 树的查询效率。形象地说，就是让聚集在一起的空间对象尽 可能早地组合在一起。但是怎样衡量空间对象的聚集，是一个非常复杂的问 题。由于衡量的方法不同，也产生了众多的r 树的变形。r 树使用面积这个指 标来衡量空间上的聚集。在插入操作时，选择插入新对象后最小包含矩形面积 增长最小的结点作为根的子树。而在分裂溢出结点时，选择各种分裂组合中， 最小包含矩形面积和最小的结合方式。对树7 1 在插入操作时则将叶子结点和非 叶子结点分开考虑，分别采用不同的标准，同时提出了既考虑最小包含矩形的 周长也考虑其相互重叠的面积的方法来衡量空间上的聚集，在分裂溢出结点时 也提出了更为复杂的算法。而h i l b e r t r 树8 i 则利用分形中采用的一种空间填充 曲线h i l b e r t 曲线，把各个数据矩形的中心映射为h i l b e r t 曲线上的一个值，将 多维空间的空间对象映射到一维空间，使得高维数据在低维空间有一个对应， 而且，高维空间数据之间的关系能够在低维的映射中得到一定的保留，然后， 哈尔滨理工大学1 二学硕f ：学位论文 利用该变换保持的空间聚集的特性来解决这个问题。 总之，这类索引结构需要解决的主要问题仍然是减少区域的重叠，提高搜 索效率。然而，让r 树的组合结构尽可能地合理是一个非常复杂的问题。上面 的众多方法都不能很完善地衡量空间的聚集。同时，都只能作到局部的优化， 无法保证由此形成的r 树的整体组合结构最优。但r 树系列空间索引具有其 它索引无法企及的优势，具有很强的灵活性，能够较好地与传统的关系型数据 库相融合，这是许多空间数据库选择r 树作为空间索引的一个主要原因。 ( 3 ) 基于哈希的网格技术这种基于哈希方法n 训的基本思路是将索引空间划 分为相等或者不相等的一些小方网格，与每个网格相关联的空间目标存储在同 一磁盘页上，而网格的访问地址则可以直接通过求数组下标或应用某种算法得 到，常见的方法有g r i df i l e 妇0 1 等，这类方法主要适用于索引多维空间点。 ( 4 ) 空间目标排序法这种方法的基本思想是将索引空间划分为许多小的格 子，然后对每个格子指定一个唯一的数字或编码，空间目标用与其相交的一个 或多个格子的数字来表示，或者用与其相交格子的编码求得的另一个唯一的编 码来表示。这种方法的实质是将多维空间的实体映射到一维空间，然后采用一 维的数值对多维的空间目标进行排序，常见的方法有q u a d t r e e 1 、z o r d i n g 等。 1 3 2 移动对象索引技术 移动对象数据库的一项根本任务就是信息的检索查询，能否快速的检索信 息是移动对象数据库性能高低的一个主要的标志。移动对象数据库于1 9 9 7 年 被提出，至今为止，国内外对其索引技术的研究还处于初级阶段，提出的几种 索引结构大部分都是由空间索引结构发展而来的。 移动对象索引技术分为两类：索引移动对象当前和未来位置的技术以及索 引移动对象历史轨迹的技术。 关于索引移动对象历史轨迹的技术，大多数方法都是将空间数据进行离散 的处理，并没有考虑到其连续变化，通过加入一个时间维，使移动对象在d 维 空间的运动转化为d + 1 维空间的轨迹来描述。2 0 0 4 年由d p f o s e r 、c s j e n s e n 和y t h e o d o r i d i s 提出两种方法s t r - t r e e ( s p a t i o t e m p o r a lr - t r e e ) 和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 ) 圳。这两种树结构对于索引移动对象轨迹的查询要 优于r 树系列。2 0 0 4 年y t a o 和d p a p a d i a s 又提出了m v 3 r - t r e e ( m u l t i v e r s i o n 3 dr - t r e e ) 幢引，此结构将m u l t i v e r s i o nb t r e e | 2 5 1 和3 d r t r e e 相结合，可以较好地 哈尔滨理工大学t 学硕l 学位论文 索引移动对象的历史轨迹。 关于索引移动对象当前和未来位置的技术，目前有以下几种方法被提出： ( 1 ) 1 9 9 8 年j t a y e b 、o u l u s o y 和o w o l f s o n 首次提出了移动对象的索引方 法m 1 ，可以对移动对象的未来位置进行索引。这种方法将索引空间分割成四部 分，采用p m rq u a d t r e e 来索引移动对象。假设移动对象在d 维空间运动，通 过加入一个时间维，将移动对象的未来轨迹转化为d + l 维空间的线来索引，然 后通过移动对象动态属性的时间函数有效地进行未来位置的预测。然而这种方 法需要不断存储线的信息，从而可能会导致过量的存储。 ( 2 ) 1 9 9 9 年g k o l l i o sd g u n o p u l o u s 和v j t s o t r a s 提出了在一维和二维空间 索引移动对象未来位置的方法1 ，此方法采用h o u g h 转换幢引将移动对象的轨迹 在更高维空间中映射成点，然后采用h b 兀t r e e 啪1 的点存取方法和多个b + - t r e e 的方法进行索引。为了适应这种数据的转化，这种情况下的查询也要进行转 化。而且，这种索引结构不能够扩展到高维空间，具有很大的局限性。 ( 3 ) 2 0 0 0 年s s a l t e n i s 、c s j e n s e n 和s t l e u t e n e g g e r 提出了一种r 树的扩 展树：t p r 树( t i m e p a r a m e t e r i z e dr - t r e e ) 1 ，它是一种以时间为参数并且能够 存储动态目标的索引结构，可以将所有基于m o s t 模型的移动对象进行存 储，树中的各个结点都是一个以时间为参数的表达式，可以有效地表示移动物 体的方向和速度。这种方法在原始空间索引数据，采用速度矢量将索引结构参 数化，使得未来任何时刻的索引结构都能被得出，是一种非常直观的索引技 术，适合于对一维、二维、三维空间的数据进行索引，不需要对其进行频繁的 索引重建，与目前提出的其他方法相比，具有较为突出的优越性。2 0 0 2 年 s s a l t e n i s 和c s j e n s e n 对t p r 树这种索引结构作了改进，在此基础上专门 针对过期数据的处理提出了一种r e x p t r e e ，更好地改善了这种索引结构的查询 性能2 0 0 3 年y t a od p a p a d i a s 和j s u l l 对t p r 树进行改进提出了一种t p 树 3 2 1 ，更好地考虑了移动目标的动态属性，其性能优于t p r 树。 1 4 最近邻查询方法的研究现状 最近邻查询问题一直是数据库研究中的重要应用领域，然而，过去的大部 分研究工作一直集中于静态环境下的最近邻查询。随着近几年移动对象数据库 的发展，使得最近邻查询问题扩展到了动态环境这一领域。有效地查询动态环 境下，移动物体的最近邻变得极为重要。 哈尔滨理_ t 大学丁学硕士学位论文 1 4 1 静态环境下的最近邻查询 目前，国内外对于静态环境下的最近邻查询问题已经取得了一定的研究 成果，提出了多种适用于静态环境的查询算法。其中，最基本的最近邻查询算 法是基于r 树的b a b ( b r a n c h a n d - b o u n d ) 算法其中包括深度优先遍历r 树的 d f ( d e p t h - f i r s t ) 算法和宽度优先遍历r 树的b f ( b r e a d t h - f i r s t ) 算法，都可以应用 于发出查询请求的物体和被查询的目标都是静止的情况。d f 算法由 n r o u s s o p o u l u ss k e l l e y 和f v i n c e n t 于19 9 5 年提出嘲，这种方法通过查询点q 和结点e 的子树中所包含目标的距离的最小值m i n d i s t 值查询点q 和结点e 的子树中所包含目标的距离的最大值m i n m a x d i s t 值作为判断条件深度优先 遍历r 树查询最近邻，并在文献 3 4 】中分析了这种算法的性能。一种改进的 d f 算法由k l c h e u n g 和a w f u 于2 0 0 0 年提出1 ，这种方法只采用 m 1 n d i s t 值作为判断条件深度优先遍历r 树完成查询。b f 查询算法由 g r h j a l t a s o n 和h s a m e t 于2 0 0 2 年提出嘲1 ，此算法采用了一个优先队列保存 到目前为止已经访问过的结点，从所有结点中选择下一个要处理的结点，是一 个较为优越的算法。 对于发出查询请求的物体是移动的、被查询的目标是静止的最近邻查询问 题，也有一些方法被提出。其中，一种解决这个问题的方法采用v d ( v o r o n o i d i a g r a m ) 模型船7 1 这一概念，由b z h e n g 和d l l e e 于2 0 0 4 年提出，这种方法m 1 适用于移动查询点对静态目标的查询，静态目标通过r 树对其建立索引，但是 这种方法只适用于查找移动对象的一个最近邻，无法将其扩展到k 个最近邻的 查询。另一个最近邻查询算法于2 0 0 5 年由z s o n g 和n r o u s s o p o u l o s 提出 1 ，通过在取样点重复应用最近邻查询算法为一个移动查询点找到连续最近 邻。这种方法采用前一个点的计算结果来计算后点，避免重复运算。然而，不 同的取样频率会影响到结果的精确性。另外一种不会产生错误的方法于2 0 0 5 年由y t a od p a p a d i a s 和q s h e n 提出，是一种基于r 树的查询算法，可有 效地通过一次查询得出移动点的连续最近邻，避免了分割点的丢失和高代价的 查询，在性能上也有较大提高。 然而，上述方法只适用于静止查询点对静止查询目标的最近邻查询或者移 动查询点对静止查询目标的最近邻查询。对于移动对象数据库中查询点和查询 目标都是移动的情况，则无法应用上述方法完成最近邻查询。随着移动对象数 据库的产生，最近邻查询问题扩展到动态环境成为必然的趋势，于是，对于动 态环境下这一问题的研究成为了国内外学者共同的研究热点。 哈尔滨理t 大学t 学硕 ：学位论文 1 4 2 动态环境下的最近邻查询 关于动态环境下最近邻查询问题的研究，国内外还处于初始阶段。要完成 这种查询，首先需要基于能够存储动态目标的索引结构。虽然已有一些索引结 构被提出，但是适合于进行未来最近邻查询的索引结构是非常有限的。国外至 今为止提出了几种能够索引移动对象未来位置索引结构，例如：p m r - q u a d t r e e h b 兀t r e e 、t p r 树等。那么在一种适合于进行未来最近邻查询的索引结构的基 础上，通过执行有效的最近邻查询算法，完成动态环境下的未来最近邻查询将 是解决这一问题的有效途径。 动态环境下的最近邻查询算法于2 0 0 5 年由g k o l l i o s 、d g u n o p u l o u s 和 v j t s o t r a s 提出h ，这种算法采用复制转换的方法，将一个移动点的运动轨迹 x ( t ) - - - x 0 + v xt 转化成在空间中的一个点( x 0 , v x ) 然后在此基础上采用l a b n - t r e e 和 b + - t r e e 索引结构完成最近邻查询。但是，这种方法只适用于一维空间，无法 扩展n - - 维空间。 r b e n e t i s 、c j e n s e n 和g k a r c i a u s k a s 于2 0 0 5 年提出了基于t p r 树的最 近邻查询算法m 1 ，可以应用于二维空间的移动对象最近邻查询，并可扩展到多 维空间。然而，该算法只能完成未来段时间的最近邻查询，不能进行连续的最 近邻查询，具有一定的局限性。 1 5 课题来源及研究内容 本课题来源于黑龙江省自然科学基金f 2 0 0 6 0 1 。 在移动对象数据库中，无论发出查询请求的物体还是被查询的目标都是运 动的，这就需要把适用于存储动态目标的索引结构和高效、快速的查询算法相 结合，从而提供在动态环境下快速查询移动对象最近邻的算法。本课题的主要 研究内容为： ( 1 ) 通过对移动对象索引方法进行综合分析与比较，研究了一种适合于未来 最近邻查询的、可以提高查询的质量和效率的索引方法t p r 树，并基于这一 索引结构进行查询算法的研究。 ( 2 ) 通过对最近邻查询问题的特征分析，提出分界时间这一概念，并提出其 具体的计算公式和方法。对于计算包含矩形分界时间过程中涉及到的距离计算 问题，将原有的距离计算算法进行改进。 ( 3 ) 将现有的静态环境下的最近邻查询算法与本文提出的分界时间这一概念 哈尔滨理工人学- t 学硕j ：学位论文 相结合，提出了两种新的最近邻查询算法分别通过深度和宽度优先遍历t p r 树找到移动对象的最近邻。 ( 4 ) 进一步将此算法扩展到动态环境下的k 个最近邻查询和连续最近邻查 询。 ( 5 ) 通过实验验证算法的可行性和有效性。 1 6 论文结构安排 本文各章的结构安排如下： 第二章系统地介绍了空间数据库索引结构r 树和移动对象数据库索引结构 t p r 树的组织特点以及静态环境下基本的最近邻查询算法，为进一步研究奠定 了理论基础。 第三章提出了分界时间这一概念及其计算方法，并将计算包含矩形分界时 间时涉及的距离计算算法进行改进，给出了一种动态环境下最近邻查询的解决 方案。 第四章将分界时间引入到最近邻查询算法中，给出了两种基于t p r 树的 深度优先和宽度优先遍历的最近邻查询算法，能够有效地完成动态环境下的最 近邻查询。 第五章将这一算法扩展到动态环境下的k 个最近邻和连续最近邻查询，并 进行实验，验证了算法的有效性。 哈尔滨理t 人学工学硕：l 学位论文 第2 章基础理论 实现最近邻查询的关键技术由索引技术和基于索引结构的最近邻查询算法 两部分组成。一种有效的索引技术是快速检索信息的基础，便于在此基础上的 查询算法的实现。因此，动态环境下的最近邻查询研究要以能够索引移动对象 的动态索引结构为基础，然后，将静态环境下的最近邻查询算法扩展到动态环 境中。本章将介绍空间数据库索引技术、移动对象数据库索引技术以及基本的 最近邻查询算法理论，为后文的研究工作奠定理论基础。 2 1 空间数据库索引技术 随着计算机技术的发展，空间数据库应用范围已经扩展到了机器人、计算 机辅助设计、图像识别、环境保护、地理信息处理等领域。与传统的数据库管 理系统相比，空间数据库涉及对现实世界大量空间目标的处理。然而，空间目 标具有其特殊性。首先，空间目标往往具有不规则的几何形状，而且目标之间 的空间关系复杂，存储需求量大：其次，针对空间目标的空间操作，计算的代 价比起传统的操作复杂、运算量大；最后，空间目标的空间次序难以定义，无 法应用通常的排序技术。因此，这种数据需要特殊的数据结构才能有效地处 理。 空间索引是按照空间分布特性来组织和存储数据的几何数据结构m 1 。建立 空间索引机制的主要目的是提供对数据的访问路径或指针，便于对空间目标的 查询以及各种空间数据进行操作，提高对空间数据的搜索速度。目前存在许多 索引结构和技术来解决空间数据库中查询数据集问题一1 ，但是总体而言， 都是由r 树派生出来的各种变种，移动对象数据库的索引技术t p r 树也是r 树的一种扩展，因此，首先介绍r 树的结构及其相关操作。 2 1 1r 树索引结构 r 树是目前常用的一种空间数据索引方法m 1 ，并且广泛应用于空间及多维 数据库中。它是一维的b 树在空间数据库中的一种扩展，与b 树的结构类 似，也是一种平衡树结构，并且已经成为很多空间数据索引方法的基础。r 树 是一种由最小包含矩形来近似表达空间目标的结构，可以直接对地理空间中占 据一定范围的空间目标进行索引。 哈尔滨理工大学工学硕士学位论文 r 树中的每个非叶子结点由若干个( m b r , p o i n t t o c h i l d ) 组成。其中的 m b r ( m i n i m u mb o u d i n gr e c t a n g l e ) 为包含其对应孩子的最小包含矩形，这个矩 形是一个广义上的概念，它在二维空间上是矩形，在三维空间上则是长方体， 以此类推到高维空间，p o 硫t o c l l i l d 是一个指向其对应孩子结点的指针。r 树 中的每个叶子结点都由若干个( m b i l g e o o b j e c t l d ) 组成。其中m b r 为包含对应 的空间对象的最小包含矩形，g e o o b j e c t l d 是空间对象的标号，通过该标号可 以得到对应空间对象的详细信息。 r 树的建立需要满足一定的规则。设m 为r 树中结点所包含的子结点的 最大数目，m 为r 树中所包含的子结点的最少数目，则有m m 2 。此外，r 树还具有以下性质： ( 1 ) 每个叶子结点包含【m ，m 】个索引记录，除非它是根结点： ( 2 ) 对于每个在叶子结点的索引记录( m b r , g e o o b j e c t l d ) ，m b r 是一个最 小的1 1 维方体，它包含了对应的数据对象； ( 3 ) 每个非叶子结点具有 m ，m 】个孩子，除非它是根结点； ( 4 ) 对于每个非叶子结点的( m b r , p o i n t t o c h i l d ) ，m b r 是一个最小的方 体，它包含了孩子结点对应的方体； ( 5 ) 根结点至少具有两个孩子，除非它是叶子； ( 6 ) 所有的叶子都出现在相同的层次上。 一个包含n 个索引记录的r 树的高度至多是l o g ：, 一1 ，因为每个结点的分 支因子至少是m 。最坏情况下除根结点以外的所有结点的空间利用率是m m 。 因此，r 树具有较高的空间效率，可以保证空间利用率在5 0 以上。 如图2 1 所示，为二维空间中的一个r 树结构。由此图可以看出，r 树结 构的一个重要特点就是兄弟结点对应的空间区域可以互相重叠，这样的特性一 方面使r 树比较容易进行删除和插入操作，但另一方面，使空间搜索的效率降 低。因为区域之间有重叠，可能要对多条路径进行搜索后才能得到最后的结 果。这样的不足促使人们研究区域之间没有重叠的索引方法，这样就发展了 r + 树、r 树等其它的索引结构。 2 1 2r 树操作 r 树索引结构建树算法的基本思想是：根据空间对象在空间上的分布情 况，将对象集合进行划分，每组对象在空间位置上尽可能聚集为一簇，并且每 哈尔滨理t 大学t 学硕j ：学位论文 曳1 3 旧马 r l l h 一 ； i | r 3l 田i il lu i 恼l 固l l! ，呻。曼l 乙 il - ： ! 对象 a ) a t i a lo b j c t s 一一 t r e e图2 r 树结 f i 2 - 1 s t r c t u r eo f- t e e1 哈尔滨理工大学t 学硕卜学位论文 组对象的对象数尽可能接近树中规定的结点最大容量m 值而又不超过它。然 后，每组对象构造一个叶子结点，求出该叶子结点的最小包含矩形，即该组中 所含的所有对象的矩形外包。将形成的叶子结点按照与空间对象同样的方法处 理，如此递归下去，直到形成一个根结点，树的构造完成。 r 树是一种动态的索引结构，其插入、删除可以和查找混合进行。 r 树的插入与许多的有关树的操作一样是一个递归的过程。首先从根结点 出发按照一定的标准，选择其中一个孩子插入新的空间对象。选择孩子结点时 有下面三种情况： ( 1 ) 当点包含在一个叶子结点区域内时，就选择该叶子结点； ( 2 ) 当点包含在几个不同的叶子结点区域内时，选择产生最小体积的叶子结 占 j 、 ( 3 ) 当点未被包含在任何叶子结点区域内时，选择扩大最小的区域及可包含 该点的叶子结点，如果几个叶子结点的扩大值相同，则选择本身体积最小的叶 子结点。 然后，从孩子树的根结点出发重复进行上面的操作，直到叶子结点。当新 对象的插入使叶子结点中的单元个数超过m 时，需要进行结点的分裂操作。 分裂操作是将溢出的结点按一定的规则分为若干个部分。在其父结点删除 原来对应的单元，并加入由分裂产生的相应的单元。如果这样引起父结点的溢 出，则继续对父结点进行分裂操作。分裂操作也是个递归操作，它保证了空间 对象插入后的r 树仍能保持平衡。分裂算法按照复杂度，分为线性、二次和指 数分裂三种，实验证明，二次分裂方式在性能和计算复杂度上具有比较好的综 合指标。 从r 树中删除一个空间对象，首先要从r 树中查找到记录该空间对象所 在的叶子结点，这就是r 树的查找过程。查找时，从根结点开始，依次搜索 m b r 包含空间对象的单元所对应孩子结点为根结点的子树，查询方式利用了 r 树的结构特征，减少了检索的范围，提高了检索的效率。查找到该空间对象 所在的叶子结点后，删除其对应的单元。如果执行删除操作之后，该叶结点的 单元个数小于m ，则需要进行r 树的压缩操作，将单元数目过少的结点删除。 如果父结点因此单元数目也少于m ，则继续对父结点重复进行该操作。最后将 因进行结点调整而被删除的空间对象重新插入到r 树中。这就是r 树的压缩 操作，它使得r 树的每个结点单元数目不低于m 这个下限，从而保证了r 树 结点的利用率。 r 树的更新操作即为更新一个数据元组时，其对应的索引要从r 树中被删 哈尔滨理工人学工学硕士学位论文 除，然后再重新插入，这样才能保证在查找的时候正确发现该记录所在的位 置。 从r 树的操作上可以看出，让空间上靠近的空间对象拥有尽可能近的共 同祖先，能提高r 树的查询效率。形象地说，就是让聚集在一起的空间对象尽 可能早地组合在一起。r 树使用面积这个指标来衡量空间上的聚集，在插入操 作时，选择插入新对象后m b r 面积增长最小的结点为根的子树。而在分裂溢 出结点时，选择在各种分裂组合中，各部分的最小包含矩形面积和最小的结合 方式。然而，空间对象插入顺序的不同会形成不同结构的r 树，所以随着空间 对象的频繁插入和删除，会将r 树的查询效率带向不可预知的方向。 但是，从总体来讲，r 树是一种较好的索引结构。它基于对象分割的方法 来组织索引结构，索引空间的分割由空间对象来确定，不需要预知整个空间对 象所在的空间范围就能够建立索引。而且，r 树具有与b 树相似的结构和特 性，能够较好的与传统的关系型数据库相融合，更好地支持数据库的事务、滚 回和并发等功能。因此，国内外的空间数据库都广泛采用这种索引方法。 2 2 移动对象数据库索引技术 自从能够描述移动对象及其位置信息的移动对象数据库产生以来，基于这 种移动数据库的索引技术成为研究中的重点。 国内外对于移动对象数据库索引技术的研究还处于初级阶段，目前提出的 几种索引结构大部分都是以空间索引结构为基础发展而来的1 。对于动态环境 下的最近邻查询研究，也需要以能够索引移动对象未来位置的技术为基础，因 此，找到一种适合于进行未来最近邻查询的索引结构有着重要的意义。 2 2 1 移动对象索引技术分析 在移动对象索引技术中，有几种方法被用来索引移动对象的未来位置，适 合于进行未来最近邻查询。它们是分割索引空间的p m rq u a d t r e e 方法，基于 空间映射的h b n t r e e 、b + - t r e e 方法和索引结构矢量化的t p r 树方法。 这三种方法的主要区别如下： ( 1 ) 索引的空间不同假设移动对象在d 维空间运动，一种方法通过加入一 个时间维，将移动对象的未来轨迹转化为d + l 维空间的线来进行索引，基于 p m rq u a d t r e e 的索引方法即为这种方法，然而此方法需要不断存储线的信息， 可能会导致过量的存储。另外一种方法将移动对象的轨迹进行转换，将轨迹在 哈尔滨理t 大学t 学硕l ：学位论文 更高维的空间中映射成点，然后对这些点采用h b n t r e e 和b + - t r e e 进行索引。 为了适应这种数据的转化，这种情况下的查询也要进行这种转化，相对比较复 杂。还有一种方法则是在原始的d 维空间索引数据，采用速度矢量将索引结构 参数化，使得未来任何时刻的索引结构都能被计算出，能够索引高维空间的数 据，t p r 树就采用了这种方法，是一种非常直观的索引技术。 ( 2 ) 索引方法分割数据还是分割空间有的索引结构是分割空间的，按照索 引空间来建立索引，如p m rq u a d t r e e 将索引空间分为四部分。有的索引结构 则是分割数据的，按照数据点的位置建立索引。这种在自然空间索引数据，基 于数据分割的方法是比较自然的索引方法，t p r 树就采用了这种方法。 ( 3 ) 索引结构是否必须进行周期性的重建有的索引结构只是在一定时间内 是有效的，过期后则无效，因此在无效