时空相点移动对象数据索引PM-Tree  

Temporal-Spatial Phase Point Moving Object Data Indexing:PM-Tree

作　　者：汤娜[1] 朱展豪 李晶晶 汤庸[1] 叶小平[1] TANG Na;ZHU Zhan-Hao;LI Jing-Jing;TANG Yong;YE Xiao-Ping(School of Computer Science,South China Normal University,Guangzhou 510631)

机构地区：[1]华南师范大学计算机学院,广州510613

出　　处：《计算机学报》2021年第3期579-593,共15页Chinese Journal of Computers

基　　金：国家自然科学基金(61772211,U1811263);国家重点研发计划(2018AAA0101300);广东省教育厅创新团队(粤教科函2018-64/8S0177);广州市科技计划项目(国际合作)(201807010043)资助。

摘　　要：随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点是如何提高窗口查询的效率.这类索引通常以同一线路为单位来组织轨迹数据的存储.索引通常采用两层的R-tree索引结构,上层的2D R-tree用于索引在某个区域内的线路,下层的2D R-tree用于索引某个时间段内在这些区域的移动对象.这类索引在处理轨迹信息的时间维度的时候,仅仅是把时间维度等同于空间的维度来进行R树维度的扩展.由于R树算法不能有效地降低最小限定矩形的空间堆叠问题,尤其是在数据量较大、数据维数增加时表现得更为明显.所以,为了提高路网中移动对象时空信息的存储以及查询的效率,本文则将轨迹信息中的时间数据和空间数据整合起来,提出了一种移动对象数据索引PM-tree(Phase-point Moving Object Tree).首先运用映射函数把路网中移动对象运动轨迹的二维时空矩形投影成带参数的一维"时空相点",并讨论了时空相点之间的偏序关系,建立了基于相点偏序划分的相点序分枝结构,为索引的建立提供了理论支撑.接着论文以MON-tree索引为基础,以相点序分枝结构来改进其下层索引结构,提出了时空相点移动对象数据索引,该索引能完成运动轨迹时空的一体化查询,能避免类R-tree索引中最小限定矩形堆叠导致的效率低下的问题,有效地缩小搜索空间.最后论文实现了索引的增量式动态更新管理.通过实验的对比分析,表明PM-tree索引不但能有效提高储存空间的利用率,"一次一集合"的查询模式还提高了查With the development of mobile location technology and wireless communication technology,the application of moving objects has exhibited a broad application prospect.As moving objects’position varies as time goes on,the spatial data and temporal data generated continuously by moving objects has the characteristics of multi-dimension,complex data structure,massive data scale and complex data relationship.Usually the trajectory of moving objects was confined to a specific road network,so the index of moving objects based on the road network has become an important branch of the research of temporal spatial data index.At present,for the query optimization of the historical data of moving objects,the research focus on how to improve the efficiency of the window query.Usually such kind of indexes partitioned the trajectory data of moving objects by route,so the trajectory data of moving objects on a specific route was stored together.So this kind of indexes was a two-layer R-tree index structure,the upper layer was a 2 D R-tree for indexing the routes in a region,and the lower one was also a 2D R-tree for indexing the moving objects in the ranges of routes in a certain period of time.In the view of these papers,the dimension of time in trajectory information was the same as the dimension of space.So dealing with the dimension of time,this kind of temporal spatial moving object index just extended the temporal dimension to R tree.However,because the algorithm of R tree cannot effectively reduce space overlapping of Minimal Bounding Rectangle(MBR),and it is more serious when the data volume is large and the dimension increases.In order to improve the efficiency of spatial-temporal trajectory information storage and query of moving objects in road network at some interval,this paper integrated temporal data and spatial data,and proposed a temporal-spatial phase point moving object data index(PM-Tree index).Firstly,this paper modeled the spatial trajectory of the moving object at some interval as a set of two-dimensiona

关 键 词：时空矩形 路网 移动对象索引 时空映射 相点偏序 

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