基于速度分布的移动对象混合索引方法

TPR*树是目前广泛使用的移动对象当前及未来位置预测索引技术,但是其频繁更新及查询性能随着时间变化而急遽下降.文中提出了一种基于速度分布的移动对象混合索引HVTPR树,综合考虑移动对象在速度域和空间域中的分布,首先在速度域中对移动对象集进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶,每个速度桶中移动对象具有相近的速度矢量;对每个速度桶中的移动对象,则利用TPR树进行索引.HVTPR树索引增加了一个建于移动对象标识上的Hash辅助索引结构,并采用增强的自底向上更新(EBUU)算法以提高其频繁更新性能,具有很好的动态更新性能和并发性.实验表明,采用EBUU算法的HVTPR树索引动态更新及查询性能优于TPR*树等通用索引技术.     

利用覆盖区域设计与实现移动对象索引

对移动对象索引频繁更新问题进行了研究,提出了一种基于区域覆盖的空间索引结构虚拟网格四分树(virtual grid quadtree,VGQ);通过索引移动对象所在的区域而非移动对象本身来减少由于移动对象位置的改变而引起的索引结构的改变,并给出了近似连续范围查询算法及增量和自底向上优化策略。实验结果表明,VGQ在查询效率和空间使用上是一种有效的索引方法。     

支持频繁位置更新的不确定移动对象索引策略

移动数据采集和处理技术的迅速发展给研究人员提出了新的应用需求,如何在频繁位置更新应用中索引不确定移动对象的当前及未来位置信息成为当前的研究热点之一.TPU树是针对不确定移动对象的当前及未来位置信息索引的策略,其具有较高的概率域查询效率,但是其采用的传统自顶向下更新算法,存在频繁位置更新效率低下的问题.通过在TPU树上增加一个记录不确定移动对象状态特征的更新备忘录(UM)内存结构,文中提出了一种支持频繁位置更新的不确定移动对象索引策略TPU2M树,并在此基础之上提出了一种改进的基于备忘录(MMBU/I)的更新/插入算法.代价分析和实验仿真表明,采用MMBU/I算法的TPU2M树频繁更新性能大大优于TPU树和ABx树索引,且概率查询性能与传统索引大致相当,因此具有很好的实用价值和广泛的应用前景.     

移动对象数据库预测范围聚集查询技术研究

针对预测范围聚集查询处理技术,提出了一种面向移动对象的聚集TPR树索引。聚集TPR树索引在TPR树中间节点中加入移动对象聚集信息以减少预测范围聚集查询所需要的节点访问代价。并增加了一个建于移动对象标识上的哈希辅助索引结构以支持自底向上的删除搜索算法,具有很好的动态更新性能和并发性。提出了一种EPRA查询算法,采用更精确的剪枝搜索准则,大大减少了查询所需要访问的磁盘节点,具有良好的查询性能。     

基于Quadtree和Hash表的移动对象全时态索引

为解决大量移动对象位置频繁更新所带来的性能下降问题,提出一种基于改进的Quadtree和Hash表的QH全时态索引结构。这种新的索引结构可以支持移动对象全时态索引,在Hash表中通过存储移动对象指针来支持移动对象标识查询,并对Quadtree的叶子节点采用适时合并的方法来防范分支太深而造成的查询效率低下。实验证明,QH索引与TPR-tree相比,移动对象的更新效率更高、对象标识查询较优、范围查询性能相近。     

道路网络中移动对象的索引研究

为了能有效地实现网络中移动对象的过去、当前和将来轨迹的查询,提出了一种L2R索引,它由两层R树和一个链表结构组成。两层R树用以索引道路网络和移动对象过去的运动,对象当前的位置和将来的预测轨迹信息保存在链表中。L2R索引不仅可以支持网络中的移动对象的轨迹查询,尤其是可方便的在纵向链表中查询在同条路线上的所有对象。在此索引基础上文中实施了对移动对象的范围查询和点查询,最后通过实验表明L2R结构的索引和查询性能均要优越于TPR树。     

一种适合于频繁位置更新的网络受限移动对象轨迹索引

