《基于R树移动对象预测位置查询》由会员分享，可在线阅读，更多相关《基于R树移动对象预测位置查询（7页珍藏版）》请在金锄头文库上搜索。
1、基于基于 R R 树移动对象预测位置查询树移动对象预测位置查询1胡国建胡国建 张张祺祺 夏夏胜凯胜凯（浙江海洋学院（浙江海洋学院 数理与信息学院数理与信息学院 浙江浙江 舟山，舟山，316004）摘要：摘要：当前对移动对象位置预测查询的研究中，索引结构是查询性能优良的关键。针对 现有方法中存在的缺陷，本文提出 R-tree 索引方法。R 树算法能有效的索引移动对象的现 在与预测的将来位置。R 树算法考虑移动对象的速度与方向来预测移动对象在不久将来的 大致位置。实验结果表明，采用 R-tree 索引结构具有最优的查询和更新性能。关键词：关键词： R 树; 移动对象; 位置预测;MovingMov
2、ing ObjectObject PredictionPrediction LocationLocation QueryQuery basedbased onon R-R- treetree Hu guojian，Zhang qi，Xia shengkai(Maths，Physics and Information College，Zhejiang Ocean University， Zhoushan Zhejiang 316000，China)AbstractAbstract: In the research of the prediction location query of the m
3、oving objects, the design of index structure is the key to performance. According to defects of the existing index methods, R-tree index method is proposed in this paper. R-tree algorithm can effectively index space moving object and predict the future positions. R-tree algorithm predicts the moving
4、 objects location through the speed and direction of object mobile bound. The experimental results show that R-tree index structure have a optimal search and performance.KeyKey wordswords：R-tree; Move objects; Location prediction;1 1 引引 言言移动计算、无线通讯和定位技术的快速发展使得跟踪和管理实际生活中的移动对象轨迹成为了现实。随着移动通信、移动定位技术的迅速发
5、展和移动终端设备（如车载、手持设备等）的不断普及，越来越多的应用（如车载导航、智能交通、实时监控、作战指挥控制等）要求在移动过程中实现对地理空间信息的实时获取。移动对象轨迹是物体在某一个时间段内所经过的路线。对于移动对象在一定时间内的预测位置查询处理技术成为了当前涉及移动对象轨迹信息的时空数据库研究领域的重点与热点之一。 传统的 B 树已经不能完全的满足于社会进步，人们需求。R 树在数据库等领域做出的功 绩是非常显著的。它把 B 树的思想很好的扩展到了多维空间，采用了 B 树分割空间的思想， 并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。，对移动对象位置基金项目：浙江省自然科学
6、基金(Y12F020080)，浙江省重大科技专项(2011C11046)作者简介：胡国建，男，本科生，A11 计算机。张祺，夏胜凯，男，本科生。查询索引方法大体分为两类：一类为对历史位置的提取；一类为对当前位置提取和对将来 位置的预测。它很好的解决了在高维空间搜索等问题。在 BiN-tree 中，引入对象标识辅助 索引，搜索 B tree，直接获取被更新对象在 TPN-tree 中的存取路径(对象的更新数据可简 化为(Old，P ，V )，然后执行删除和插入操作。能够有效而又简单的解决移动对象预测 位置的查询。移动对象是指对象的空间数据随时间的变化而连续变化的对象，它主要可以分为移动 点（mo
7、ving point）和移动区域（moving region）。移动点是指随时间而变化的空间对象 的位置（position）。对移动点的查询主要是要确定移动对象的位置。移动区域是指随时 间而变化的空间对象的位置及其形状。对移动区域的查询主要是要确定在特定时间内移 动对象的位置或形状。 移动对象数据库通常管理着数量非常庞大的移动对象。在查询处理时如果逐个扫描所 有的移动对象显然将会极大地影响系统的性能。移动对象的索引方法通常借鉴于空间数据 索引技术，不同之处在于移动对象的索引中有一维必然是时间维。已提出的移动对象索引 方法主要分为两类：1)索引移动对象过去与当前的位置；2)索引移动对象当前与将来
8、 的位置。1基于 R-tree 的移动对象索引技术迄今为止，一些好的关于移动对象索引技术的综述已被给出。例如，Gaede 等12给出了一个关于空间数据库中各种多维访问方法的综述；Mokbel 等13给出了一个关于已有的各种时空访问方法的综述。根据各种时空访问方法所支持的查询类型与时间，Mokbel 等将时空索引方法分成两类：索引过去、索引现在与预测将来位置，并对每类方法进行了简单讨论。另外，他们还简单地介绍了一些开放的并且可利用的索引工具，例如，数据库系统的通用查找树（Generalized Search Tree for Database Systems, GiST）和空间划分的通用查找搜索
9、树（Space-partitioning Generalized Search Tree, SP-GiST）等，这些索引工具可以帮助我们实现各种不同的时空访问方法。最近，Manolopoulos 等系统性给出了一个基于 R-tree 及其变体的移动对象索引方法的综述。他们详细讨论了 R-tree 及其变体的适用性，精确的代价模型，诸如并发控制、恢复以及并行处理等的实现问题等，并且还介绍了由一些数据库开发商所实现的 R-tree 及其变体。虽然他们给出了一个好的基于R-tree 及其它的变体的各种移动对象索引技术的综述，但是却没有考虑基于四叉树（quadtree）的移动对象索引技术和其它的移动对
10、象索引技术；下面我们将分别对三类移动对象索引技术及其各自相应的移动对象索引方法分别进行简单的讨论。 42 2 预测索引方法预测索引方法自从1984年Guttma n提出R-树以后，人们以此为基础，针对不同的时空操作需求提出 了各种改进方案，逐渐形成R树家族。其中，对移动对象位置查询索引方法大体分为两类： 一类为对历史位置的提取；一类为对当前位置提取和对将来位置的预测。2.12.1扩展扩展 TPR-treeTPR-tree 使其支持对象标识查询使其支持对象标识查询-ETPR_tree-ETPR_treeETPR-tree更新算法 我们假定Old是所有移动对象的唯一标识，即不同对象的Oid不同。更
11、新结构为 (Oid，(P ，V)更新算法分为3个步骤：步骤1：对象标识Oid查询。 步骤2：删除过时的对象。 步骤3：插入更新后的对象。 对象标识Oid查询以更新对象的标识Oid为索引树的查找目标，确定此对象在树叶子结 点中的位置。显然只需要用IdBR指示树的搜索方向，计算仅涉及一个维度(见算法1)。删除 和插入处理与TRP-tree类似。 算法1：对象标识查询算法 Queryld(OOid，N) if(N是叶子结点) for(N中的每一entry) if(entryOid与OOld相等) 记录()在树中的位置并返回elsefor(N中的每一entry) if()OidE entryIdBR)
12、 QueryId(OOld，entrypchild)；End Queryld2.22.2双索引结构双索引结构 R-treeR-tree解决TPR-tree不能有效支持对象标识查询缺陷的另一种方法是采用双索引结构：构建以 Oid为关键字(key)的B+-tree作为辅助索引，原有的TPR-tree结构和相应算法不变。在B+- tree中，叶子结点中的每一条目记录对象标识与此对象在TPR-tree的相应位置，即 (Oid，ptr)，其结构如图1所示。12342910 1112B+-treeTPR-tree图1 R-Tree索引结构 在BiN-tree中，引入对象标识辅助索引，搜索B+-tree，直
13、接获取被更新对象在TPN-tree中 的存取路径(对象的更新数据可简化为(Old，P ,V )，然后执行删除和插入操作(见算法2)、 R-tree的更新计算复杂度及结点访问数(I/O量)明显低于TPN-tree。当然，B+-tre的同步更 新会产生附加的I/O量，但其I/O量较小(等于B+-tree的高度)。算法2的复杂度为O(H+H2)次 I/O，其中H 和H2分别为B+-tree与TPN-tree的高度。 算法2：BiN-tree更新算法 Updatelndex(Oid，newkey) Path=IdTreeSearch()id)； N= TPRTreeReadNode(Path)； E=
14、GetEntry(N，Old)；NDelete(E)： NewPath=TPRTreeInsert(Oid，newkey)； IdTreeUpdate(Old，NewPath)； End Updatelndex；2.32.3索引现在与将来索引现在与将来二元变换：Kollios等使用二元变换(Duality transformation)把在时空域上的移动 对象的迹线转换到二维空间上的点。该索引方法的主要设计思想是用方程式xt=at+b来表示 一个二维空间中的点(a,b),其中a代表速度并作为水平维；而b代表参考位置并作为垂直维。 由于移动对象杂乱的分布在二元空间上，所以基于kd树(kd-tre
15、e)的空间索引方法被用来代 替R-tree。由于在初始的时空空间里的矩形区域查询被转换成在二元速度位置空间里的多 边形区域查询，所以由Goldstein等提出的算法可被用来有效的处理区域查询。 TPR-tree：Saltenis等提出了基于R*-tree的索引技术，称为时参R(TimeParameterized R-tree, TPR-tree)。TPR-tree能有效的索引在一维，二维，三维空间中的移动点对象的现 在与预测的将来位置。TPR-tree考虑移动对象的速度与方向来预测移动对象在不久将来的 大致位置2。并且通过考虑在树结构中可计算的位置来减少时间函数的频繁更新问题。同 时， TPR
16、-tree的更新算法也能使其自动的调整以适应于一个动态变化的数据集。 PR-tree：参数化R树(Parametric R-tree, PR-tree)与TPR-tree类似，但是PR-tree考 虑用参数化矩形来表示移动对象的空间区域。每个参数化矩形都有一个时间间隔来表示移 动对象运动的开始时间和结束时间。与TPR-tree考虑连续运动的对象不同，PR-tree还考虑 移动对象的结束时间。因此，一个移动对象在空间上用一个多边形来表示而不是连续的运 动迹线。给定运动的结束时间，一系列的移动对象可以用可计算的多边形来表示。 MP-tree：Lee等提出了一棵移动点树(Moving Point Tree, MP-tree)，它是一个用来 索引移动点对象数据的基于R-tree的索引方法。MP-tree使用投影操作(projection operation）来有效的支持诸如时间片查询与区域查询等的查询操作。但是使用投影操作带 来的一个缺点就是当结点被输入时需
