UTR^＊-Tree：受限网络中移动对象不确定轨迹索引模型

UTR^＊-Tree： An Uncertain Trajectories Model for Indexing Moving Objects in Constrained Networks

受限网络中移动对象不确定轨迹的有效索引是移动对象数据库中的研究重点。针对现有方法的不足,提出了一种新的不确定轨迹索引结构UTR*-Tree。该索引结构采用静态和动态相结合存储管理移动对象,将变化极小的受限道路网络作为静态部分使用2维空间R*-Tree进行管理;将移动对象位置则作为动态信息采用R*-Tree和Hash数组协同管理。借助该结构,移动对象数据库不仅可以快速地处理对移动对象过去可能位置的查询,而且能够对其现在及将来的可能位置进行高效的查询处理。实验结果表明同目前有代表性的轨迹索引结构UTR-Tree相比,该索引结构在维护性能上提高了一个数量级,在查询性能上平均提高了约25%。

A novel index structure named UTR＊ -Tree was proposed for indexing uncertain trajectories.This index combined the dynamic and the static storage structure to manage the moving objects,which treated the constrained networks （where roads nearly keep unchanged） as the static factor and used a 2-dimensional R^＊ -Tree to manage the moving objects.An R^＊ -Tree and hash structure were also applied to manage the position information of moving objects,which was considered to be the dynamic operation.The index can obtain the possible historical positions of moving objects from the moving objects database as well as efficiently find the current and future possible positions of moving objects.The experimental results showed that the index outperforms the traditional UTR-Tree which is a representative index structure for uncertain trajectories;The performance of node maintenance is improved by one order of magnitude,and the query performance is increased by about 25% on average.