移动对象索引是支持海量移动对象管理的一项关键技术.目前的移动对象时空轨迹索引方法如STR-Tree、TB-Tree、FNR-Tree、MON-Tree等均直接以轨迹单元作为基本的索引记录单位,在位置更新时需要频繁地在索引中插入新的记录,从而严重地影响了数据库的总体性能.为了解决上述问题,文中提出一种网络受限移动对象的动态概略化轨迹R树索引(DSTR-Tree).DSTR-Tree将索引空间划分成等距格栅,并通过格栅单元对每一条移动对象轨迹进行概略化,然后以概略化轨迹单元为基本索引记录单位建立R树索引.由于概略化轨迹的粒度大大粗于原始轨迹,因此移动对象不需要在每次位置更新的同时触发索引更新,而仅需要在轨迹跨越当前格栅单元时才进行索引更新,从而显著地降低了索引更新的代价.实验结果表明,DSTR-Tree在移动对象数据库频繁位置更新的实际运行条件下,提供了良好的索引维护及总体查询处理性能.     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

移动点对象HR索引及反向最近邻查询

在此提出了一种基于速度分布的HR树索引结构,首先在速度域中对移动对象集进行规则划分,根据速度标量大小将移动对象划分到不同的速度树中,每棵速度树中移动对象具有相近的速度;对每棵速度树中的移动对象,则利用时间间隔进行划分。HR树索引增加了两个分别建于叶节点和根节点之上的Hash辅助索引结构,并基于HR树提出了反向最近邻查询算法,具有很好的动态更新性能和并发性。实验结果与分析表明,基于HR树索引的反向最近邻查询算法具有良好的更新及查询性能,优于通用的TPR树索引。     

改进的移动对象索引机制

针对R树结构在索引移动对象时存在的内部节点重叠问题,结合四叉树结构,提出一种R+树与四叉树(Quad树)混合的改进索引结构,采用懒惰更新算法以及扩充与收缩MBR方法,可同时索引移动对象历史及当前位置信息。仿真实验结果表明,该索引结构在查询数量较大时能够获得较高的查询效率。     

一种基于固定网络的移动对象运动轨迹索引模型

实际应用中移动对象通常运动在城市固定道路上,针对此特征研究人员已提出一些相关索引模型,但都存在一定的局限性,表现为索引模型只管理对象的历史位置信息或实时位置信息以及只对窗口查询或轨迹查询进行优化.IMTFN是一种基于固定网络的移动对象运动轨迹索引模型,管理移动对象的实时位置信息和历史轨迹信息,并且有效优化窗口查询及轨迹查询操作.IMTFN由一个管理固定网络的2D R^＊-Tree、一组管理移动对象运动轨迹的1D R^＊-Tree以及记录移动对象实时位置信息的Hash结构组成.最后通过实验IMTFN分别与STR-Tree与FNR-Tree进行性能比较,证明IMTFN模型提供速度更快的查询操作.     

基于LRS与GDF的移动对象轨迹建模及索引*

针对当前基于受限网络的移动对象管理研究中道路网模型简单,以及以空间平面坐标表达移动对象位置的方法不适合于道路网应用的问题,采用交通应用中流行的GDF路网模型并结合线性参考系统设计了一种针对道路网络的移动对象索引模型。与FNRtree及相关改进的索引方法相比,该方法在移动对象位置更新及添加上有更高的效率,在相关查询上结果更加合理。     

时空相点移动对象数据索引PM-Tree

随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点...     

网络受限移动对象过去、现在及将来位置的索引

提出了一种适合于网络受限移动对象数据库的动态轨迹R树索引结构(network-constrained moving objects dynamic trajectory R-Tree,简称NDTR-Tree).NDTR-Tree不仅能够索引移动对象的整个历史轨迹,而且能够动态地索引和维护移动对象的当前及将来位置.为了比较相关索引结构及算法的性能,进行了详细的实验.实验结果表明,与现有的基于道路网络的移动对象索引方法如MON-Tree和FNR-Tree等相比,NDTR-Tree有效地提高了对网络受限移动对象动态全轨迹的查询处理性能.     

一种实时的主动跟踪方法

针对单视角像机的视野局限性以及连续跟踪特定目标时运动目标实时检测的困难,提出了一种离散化活动像机运动的方法。先离散化像机运动;建立像机预置位表和背景索引表;然后,利用目标位置信息和运动信息判断像机转动情况,并结合对应的控制原理,实现了像机的调度;最后,利用通过计算机视觉方法确定了特定目标在不同离散空间的对应关系,实现了对特定目标大范围的主动跟踪和运动目标的实时检测。实验结果表明,对于复杂场景中特定运动目标大范围的主动跟踪具有较好的鲁棒性和实时性,并且可以实时提取场景中的运动区域。     

