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

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

网络受限移动对象不确定性轨迹的索引

近年来,人们对于如何表示和处理移动对象的不确定性进行了研究,提出了一些较为有效的模型和算法.但是,在如何索引移动对象的不确定时空轨迹方面,相关的研究工作十分有限.为了解决上述问题,本文提出了一种网络受限移动对象不确定轨迹的索引结构(UTR-Tree),并给出了相关的索引更新及查询算法.在该索引结构的支持下,移动对象数据库不仅可以快速地处理对移动对象过去可能位置的查询,而且能够对其现在及将来的可能位置进行高效的查询处理.     

路网中移动对象轨迹索引的研究

索引结构对有效保存和查询移动对象的运动轨迹是至关重要的.根据交通网络中移动对象的轨迹特点,讨论了目前具有代表性的几种索引结构,重点分析了MON-Tree索引结构,将它与3D-Rtree进行了性能比较.在此基础上,提出并实现了一种基于MON-Tree的网络中移动对象轨迹数据库原型.     

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

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

移动对象数据库模型、查询语言及实时交通流分析

提出一种移动对象数据库模型——Dynamic Transportation Network Based Moving Objects Database(简称DTNMOD),并给出了DTNMOD中基于移动对象时空轨迹的网络实时动态交通流分析方法.在DTNMOD中,交通网络被表示成动态的时空网络,可以描述交通状态、拓扑结构以及交通参数随时间的变化过程;网络受限的移动对象则用网络移动点表示.DTNMOD 模型包含了完整的数据类型和查询操作的定义,因此可以在任何可扩充数据库(如PostgreSQL 或SECONDO)中实现,从而得到完整的数据库模型和查询语言.为了对相关模型的性能进行比较与分析,基于PostgreSQL 实现了一个原型系统并进行了一系列的实验.实验结果表明,DTNMOD 提供了良好的区域查询及连接查询性能.     

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

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

一种基于受限网络的移动对象索引

为了有效地支持城市交通网络中移动对象的过去、现在和将来的轨迹查询,在基于模拟预测的位置表示模型基础上,提出了一种两层R树加上一个表结构的复合索引结构AUC(Adaptive Unit Compounding).根据城市交通网的特征,采用了一种带有环形交叉口的元胞自动机模型模拟移动对象的将来轨迹,并用线性回归和圆弧曲线拟合分别得到对象在规则路段和交叉口的轨迹预测方程;根据移动对象的运动特性,采用了一种新的自适应单元(AU)作为索引结构的基本单位.实验表明,AUC索引的查询和更新性能都要优于TPR树和TB树.     

一种混合的时空数据库索引机制

近年来，时空数据库的应用得到迅速发展，在动态时空环境里，维持持续移动对象的位置信息是一个挑战。本文提出了一种新的索引机制，采用两种不同类型的索引结构，一种索引移动对象历史轨迹，一种能够有效地索引移动对象现在、最近、将来的位置信息，而且随着时间的推移，能够将两种索引结构内容快速过渡。在实现移动对象历史轨迹的完整或局部的有效查询的同时，又保证了移动轨迹的空间紧密性。     

一种基于城市交通网络的移动对象全时态索引

高效地管理移动对象以支持查询是一个重要课题.为了支持在城市交通网络上的移动对象过去、现在和将来位置查询,提出了一种新的索引技术.首先提出基于模拟预测的位置表示模型来改进对移动对象将来运动轨迹的预测精度;其次根据城市交通网的特征,设计了一种全新的动态结构自适应单元(AU),将其开发为一个基于R树的索引结构(current-Au);最后在AU的基础上进行扩展(past-AU)使其支持移动对象历史轨迹查询并且避免了大量的死空间.实验证明,AU索引优于传统的TPR树和TB树索引.     

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

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

受限网络移动对象不确定性轨迹的查询

针对移动对象轨迹的内在不确定性及其导致的查询精度较低的问题,将已有移动对象的空间轨迹不确定性模型应用于网络移动对象的轨迹表示中。在此基础上,将概率查询方法运用到受限网络移动对象的不确定轨迹查询中,提出移动对象轨迹的不确定性点查询和概率范围查询方法。实验结果表明,该方法具有较高的查询效率。     

移动对象轨迹时空相似性度量方法

