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

位置不确定性是移动对象的重要特点之一。已有的不确定移动对象索引技术旨在提高查询效率,但是当移动对象位置频繁更新时,存在更新代价较大的问题。针对移动对象频繁位置更新引起的开销增加问题,在TPU-tree索引结构上支持移动对象群组划分策略,给出了一种适用于频繁位置更新的索引结构GTPUtree。在此基础上提出了基于空间轨迹相似度的群组划分算法STSG(spatial trajectory of similarity group)和不确定移动对象群组更新算法。GTPU-tree通过减少同一分组中移动对象的更新次数,降低磁盘I/O次数,从而降低更新代价。通过实验对基于GTPU-tree和TPU2M-tree等索引结构的算法效率进行了对比分析,结果表明GTPU-tree相比于TPU2M-tree在移动对象数量较大时,GTPU-tree的更新代价将低于TPU2M-tree;与TPUtree相比插入性能提高约30%,更新代价降低约35%。     

基于GPS车辆跟踪系统的移动对象数据库应用研究

本文结合GPS车辆实时跟踪应用系统,利用移动对象数据库技术,对移动车辆的运动空间及时间进行分割,建立了移动目标数据库的数据模型、数据结构以及索引结构,实现实时更新车辆位置信息,有效地回放移动车辆的历史行驶轨迹,预测车辆将来的运动路线。     

基于路网的移动对象动态双层索引结构

为了支持对大规模不确定性移动对象当前及将来位置的查询,亟需设计更加有效和高效的索引结构.当前索引算法主要考虑索引建立和维护的效率问题或关注基于索引进行查询时的准确性,对索引建立维护以及查询时性能综合考虑的研究较少.针对已有方法的不足,提出基于路网的移动对象动态双层索引结构DISC-tree,对静态路网信息采用R~*-tree索引,对实时更新的移动对象运动轨迹采用结点更新代价较小的R-tree进行索引,设计哈希表和双向链表辅助结构对索引协同管理.成都市真实地图数据集上的实验结果表明:相比于经典的NDTRtree,DISC-tree在索引建立和维护方面时间代价平均减少39.1%,移动对象轨迹查询时间代价平均减少24.1%;相比于FNR-tree,DISC-tree的范围查询准确率平均提高约31.6%.     

公路环境下支持高效更新的时空数据索引结构

随着定位技术在各个领域的应用普及,降低时空数据索引结构中的更新代价已经成为当前很多实际应用的热点研究问题,如定位服务、交通控制等。提出一种针对公路网络中移动对象的索引结构——NLUR-Tree(Network-based Lazy Update R-tree)。NLUR-Tree不但借助于缓冲插入和缓冲删除来减少更新代价,而且还利用公路网络中对象移动的运动模式来提高更新效率。其次,NLUR-Tree还利用缓冲池来管理内存磁盘空间,在一定程度上解决了移动对象在公路网络分布的不均衡性带来的问题。最后,实验证明了NLUR-Tree要明显优于现有的同类型索引结构。     

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

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

基于更新日志的移动对象索引方法

在TPR-tree上增加一个基于内存的更新日志,实现一种支持频繁更新的移动对象索引ULTPR-tree,采用分组更新方法对移动对象记录进行批量删除,从而减少ULTPR-tree索引结构的删除维护代价。理论分析和实验结果表明,ULTPR-tree的动态更新性能优于TPR-tree和HTPR-tree。     

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

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

移动对象位置预测的索引方法

当前对移动对象位置预测查询的研究中,索引结构的查询性能成为关注的热点,而忽视其更新代价。针对现有方法中存在的更新缺陷,本文以TPR-tree为基础提出两种索引方法（ETPR-tree和BiR-tree）。实验结果表明,采用辅助索引结构的BiR-tree具有最优的查询和更新性能。     

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

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

TPR^＊树索引构建及其动态维护方法

提出一种新的TPR^＊树索引构建方法,在根节点层利用速度矢量对移动对象集进行划分,根据速度矢量的大小将移动对象聚集到不同子节点中,并逐层构建TPR^＊树。在根节点层用溢出桶存储插入的移动对象记录,同时对TPR^＊树索引进行批量插入更新,以减少其插入更新维护的代价。实验结果表明,该方法是可行的。