Spatio-temporal Data Analysis and Intelligent Optimization Theory for Logistics

Two-level trajectory data partition algorithm based on query cost

  • Mengnan LIU ,
  • Jianqiu XU
Expand
  • College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China

Received date: 2022-06-22

  Online published: 2022-09-26

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.

Cite this article

Mengnan LIU , Jianqiu XU . Two-level trajectory data partition algorithm based on query cost[J]. Journal of East China Normal University(Natural Science), 2022 , 2022(5) : 184 -194 . DOI: 10.3969/j.issn.1000-5641.2022.05.015

References

1 张林, 汤大权, 张翀. 时空索引的演变与发展. 计算机科学, 2010, 37 (4): 15- 20,26.
2 赵馨逸, 黄向东, 乔嘉林, 等. 基于不均匀空间划分和 R 树的时空索引. 计算机研究与发展, 2019, 56 (3): 666- 676.
3 CHAKKA P V, EVERSPAUGH A C, PATEL J M. Indexing large trajectory data sets with SETI [C/OL]// First Biennial Conference on Innovative Data Systems Research, CIDR 2003. (2003-01-05)[2022-06-09]. https://www.cidrdb.org/.
4 GUTTMAN A. R-trees: A dynamic index structure for spatial searching [G]// Readings in Database Systems. San Francisco: Morgan Kaufmann Publishers Inc., 1994: 125-135.
5 YUE Z W, ZHANG J W, ZHANG H B, et al. Time-based trajectory data partitioning for efficient range query [C]// International Conference on Database Systems for Advanced Applications. Cham: Springer, 2018: 24-35.
6 TANG J, LIU L F, WU J G. A trajectory partition method based on combined movement features [J]. Wireless Communications and Mobile Computing, 2019, 2019: 7803293. DOI: 10.1155/2019/7803293.
7 MOUASVI S M, HARWOOD A, KARUNASEKERA S, et al. Geometry of interest (GOI): Spatio-temporal destination extraction and partitioning in GPS trajectory data. Journal of Ambient Intelligence and Humanized Computing, 2017, 8 (3): 419- 434.
8 LEE J G, HAN J, WHANG K Y. Trajectory clustering: a partition-and-group framework [C]// Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. ACM, 2007: 593-604.
9 MASCIARI E. Trajectory clustering via effective partitioning [C]// International Conference on Flexible Query Answering Systems. Berlin: Springer, 2009: 358-370.
10 HADJIELEFTHERIOU M, KOLLIOS G, TSOTRAS V J, et al. Efficient indexing of spatiotemporal objects [C]// International Conference on Extending Database Technology. Berlin: Springer, 2002: 251-268.
11 RASETIC S, SANDER J, ELDING J, et al. A trajectory splitting model for efficient spatio-temporal indexing [C]// VLDB’05: Proceedings of the 31st International Conference on Very Large Data Bases. VLDB Endowment, 2005: 934-945.
12 THEODORIDIS Y, SELLIS T. A model for the prediction of R-tree performance [C]// Proceedings of the 15th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM, 1996: 161-171.
13 李松, 崔环宇, 张丽平, 等. 基于CURE聚类算法的静态R树构建方法[J]. 计算机科学, 2015, 42(10): 193-197.
14 LEUTENEGGER S T , LOPEZ M A , EDGINGTON J. STR: A simple and efficient algorithm for R-tree packing [C]// Proceedings 13th International Conference on Data Engineering. IEEE, 1997: 497-506. DOI: 10.1109/ICDE.1997.582015.
15 BECKMANN N, KRIEGEL H P, SCHNEIDER R, et al. The R*-tree: An efficient and robust access method for points and rectangles [C]// SIGMOD Conference. ACM, 1990: 322-331.
16 GüTING R H, BEHR T, DüNTGEN C. SECONDO: A platform for moving objects database research and for publishing and integrating research implementations [G]// Bulletin of the IEEE Computer Society Technical Committee on Data Engineering. IEEE, 2010: 56-63.
Outlines

/