摘要
移动对象索引是支持海量移动对象管理的一项关键技术.目前的移动对象时空轨迹索引方法如STR-Tree、TB-Tree、FNR-Tree、MON-Tree等均直接以轨迹单元作为基本的索引记录单位,在位置更新时需要频繁地在索引中插入新的记录,从而严重地影响了数据库的总体性能.为了解决上述问题,文中提出一种网络受限移动对象的动态概略化轨迹R树索引(DSTR-Tree).DSTR-Tree将索引空间划分成等距格栅,并通过格栅单元对每一条移动对象轨迹进行概略化,然后以概略化轨迹单元为基本索引记录单位建立R树索引.由于概略化轨迹的粒度大大粗于原始轨迹,因此移动对象不需要在每次位置更新的同时触发索引更新,而仅需要在轨迹跨越当前格栅单元时才进行索引更新,从而显著地降低了索引更新的代价.实验结果表明,DSTR-Tree在移动对象数据库频繁位置更新的实际运行条件下,提供了良好的索引维护及总体查询处理性能.
Index is a key technology to improve the query processing performance of moving objects databases.However,current index methods for moving object trajectories,such as STR-Tree,TB-Tree,FNR-Tree,and MON-Tree,take trajectory units as the basic index records,and therefore,frequent insertions are needed when location updates occur in order to keep the consistency between the index and the trajectories in database,which greatly affects the overall performance of moving objects databases.To solve this problem,we propose a new index method,Dynamic Sketched-Trajectory R-Tree for Network-constrained Moving Objects（DSTR-Tree） in this paper.The DSTR-Tree divides the spatial-temporal space into equal-sized grid cells,transforms every trajectory into a sketched trajectory with each unit connecting two centers of the grid cells that the moving object travels through,and indices the sketched trajectory units as an R-Tree.Since the sketched trajectory has much coarser granularity than the original trajectory,the index updating cost can be greatly reduced-when a location update occurs,even though the original trajectory needs to be changed,the sketched trajectory may remain unchanged so that the DSTR-Tree does not need to be changed either.The experimental results show that the DSTR-Tree outperforms the previously proposed trajectory index methods in running moving objects databases with frequent location updates.
出处
《计算机学报》
EI
CSCD
北大核心
2012年第7期1448-1461,共14页
Chinese Journal of Computers
基金
国家自然科学基金项目(91124001
60970030)资助~~
关键词
移动对象
数据库
时空轨迹
概略化
索引
moving objects
database
spatial-temporal trajectory
sketched
index
