一种动态紧缩的移动对象索引结构  

Dynamic packing index structure for moving objects

作　　者：卢炎生[1] 彭祥礼[1] 潘鹏[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2007年第2期50-53,共4页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：湖北省自然科学基金资助项目(ABA048)

摘　　要：DPTI(dynamic packing trajectory index)是R*-Tree和链表组合而成的移动对象索引结构.用链表来存储轨迹数据,做到了严格的轨迹保护.轨迹的分段处理对每条轨迹进行了逻辑划分,每个划分对应链表中的若干条线段.R*-Tree存取的最小单元不再是轨迹的线段,而是各个划分所对应的线段集.基于对轨迹更新的简单预测,在轨迹不断更新的过程中对存放历史信息的结点进行紧缩,使得叶子结点拥有更高的存储利用率.DPTI的两层索引结构做到了严格的轨迹保护,分段处理使得各段轨迹能够按照时空位置插入R*-Tree,动态紧缩提高了索引的存储利用率,这些改进都促使DPTI得到了较好的时空查询效率.Dynamic packing trajectory index （DPTI）, a hybrid indexing structure, composing of R-tree and link-list, is proposed in which trajectory preservation is achieved by using link-list and a more reasonable algorithm to partition a trajectory into several subsections is adopted to decrease dead space of trajectory MBR （minimal bounding rectangle）. The leafnode＇s entry of DPTI isn＇t pointing to a line segment, but a set of line segments. DPTI has a new update policy of trajectory and then forecasts the increase of entry which caused by trajectory update. Based on the forecast, a method named dynamic packing policy can pack the nodes which save historical data step by step while the trajectory dataset is very large. DPTI is two-level index structure and guarantees strict trajectory preservation. The method of partition keeps neighboring line segments to be clustered in nodes. Dynamic packing policy enhances the storage utilization of index. Therefore the spatio-temporal queries of DPTI are improved efficiently.

关 键 词：移动对象 轨迹 索引 

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