Efficient and Effective Similar Subtrajectory Search with Deep Reinforcement Learning
This addresses a finer-grained trajectory similarity problem for applications analyzing subtrajectories, but it is incremental as it builds on existing trajectory search work.
The paper tackles the similar subtrajectory search (SimSub) problem by developing algorithms, including deep reinforcement learning-based ones, which outperform non-learning methods in effectiveness and efficiency on real-world datasets.
Similar trajectory search is a fundamental problem and has been well studied over the past two decades. However, the similar subtrajectory search (SimSub) problem, aiming to return a portion of a trajectory (i.e., a subtrajectory) which is the most similar to a query trajectory, has been mostly disregarded despite that it could capture trajectory similarity in a finer-grained way and many applications take subtrajectories as basic units for analysis. In this paper, we study the SimSub problem and develop a suite of algorithms including both exact and approximate ones. Among those approximate algorithms, two that are based on deep reinforcement learning stand out and outperform those non-learning based algorithms in terms of effectiveness and efficiency. We conduct experiments on real-world trajectory datasets, which verify the effectiveness and efficiency of the proposed algorithms.