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

Fast algorithm of similarity measurement for classical trajectory

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

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.