经典轨迹的相似度量快速算法

doi:10.3969/j.issn.1001-506X.2020.10.06

Abstract

Abstract:

In view of the time-consuming of the classical trajectory similarity measurement, a fast similarity measurement algorithm based on the longest common subsequence (LCS) is proposed by using the trajectory compression algorithm. Firstly, the real-time trajectory is compressed to reduce the number of the trajectory point. Secondly, based on the distance between the point of the classical trajectory and the line segment of the real-time trajectory, the LCS length between the classical trajectory and the real-time trajectory is calculated according to the improved multi-to-one LCS length formula. Finally, the ratio of the LCS length to the point number of the classical trajectory is taken as the similarity of the classical trajectory. The experimental results show that the calculation time can be reduced by more than 60% through the trajectory compression.

Key words: longest common subsequence (LCS), trajectory similarity measurement, trajectory compression, fast computation, classical trajectory

CLC Number:

TP301

Qiandong WANG. Fast algorithm of similarity measurement for classical trajectory[J]. Systems Engineering and Electronics, 2020, 42(10): 2189-2196.

Figures/Tables 7

Fig.1

Fig.2

Fig.3

Fig.4

Table 1

Table 2

Table 3

References 20

1	李建江, 陈玮, 李明, 等. 基于网格热度值的船舶规律路径提取算法[J]. 计算机研究与发展, 2018, 55 (5): 908- 919.
	LI J J , CHEN W , LI M , et al. The algorithm of ship rule path extraction based on the grid heat value[J]. Journal of Computer Research and Development, 2018, 55 (5): 908- 919.
2	ANDRIENKO G , ANDRIENKO N , FUCHS G , et al. Clustering trajectories by relevant parts for air traffic analysis[J]. IEEE Trans.on Visualization and Computer Graphics, 2018, 24 (1): 34- 44.
3	ESTER M, KRIEGEL H P, XU X.A density-based algorithm for discovering clusters in large spatial databases with noise[C]//Proc.of the International Conference on Knowledge Discovery and Data Mining, 1996: 226-231.
4	毛嘉莉, 金澈清, 章志刚, 等. 轨迹大数据异常检测:研究进展及系统框架[J]. 软件学报, 2017, 28 (1): 17- 34.
	MAO J L , JIN C Q , ZHANG Z G , et al. Anomaly detection for trajectory big data:advancements and framework[J]. Journal of Software, 2017, 28 (1): 17- 34.
5	AGRAWAL R, FALOUTSOS C, SWAMI A.Efficient similarity search in sequence databases[C]//Proc.of the International Conference on Foundations of Data Organization and Algorithms, 1993: 69-84.
6	KEOGH E , RATANAMAHATANA C A . Exact indexing of dynamic time warping[J]. Knowledge and Information Systems, 2005, 7 (3): 358- 386. doi: 10.1007/s10115-004-0154-9
7	GUO N , MA M Y , XIONG W , et al. An efficient query algorithm for trajectory similarity based on Frechet distance threshold[J]. ISPRS International Journal of Geo-Information, 2017, 6 (11): 326. doi: 10.3390/ijgi6110326
8	魏龙翔, 何小海, 滕奇志, 等. 结合Hausdorff距离和最长公共子序列的轨迹分类[J]. 电子与信息学报, 2013, 35 (4): 784- 790.
	WEI L X , HE X H , TENG Q Z , et al. Trajectory classification based on Hausdorff distance and longest common subsequence[J]. Journal of Electronics & Information Technology, 2013, 35 (4): 784- 790.
9	朱进, 胡斌, 邵华. 基于多重运动特征的轨迹相似性度量模型[J]. 武汉大学学报信息科学版, 2017, 42 (12): 1703- 1710.
	ZHU J , HU B , SHAO H . Trajectory similarity measure based on multiple movement features[J]. Geomatics & Information Science of Wuhan University, 2017, 42 (12): 1703- 1710.
10	王前东. 一种带匹配路径约束的最长公共子序列长度算法[J]. 电子与信息学报, 2017, 39 (11): 2615- 2619.
	WANG Q D . A matching path constrained longest common subsequence length algorithm[J]. Journal of Electronics & Information Technology, 2017, 39 (11): 2615- 2619.
11	VLACHOS M, KOLLIOS G, GUNOPULOS D.Discovering similar multidimensional trajectories[C]//Proc.of the 18th International Conference on Data Engineering, 2002: 673-684.
12	WAGNER R A , FISCHER M J . The string-to-string correction problem[J]. Journal of the Association for Computing Machinery, 1974, 21 (1): 168- 173. doi: 10.1145/321796.321811
13	WANG H X, ZHONG J D, ZHANG D F.A duplicate code checking algorithm for the programming experiment[C]//Proc.of the 2nd International Conference on Mathematics and Computers in Sciences and in Industry, 2015: 39-42.
14	BEAL R, AFRIN T, FARHEEN A, et al.A new algorithm for "the LCS problem" with application in compressing genome resequencing data[C]//Proc.of the IEEE International Confe-rence on Bioinformatics and Biomedicine, 2015: 69-74.
15	LIU R C, GUO H Q, ZHANG J, et al.Comparative visualization of vector field ensembles based on longest common subsequence[C]//Proc.of the IEEE Pacific Visualization Symposium, 2016: 96-103.
16	CHOONG M Y, ANGELINE L, CHIN R K Y, et al.Modeling of vehicle trajectory clustering based on LCSS for traffic pattern extraction[C]//Proc.of the IEEE 2nd International conference on Automatic Control and Intelligent Systems, 2017: 74-79.
17	刘宇, 王前东. 基于最长公共子序列的非同步相似轨迹判断[J]. 电讯技术, 2017, 57 (10): 1165- 1170.
	LIU Y , WANG Q D . Computing similar measure between two asynchronous trajectories based on longest common subsequence method[J]. Telecommunication Engineering, 2017, 57 (10): 1165- 1170.