在分析移动对象行为时,移动对象轨迹因包含大量的信息而具有重要的作用。在实际应用中移动对象常受限于空间网络而无法利用现有欧氏空间中轨迹及其距离处理技术。分析了道路网络空间轨迹相似性性质,提出一种移动对象轨迹建模的时空表示方法,能有效地将轨迹从道路网络空间转化到欧氏空间;同时提出了一种基于兴趣点POI（Points Of Interesting）距离的轨迹间相似性测量方法,有效地对轨迹进行化简并减少轨迹中节点的数目,从而降低算法时间复杂度。该方法不仅可以用于搜索相似轨迹,还可方便地应用到轨迹聚类的相关工作中。     

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

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

A Competitive Neural Network for Multiple Object Tracking in Video Sequence Analysis

Tracking of moving objects in real situation is a challenging research issue, due to dynamic changes in objects or background appearance, illumination, shape and occlusions. In this paper, we deal with these difficulties by incorporating an adaptive feature weighting mechanism to the proposed growing competitive neural network for multiple objects tracking. The neural network takes advantage of the most relevant object features (information provided by the proposed adaptive feature weighting mechanism) in order to estimate the trajectories of the moving objects. The feature selection mechanism is based on a genetic algorithm, and the tracking algorithm is based on a growing competitive neural network where each unit is associated to each object in the scene. The proposed methods (object tracking and feature selection mechanism) are applied to detect the trajectories of moving vehicles in roads. Experimental results show the performance of the proposed system compared to the standard Kalman filter.     

面向路网的移动对象全时态高效索引模型

针对现有索引模型的冗余搜索问题,考虑路网拓扑结构及交叉口转向约束条件,提出一种面向路网的移动对象全时态高效索引模型。采用添加临近路段信息的方法索引历史轨迹和实时位置信息,设计新型窗口查询算法,实现移动对象查找,并运用指数平滑法进行轨迹的预测。实验结果表明,该模型具有较好的更新及查询性能。     

搜索路网空间中时空相似轨迹

为了分析移动对象行为特征,需要一种度量轨迹间相似性的方法,虽然在欧氏空间检索移动对象相似轨迹的研究较多,但在路网空间这种研究还不多见。在实际应用方面,大多数移动对象位于路网空间而不是欧氏空间。本文研究了路网空间相似轨迹的特性,并提出了一种在路网空间搜索相似轨迹的度量方法。实验结果表明该方法不仅是搜索相似轨迹的实用技术,也是一种较好的轨迹聚类方法     

Indexing in-network trajectory flows

Indexing moving objects (MO) is a hot topic in the field of moving objects databases since many years. An impressive number of access methods have been proposed to optimize the processing of MO-related queries. Several methods have focused on spatio-temporal range queries, which represent the foundation of MO trajectory queries. Surprisingly, only a few of them consider that the objects movements are constrained. This is an important aspect for several reasons ranging from better capturing the relationship between the trajectory and the network space to more accurate trajectory representation with lower storage requirements. In this paper, we propose T-PARINET, an access method to efficiently retrieve the trajectories of objects moving in networks. T-PARINET is designed for continuous indexing of trajectory data flows. The cornerstone of T-PARINET is PARINET, an efficient index for historical trajectory data. The structure of PARINET is based on a combination of graph partitioning and a set of composite B⁺-tree local indexes. Because the network can be modeled using graphs, the partitioning of the trajectory data makes use of graph partitioning theory and can be tuned for a given query load and a given data distribution in the network space. The tuning process is built on a good quality cost model that is supplied with PARINET. The advantage of having a cost model is twofold; it allows a better integration of the index into the query optimizer of any DBMS, and it permits tuning the index structure for better performance. The tuning process can be performed before the index creation in the case of historical data or online in the case of indexing data flows. In fact, massive online updates can degrade the index quality, which can be measured by the cost model. We propose a specific maintenance process that results into T-PARINET. We study different types of queries and provide an optimized configuration for several scenarios. T-PARINET can easily be integrated into any RDBMS, which is an essential asset particularly for industrial or commercial applications. The experimental evaluation under an off-the-shelf DBMS shows that our method is robust. It also significantly outperforms the reference R-tree-based access methods for in-network trajectory databases.     

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

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