Two-level trajectory data partition algorithm based on query cost

doi:10.3969/j.issn.1000-5641.2022.05.015

Abstract

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:

TP392

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.

Figures/Tables 9

Fig.1

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

References 16

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.

符号	释义
$ {T} $	轨迹
$ {u_i} $	轨迹的第 $ {i} $ 个轨迹段
$ {q} $	查询窗口
D	磁盘访问次数(磁盘I/O次数)
$ {h} $	R-tree高度
$ f $	R-tree结点最大容纳条目个数
$ {{S}}_{{n}} $	划分段数为 $ {n} $ 时, 拓展MBR的大小
${S}_{ {B^O},{n} }$	划分段数为 $ {n} $ 时, 用 $ {B^O} $ 对应的划分方式划分后MBR的大小

[1]	Wei JIAN, Zirui HU, Rong ZHANG. Online analytical processing query cardinality estimation capability evaluation [J]. Journal of East China Normal University(Natural Science), 2024, 2024(5): 141-151.
[2]	Shuai ZHANG, Huiqi HU, Yaoqiang XU, Xuan ZHOU. Time series database query optimization for anomaly detection [J]. Journal of East China Normal University(Natural Science), 2023, 2023(2): 119-131.
[3]	Ting CHEN, Zhaokun XIANG, Jinkai XU, Rong ZHANG. Benchmarking join order selection of query optimizers [J]. Journal of East China Normal University(Natural Science), 2022, 2022(5): 48-60.
[4]	ZHANG Jing-wei, DING Zhi-jun, YANG Qing, ZHANG Hui-bing, ZHANG Hai-tao, ZHOU Ya. Storage and load balancing for large-scale comment data on heterogeneous Redis cluster [J]. Journal of East China Normal University(Natural Sc, 2017, 2017(5): 20-29.
[5]	LIU Zhi, LIU Hui-ping, ZHAO Da-peng, WANG Xiao-ling. Business circle population mobility statistics based on mobile trajectory data [J]. Journal of East China Normal University(Natural Sc, 2017, (4): 97-113,138.
[6]	MAO Si-yu, ZHANG Li-jun, ZHANG Xiao-fang, GAO Jin-tao, LI Zhan-huai. Optimization strategies of correlated subquery for distributed database [J]. Journal of East China Normal University(Natural Sc, 2016, 2016(5): 56-66.
[7]	Bao Ting, Zhang Zhi-gang, Jin Che-qing. An urban population flow analysis system based on mobile big data [J]. Journal of East China Normal University(Natural Sc, 2015, 2015(5): 162-171.
[8]	JIANG Jun-wen,WANG Xiao-ling. Review on trajectory data compression [J]. Journal of East China Normal University(Natural Sc, 2015, 2015(5): 61-76.