面向移动对象的高效预测范围聚集查询方法  

An Efficient Prediction Technique for Range Aggregation of Moving Objects

作　　者：廖巍[1] 景宁[1] 钟志农[1] 陈宏盛[1] 

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

出　　处：《计算机研究与发展》2007年第6期1015-1021,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60472031)~~

摘　　要：预测范围聚集查询是移动对象数据库中重要的查询类型之一.提出了一种PRA树高效预测范围聚集查询索引,对速度域进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶中,针对每个速度桶,提出了一种聚集TPR树索引,通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价.PRA树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性.提出了一种增强预测范围聚集查询EPRA算法,采用更精确的剪枝搜索准则,减少了查询所需要访问的节点代价.实验结果与分析表明,基于PRA树索引的EPRA查询算法具有良好的查询性能,优于通用的TPR*树索引.Predictive range aggregate （PRA） queries are one of the important researching areas in the moving object database. In this paper an efficient prediction technique, PRA-tree, is presented for range aggregation of moving objects. PRA-tree splits the velocity domain regularly, and classifies moving objects into different velocity buckets by their velocities. Then a TPR-tree, which is based on the TPR-tree structure and added with aggregate information in intermediate nodes, is used to index the moving objects in each buckets, thus reducing the disk accesses of PRA queries. A PRA-tree is supplemented by a hash index on leaf nodes, and uses bottom^up delete algorithm, thus having a good update performance and concurrency. Also developed for the PRA tree is an enhanced predictive range aggregate （EPRA） query algorithm which uses a more precise branch and bound searching strategy, reducing the disk I/O greatly. Experimental results and analysis show that the EPRA algorithm for PRA-tree has a good query performance and outperforms the popular TPR^＊ tree index.

关 键 词：预测范围聚集查询 PRA树 TPR树 EPRA算法 

分 类 号：TP392[自动化与计算机技术—计算机应用技术] TP311.13[自动化与计算机技术—计算机科学与技术]