The rapid advances in mobile data collecting and processing technology has proposed the researchers new challenges: how to monitor the current and future positions of uncertain moving objects under frequent and high extent updates. TPU-tree is currently a popular indexing method for the current and future positions of uncertain moving objects. It can speed up the probabilistic range query efficiency, but the traditional top-down update method of TPU-tree has made its frequent updates performance very low. In this paper, we propose the TPU2M-tree for moving objects with frequent updates, which is based on TPU-tree, supplemented by a memory-based update-memo structure recording the state of uncertain moving objects. Furthermore, a modified memo-based update/insert algorithm is developed for TPU2M-tree. Cost analyses and experimental evaluations demonstrate that the TPU2M-tree outperforms significantly any other indexing method including TPU-tree and Abx-tree with frequent updates, while yielding similar probabilistic query performance. TPU2M-tree has more practical values and comprehensive application foreground than other indexing methods.%移动数据采集和处理技术的迅速发展给研究人员提出了新的应用需求,如何在频繁位置更新应用中索引不确定移动对象的当前及未来位置信息成为当前的研究热点之一.TPU树是针对不确定移动对象的当前及未来位置信息索引的策略,其具有较高的概率域查询效率,但是其采用的传统自顶向下更新算法,存在频繁位置更新效率低下的问题.通过在TPU树上增加一个记录不确定移动对象状态特征的更新备忘录(UM)内存结构,文中提出了一种支持频繁位置更新的不确定移动对象索引策略TPU2M树,并在此基础之上提出了一种改进的基于备忘录(MMBU/I)的更新/插入算法.代价分析和实验仿真表明,采用MMBU/I算法的TPU2M树频繁更新性能大大优于TPU树和ABx树索引,且概率查询性能与传统索引大致相当,因此具有很好的实用价值和广泛的应用前景.
展开▼
