Journal of East China Normal University(Natural Science) ›› 2022, Vol. 2022 ›› Issue (5): 184-194.doi: 10.3969/j.issn.1000-5641.2022.05.015

• Spatio-temporal Data Analysis and Intelligent Optimization Theory for Logistics • Previous Articles    

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

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

CLC Number: