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

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

摘要/Abstract

摘要：

针对经典轨迹相似度量的耗时性,利用轨迹压缩算法,提出一种基于最长公共子序列(longest common subsequence, LCS)的相似度量快速算法。首先，对实时轨迹进行压缩,减少轨迹点数。然后，利用经典轨迹的点与实时轨迹线段之间的距离,根据改进的多对1 LCS长度公式,计算经典轨迹与实时轨迹之间的LCS长度。最后，将LCS长度与经典轨迹的点数的比值作为经典轨迹的相似度。实验说明,通过轨迹压缩能够减少60%以上的计算时间。

关键词: 最长公共子序列, 轨迹相似度量, 轨迹压缩, 快速计算, 经典轨迹

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

中图分类号:

TP301

王前东. 经典轨迹的相似度量快速算法[J]. 系统工程与电子技术, 2020, 42(10): 2189-2196.

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

图/表 7

图1

图2

图3

图4

表1

表2

表3

参考文献 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]	徐秋坪, 赵锴, 屈德涛, 刘钢墩. 基于LCSS的目标航线规律快速匹配方法[J]. 系统工程与电子技术, 2022, 44(4): 1263-1269.
[2]	冯志成, 安建平. 过采样下分数阶傅里叶变换的改进算法[J]. Journal of Systems Engineering and Electronics, 2012, 34(3): 467-471.