Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (2): 578-583.DOI: 10.11772/j.issn.1001-9081.2019071249

• Data science and technology • Previous Articles     Next Articles

Trajectory similarity measurement method based on area division

Yike LYU1, Kai XU2(), Zhenqiang HUANG3   

  1. 1.College of Transport and Communications,Shanghai Maritime University,Shanghai 201306,China
    2.Shanghai International Shipping Institute,Shanghai Maritime University,Shanghai 200082,China
    3.College of Information Engineering,Shanghai Maritime University,Shanghai 201306,China
  • Received:2019-07-18 Revised:2019-09-25 Accepted:2019-09-26 Online:2019-10-25 Published:2020-02-10
  • Contact: Kai XU
  • About author:LYU Yike, born in 1995, M. S. candidate. His research interests include port and harbor big data mining, trajectory analysis application.
    HUANG Zhenqiang, born in 1993, M. S. candidate. His research interests include big data analysis and processing, shipping big data analysis.
  • Supported by:
    the National Social Science Fundation of China(15BJY069);the Youth Program of National Natural Science Foundation of China(41505001)

基于面积划分的轨迹相似性度量方法

吕一可1, 徐凯2(), 黄振强3   

  1. 1.上海海事大学 交通运输学院,上海 201306
    2.上海海事大学 上海国际航运研究中心,上海 200082
    3.上海海事大学 信息工程学院,上海 201306
  • 通讯作者: 徐凯
  • 作者简介:吕一可(1995—),男,浙江缙云人,硕士研究生,主要研究方向:港航大数据挖掘、轨迹分析应用
    黄振强(1993—),男,广东海丰人,硕士研究生,主要研究方向:大数据分析与处理、航运大数据分析。
  • 基金资助:
    国家社会科学基金资助项目(15BJY069);国家自然科学基金青年科学基金资助项目(41505001)

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%,能更好地适应轨迹点分布不均匀的轨迹相似度量工作。

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

CLC Number: