华东师范大学学报(自然科学版) ›› 2022, Vol. 2022 ›› Issue (5): 184-194.doi: 10.3969/j.issn.1000-5641.2022.05.015

• 物流时空数据分析与智能优化理论 • 上一篇    

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

刘梦男, 许建秋*()   

  1. 南京航空航天大学 计算机科学与技术学院, 南京 211106
  • 收稿日期:2022-06-22 出版日期:2022-09-25 发布日期:2022-09-26
  • 通讯作者: 许建秋 E-mail:jianqiu@nuaa.edu.cn
  • 基金资助:
    国家自然科学基金 (61972198); 江苏省自然科学基金 (BK20191273)  

Two-level trajectory data partition algorithm based on query cost

Mengnan LIU, Jianqiu XU*()   

  1. College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China
  • Received:2022-06-22 Online:2022-09-25 Published:2022-09-26
  • Contact: Jianqiu XU E-mail:jianqiu@nuaa.edu.cn

摘要:

轨迹数据具有规模大、更新频繁的特点, 对轨迹数据的查询具有较高的性能要求. 为了提高轨迹数据的查询效率, 提出了两级轨迹数据划分算法: 在第一级划分中, 使用基于优化最小边界矩形(Minimum Bounding Rectangle, MBR)的轨迹数据划分方法将轨迹数据划分为子轨迹, 以提高轨迹数据的近似效果; 在第二级划分中, 按照时空范围, 使用网格结构对子轨迹进行分组. 基于划分算法提出了R-tree结点组织方法, 将划分后的轨迹数据自底向上地构建R-tree. 通过实验展示了所提的划分算法对查询效率的提升. 实验表明, 与基于轨迹段平均个数和基于组合运动特征这两种轨迹数据划分算法相比, 所提算法具有更好的查询性能, 查询效率分别平均提升了43.0%和30.5%.

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

Abstract:

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.

Key words: trajectory data, spatio-temporal query, trajectory partition, query optimization

中图分类号: