UTR*-Tree:受限网络中移动对象不确定轨迹索引模型
UTR*-Tree: An Uncertain Trajectories Model for Indexing Moving Objects in Constrained Networks
作者：李红军(1.四川大学 计算机学院 数据库与知识工程研究所, 四川 成都 610065;2.西南科技大学 计算机学院, 四川 绵阳 621010)；唐常杰(四川大学 计算机学院 数据库与知识工程研究所, 四川 成都 610065)；乔少杰(西南交通大学 信息科学与技术学院, 四川 成都 610031)；代术成(四川大学 计算机学院 数据库与知识工程研究所, 四川 成都 610065)；王悦(四川大学 计算机学院 数据库与知识工程研究所)；郑皎凌(四川大学计算机学院 数据库与知识工程研究所)
Author：Li Hongjun(1.Inst. of Database and Knowledge Eng., School of Computer Sci., Sichuan Univ., Chengdu 610065,China;2.College of Computer Sci.,South West Univ. of Sci. and Technol.,Mianyang 621010,China)；Tang Changjie(Inst. of Database and Knowledge Eng., School of Computer Sci., Sichuan Univ., Chengdu 610065,China)；Qiao Shaojie(School of Info. Sci. and Technol., Southwest Jiaotong Univ.,Chengdu 610031,China)；(Inst. of Database and Knowledge Eng., School of Computer Sci., Sichuan Univ., Chengdu 610065,China)；(Inst. of Database and Knowledge Eng., School of Computer Sci., Sichuan Univ.)；(Inst. of Database and Knowledge Eng., School of Computer Sci., Sichuan Univ.)
收稿日期：2009-10-10 年卷（期）页码：2010,42(2):118-125
期刊名称：工程科学与技术
Journal Name：Advanced Engineering Sciences
关键字：移动对象数据库;受限网络;不确定性;轨迹;索引
Key words：moving objects databases; constrained network; uncertain; trajectory; index
基金项目：国家自然科学基金资助项目(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.
【关闭】
