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

随着移动定位技术和无线通讯技术发展,移动对象的应用领域越来越广阔.位置随时间而变化的移动对象产生的时空数据具有规模大、多维性、结构复杂和关系复杂等特点.由于移动对象的运动轨迹大多被限定在特定的交通网络中,因此基于路网的移动对象索引成为时空数据索引研究的一个重要应用分支.目前,针对移动对象历史数据的区域查询优化的研究重点是如何提高窗口查询的效率.这类索引通常以同一线路为单位来组织轨迹数据的存储.索引通常采用两层的R-tree索引结构,上层的2D R-tree用于索引在某个区域内的线路,下层的2D R-tree用于索引某个时间段内在这些区域的移动对象.这类索引在处理轨迹信息的时间维度的时候,仅仅是把时间维度等同于空间的维度来进行R树维度的扩展.由于R树算法不能有效地降低最小限定矩形的空间堆叠问题,尤其是在数据量较大、数据维数增加时表现得更为明显.所以,为了提高路网中移动对象时空信息的存储以及查询的效率,本文则将轨迹信息中的时间数据和空间数据整合起来,提出了一种移动对象数据索引PM-tree(Phase-point Moving Object Tree).首先运用映射函数把路网中移动对象运动轨迹的二维时空矩形投影成带参数的一维"时空相点",并讨论了时空相点之间的偏序关系,建立了基于相点偏序划分的相点序分枝结构,为索引的建立提供了理论支撑.接着论文以MON-tree索引为基础,以相点序分枝结构来改进其下层索引结构,提出了时空相点移动对象数据索引,该索引能完成运动轨迹时空的一体化查询,能避免类R-tree索引中最小限定矩形堆叠导致的效率低下的问题,有效地缩小搜索空间.最后论文实现了索引的增量式动态更新管理.通过实验的对比分析,表明PM-tree索引不但能有效提高储存空间的利用率,"一次一集合"的查询模式还提高了查询性能.

Temporal-Spatial Phase Point Moving Object Data Indexing: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-dimensional rectangles,and mapped it into a set of single-dimensional temporal and spatial phase points with parameters.Secondly,the paper discussed the partial order relationship among the temporal and spatial phase points on the phase plane.By partitioning the phase points with the partial order,a Phase-Point Order Branching was constructed.Then,based on Mon-tree index,the paper improved its lower layer of index structure by using the Phase-Point Order Branching structure,and proposed the spatial-temporal phase point moving object data index.This Index can realize the query optimization by the integration of spatial information and temporal information as spatial phase points,also it can avoid the low efficiency caused by MBR overlap in R tree and effectively reduce the search space.Finally,the paper realized the incremental dynamic update management of index.By comparing the performance of PM-tree index with that of Mon-tree index,the experimental results show that the PM-tree index can not only effectively improve the utilization of storage space,but also improve the query performance.