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

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

作　　者：李红军[1,2] 唐常杰[1] 乔少杰[3] 代术成[1] 王悦[1] 郑皎凌[1] 

机构地区：[1]四川大学计算机学院数据库与知识工程研究所,四川成都610065 [2]西南科技大学计算机学院,四川绵阳621010 [3]西南交通大学信息科学与技术学院,四川成都610031

出　　处：《四川大学学报（工程科学版）》2010年第2期118-125,共8页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家自然科学基金资助项目(600773169);国家"十一五"科技支撑计划(2006BAI05A01);国家博士后科学基金资助项目(20090461346)

摘　　要：受限网络中移动对象不确定轨迹的有效索引是移动对象数据库中的研究重点。针对现有方法的不足,提出了一种新的不确定轨迹索引结构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.

关 键 词：移动对象数据库 受限网络 不确定性 轨迹 索引 

分 类 号：TP311.132[自动化与计算机技术—计算机软件与理论]