基于查询代价的两级轨迹数据划分算法  

Two-level trajectory data partition algorithm based on query cost

作　　者：刘梦男 许建秋[1] LIU Mengnan;XU Jianqiu(College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China)

机构地区：[1]南京航空航天大学计算机科学与技术学院,南京211106

出　　处：《华东师范大学学报（自然科学版）》2022年第5期184-194,共11页Journal of East China Normal University(Natural Science)

基　　金：国家自然科学基金(61972198);江苏省自然科学基金(BK20191273)。

摘　　要：轨迹数据具有规模大、更新频繁的特点,对轨迹数据的查询具有较高的性能要求.为了提高轨迹数据的查询效率,提出了两级轨迹数据划分算法:在第一级划分中,使用基于优化最小边界矩形(Minimum Bounding Rectangle, MBR)的轨迹数据划分方法将轨迹数据划分为子轨迹,以提高轨迹数据的近似效果;在第二级划分中,按照时空范围,使用网格结构对子轨迹进行分组.基于划分算法提出了R-tree结点组织方法,将划分后的轨迹数据自底向上地构建R-tree.通过实验展示了所提的划分算法对查询效率的提升.实验表明,与基于轨迹段平均个数和基于组合运动特征这两种轨迹数据划分算法相比,所提算法具有更好的查询性能,查询效率分别平均提升了43.0%和30.5%.Trajectory data are typically large in scale and require frequent updates;hence, there are high performance requirements for trajectory queries. In order to improve the query efficiency of trajectory data,a two-level trajectory partition algorithm is presented herein. In the first partition, trajectory data was divided into sub-trajectories based on optimized minimum bounding rectangle(MBR) to improve the approximate effect of trajectory data. In the second partition, the sub-trajectories were grouped by the grid structure according to spatio-temporal characteristics. A packing method of R-tree was proposed based on the partition algorithm, and the divided trajectory data was packed into the R-tree from bottom to top.Finally, compared with a method based on the average number or average size of trajectory segments,experimental results show that the proposed method offers better query performance than the two other methods based on the average number of trajectory segments and combined movement features;in fact, the query efficiency is improved by 43% and 30.5%, respectively.

关 键 词：轨迹数据 时空查询 轨迹划分 查询优化 

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