Abstract:

In the era of big data， the application of spatial-temporal trajectory data is increasing and these data contain a large amount of information， and the similarity measurement of the trajectory plays a pivotal role as a key step in the trajectory mining work. However， the traditional trajectory similarity measurement methods have the disadvantages of high time complexity and inaccuracy caused by the determination based on the trajectory points. In order to solve these problems， a Triangle Division （TD） trajectory similarity measurement method with the trajectory area metric as theory was proposed for trajectories without road network structure. By setting up “pointer” to connect the trajectory points between two trajectories to construct the non-overlapping triangle areas， the areas were accumulated and the trajectory similarity was calculated to confirm the similarity between the trajectories based on the thresholds set in different application scenarios. Experimental results show that compared with the traditional trajectory point-based spatial trajectory similarity measurement methods such as Longest Common Subsequence （LCSS） and Fréchet distance metric， the proposed method improves the recognition accuracy， reduces the time complexity by nearly 90%， and can better adapt to the trajectory similarity measurement work with uneven distribution of trajectory points.

Key words: spatio-temporal trajectory, area division, trajectory similarity, similarity measurement

摘要：

大数据时代背景下，时空轨迹数据应用的场景日益增多且这些数据蕴含着大量的信息，而轨迹的相似性度量作为轨迹挖掘工作的关键步骤起着举足轻重的作用。但传统轨迹相似度量方法有着时间复杂度高、基于轨迹点判断而不够精确的问题。为了解决这些问题，提出了适用于无路网结构轨迹的以轨迹间面积度量为原理的三角分割（TD）方法轨迹相似度量方法。通过建立“指针”选择两轨迹间的轨迹点连线以构建互不重叠的三角形，累加三角形面积并计算轨迹相似度，通过在不同应用场景下设置的阈值来确认轨迹的相似情况。实验结果表明，与传统的基于轨迹点的空间轨迹相似度量方法——最长公共子序列（LCSS）方法和弗雷歇距离度量方法相比，所提方法提升了识别的准确度，且时间复杂度降低了接近90%，能更好地适应轨迹点分布不均匀的轨迹相似度量工作。

关键词: 时空轨迹, 面积划分, 轨迹相似性, 相似度量