18	孙璐, 周伟, 姜佰辰, 等. 一种时空联合约束的多源航迹相似性度量模型[J]. 系统工程与电子技术, 2017, 39 (11): 2405- 2413.
	SUN L , ZHOU W , JIANG B C , et al. Multi-source trajectories similarity measure model with spatial and temporal constraints[J]. Systems Engineering and Electronics, 2017, 39 (11): 2405- 2413.
19	DOUGLAS D H , PEUCKER T K . Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica the International Journal for Geographic Information & Geovisualization, 2001, 10 (2): 112- 122.
20	YUAN G , SUN P H , ZHAO J , et al. A review of moving object trajectory clustering algorithms[J]. Artificial Intelligence Review, 2017, 47 (1): 123- 144.

目标	f_{1_ε}/%	f_{2_ε}/%	f_{3_{δ, ε}}/%	t_{1_ε}/ms	t_{2_ε}/ms	t_{3_{δ, ε}}/ms
1	83	97	94	33	89	31
2	75	94	93	57	152	40
3	70	81	80	54	145	35
4	68	83	78	31	82	27
5	69	86	83	42	113	42
6	73	95	95	25	66	23

[1]	Fuyu LU, Ningning TONG, Weike FENG, Pengcheng WAN. Adaptive hybrid annealing particle swarm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(11): 3470-3476.
[2]	Tianye SUN, Wei SUN, Jianjun WU. UAV formation rapid assembly method based on improved Quatre algorithm [J]. Systems Engineering and Electronics, 2022, 44(9): 2840-2848.
[3]	Shiying YAN, Kefei YAN, Wei FANG, Hengyang LU. Large-scale multi-objective algorithm based on neighborhood adaptive of differential evolution [J]. Systems Engineering and Electronics, 2022, 44(7): 2112-2124.
[4]	Andi TANG, Tong HAN, Dengwu XU, Huan ZHOU, lei XIE. An improved salp swarm algorithm using Gaussian distribution estimation strategy [J]. Systems Engineering and Electronics, 2022, 44(7): 2229-2240.
[5]	Weijian PANG, Hui LI, Qian HUANG, Peng LI, Xianming MA. Review on ontology-based task planning for unmanned systems [J]. Systems Engineering and Electronics, 2022, 44(3): 908-920.
[6]	Bin ZENG, Rui WANG, Houpu LI, Xu FAN. Scheduling strategies research based on reinforcement learning for wartime support force [J]. Systems Engineering and Electronics, 2022, 44(1): 199-208.
[7]	Weiqiang MA, Yongqi GAO, Miao ZHAO. Global-best difference-mutation brain storm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(1): 270-278.
[8]	Fengtao WEI, Yangyang ZHANG, Junyu LI, Yunpeng SHI. Improved sine cosine algorithm based on dynamic classification strategy [J]. Systems Engineering and Electronics, 2021, 43(6): 1596-1605.
[9]	Jiahui DING, Jianlong TANG, Zhengyang YU. Design of lightweight incremental ensemble learning algorithm [J]. Systems Engineering and Electronics, 2021, 43(4): 861-867.
[10]	Jiayi LIU, Shaohua YUE, Gang WANG, Xiaoqiang YAO, Jie ZHANG. Cooperative evolution algorithm of multi-agent system under complex tasks [J]. Systems Engineering and Electronics, 2021, 43(4): 991-1002.
[11]	Yue LIU, Xiaoqing ZHONG, Jinyu FU, Xiang LI. Stereo matching algorithm based on hybrid optimization method [J]. Systems Engineering and Electronics, 2020, 42(12): 2692-2699.
[12]	Tao XU, Zhishuai WU, Min LU, Zonglei LYU, Zhonghu LI. Optimization model of hub-and-spoke network for congestion problem [J]. Systems Engineering and Electronics, 2020, 42(11): 2553-2559.
[13]	Zhihai YAO, Jianping LIU, Jianping WANG, Wei LI, Bo REN. Evaluation index system of ground-based TT&C resource scheduling [J]. Systems Engineering and Electronics, 2020, 42(8): 1751-1758.
[14]	Jiayi LIU, Shaohua YUE, Gang WANG, Jie ZHANG, Xiaoqiang YAO. Design of command control model based on MPC-MAS under multi-platform distributed cooperative operation [J]. Systems Engineering and Electronics, 2020, 42(7): 1582-1589.
[15]	Shengxiang SUN, Shuang HAN. Multi-factor incentive pricing model and algorithm for military equipment ordering based on bi-level decision-making [J]. Systems Engineering and Electronics, 2020, 42(6): 1338-1347.

Fast algorithm of similarity measurement for classical trajectory

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 20

Related Articles 15

Recommended Articles

Metrics

Comments