Towards effective trajectory similarity measure in linear time

With the utilization of GPS devices and the development of location-based services, a massive amount of trajectory data has been collected and mined for many applications. Trajectory similarity computing, which identifies the similarity of given trajectories, is the fundamental functionality of trajectory data mining. The challenge in trajectory similarity computing comes from the noise in trajectories. Moreover, processing such a myriad of data also demands efficiency. However, existing trajectory similarity measures can hardly keep both accuracy and efficiency. In this paper, we propose a novel trajectory similarity measure termed ITS, which is robust to noise and can be evaluated in linear time. ITS converts trajectories into fixed-length vectors and compares them based on their respective vectors’ distance. Furthermore, ITS utilizes interpolation to get fixed-length vectors in linear time. The robustness of ITS owes to the interpolation, which makes trajectories aligned and points in trajectories evenly distributed. Experiments with 12 baselines on four real-world datasets show that ITS has the best overall performance on five representative downstream tasks in trajectory computing.