基于速度分布的移动对象混合索引方法  

Hybrid Indexing of Moving Objects Based on Velocity Distribution

作　　者：廖巍[1] 唐桂芬[1] 景宁[1] 钟志农[1] 

机构地区：[1]国防科学技术大学电子科学与工程学院,长沙410073

出　　处：《计算机学报》2007年第4期661-671,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(60472031);国家"八六三"高技术研究发展计划项目基金(2003AA5110)资助.

摘　　要：TPR*树是目前广泛使用的移动对象当前及未来位置预测索引技术,但是其频繁更新及查询性能随着时间变化而急遽下降.文中提出了一种基于速度分布的移动对象混合索引HVTPR树,综合考虑移动对象在速度域和空间域中的分布,首先在速度域中对移动对象集进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶,每个速度桶中移动对象具有相近的速度矢量;对每个速度桶中的移动对象,则利用TPR树进行索引.HVTPR树索引增加了一个建于移动对象标识上的Hash辅助索引结构,并采用增强的自底向上更新(EBUU)算法以提高其频繁更新性能,具有很好的动态更新性能和并发性.实验表明,采用EBUU算法的HVTPR树索引动态更新及查询性能优于TPR*树等通用索引技术.TPR＊ -tree is the most popular indexing method for the current and future position of moving objects,but its frequent updates performance is very low. In this paper a hybrid indexing method, HVTPR-tree, which is based on the velocity distribution is presented for moving objects with frequent updates. HVTPR-tree takes into account the distribution of both velocity domain and space domain. First the velocity domain is split regularly, and moving objects are classified into different velocity buckets by their velocities, thus the moving objects in one bucket have similar velocities. Then TPR-tree is used to index the moving objects in each bucket. To support frequent updates a supplemented hash index on leaf nodes is added to HVTPR-tree. Also an extended bottom-up update algorithm is developed for HVTPR-tree, thus having a good dynamic update performance and concurrency. Experimental results show that HVTPR-tree＇s update and query performance outperform any other indexing methods including TPR＊-tree.

关 键 词：移动对象索引 TPR＊树 HVTPR树 EBUU算法 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]