基于受限移动对象当前及将来时刻检索的时空索引结构研究

在给定的空间及时间范围内,如何构建高效的时空索引结构,以实现对移动对象快速有效的检索,是实现定位服务、智能交通、数字化战争等诸多应用中所迫切需要解决的问题.本文依据移动对象的运动特点,提出了一种面向当前及将来时刻快速更新及有效检索的索引结构—PQR树.PQR树是综合PMRQuad树和R*树的结构,首先依据道路分布用PMRQuad树将移动对象的索引空间实行粗略的层分割,将所有快速移动对象与道路相关联.然后用R*树索引分布在各个子空间块内的类静止对象.实验结果表明PQR树具有良好的更新和查询性能.     

支持频繁更新的移动对象混合索引方法

TPR-tree是目前广泛使用的移动对象当前及未来位置索引技术,但是其频繁更新性能低下.通过在TPR-tree上增加一个指向索引树中间节点的直接访问表（direct-access table）内存结构和建于叶节点之上的Hash辅助索引结构,提出了一种支持频繁更新的移动对象混合索引HTPR-tree,并提出了基于HTPR-tree的扩展自底向上（EBUU）更新算法.性能分析和实验表明,采用EBUU算法的HTPRtree动态更新性能大大高于TPR^＊-tree等索引,而查询性能仅仅稍逊.     

Fast Nearest-Neighbor Query Processing in Moving-Object Databases

A desirable feature in spatio-temporal databases is the ability to answer future queries, based on the current data characteristics (reference position and velocity vector). Given a moving query and a set of moving objects, a future query asks for the set of objects that satisfy the query in a given time interval. The difficulty in such a case is that both the query and the data objects change positions continuously, and therefore we can not rely on a given fixed reference position to determine the answer. Existing techniques are either based on sampling, or on repetitive application of time-parameterized queries in order to provide the answer. In this paper we develop an efficient method in order to process nearest-neighbor queries in moving-object databases. The basic advantage of the proposed approach is that only one query is issued per time interval. The time-parameterized R-tree structure is used to index the moving objects. An extensive performance evaluation, based on CPU and I/O time, shows that significant improvements are achieved compared to existing techniques.     

Indexing the Trajectories of Moving Objects in Networks*

The management of moving objects has been intensively studied in recent years. A wide and increasing range of database applications has to deal with spatial objects whose position changes continuously over time, called moving objects. The main interest of these applications is to efficiently store and query the positions of these continuously moving objects. To achieve this goal, index structures are required. The main proposals of index structures for moving objects deal with unconstrained 2-dimensional movement. Constrained movement is a special and a very important case of object movement. For example, cars move in roads and trains in railroads. In this paper we propose a new index structure for moving objects on networks, the MON-Tree. We describe two network models that can be indexed by the MON-Tree. The first model is edge oriented, i.e., the network consists of nodes and edges and there is a polyline associated to each edge. The second one is more suitable for transportation networks and is route oriented, i.e., the network consists of routes and junctions. In this model, a polyline also serves as a representation of the routes. We propose the index in terms of the basic algorithms for insertion and querying. We test our proposal in an extensive experimental evaluation with generated data sets using as underlying networks the roads of Germany. In our tests, the MON-Tree shows good scalabiliy and outperforms the competing index structures in updating (index creation) as well as in querying.*This work was partially supported by a grant Gu 293/8–l from the Deutsche Forschungsgemeinschaft (DFG), project Datenbanken für bewegte Objekte (Databases for Moving Objects).     

一种基于空间相依性的移动对象聚类算法

移动对象的聚类算法,要求能够适应移动对象移动模式动态变化的特点.针对该问题,提出了一种基于空间相依性的移动对象聚类算法.该算法首先计算移动对象之间的空间相依度,空间相依度考虑了移动对象之间的移动速度、方向及位置.当用户之间的空间相依度大于某一阈值时,认为对象之间可达,所有相依度可达对象划分为同一个群组,从而实现移动对象聚类.算法采用一段时间内对象的平均速度和方向代替即时速度和方向,能够有效降低重新聚类次数.实验及分析表明,该算法能够体现移动对象的移动特性,对于移动对象的聚类具有较高性能.