Exact and Efficient Similar Subtrajectory Search: Integrating Constraints and Simplification

Similar subtrajectory search (SimSub) aims to find a subtrajectory (i.e., a segment) from a data trajectory (the trajectory to be queried) that closely resembles the query trajectory. Compared with similar trajectory search, SimSub can capture finer-grained similarity and is vital for various trajectory analysis tasks, such as trajectory clustering and join. However, SimSub may return a subtrajectory with extremely limited length, e.g., a single point, which may not align with the expectations of real-world applications. To solve this issue, we propose a constrained SimSub (cSimSub) problem, where the length of the returned subtrajectory must be greater than or equal to a user-specified integer$C$. We demonstrate that this problem can be solved exactly with a time complexity equivalent to$C$times the complexity of the trajectory distance measurement, given that the distance function can be computed using dynamic programming (DP). We also observe that when$C=1$, the solution of cSimSub differs from the vanilla trajectory distance computation (e.g., DTW) only in the state initialization of the DP matrix. Moreover, SimSub focuses on finding a subtrajectory with successive point indexes, which limits its applicability in certain scenarios, e.g., trajectory simplification. Thus, we extend it to sSimSub for trajectory simplification, aiming to find the most similar non-continuous subsequence of a trajectory to itself, with a length constraint of$C$. The subsequence, i.e., the simplified subtrajectory, obtained from sSimSub can achieve the best self-similarity. We conduct experiments on three public available datasets to demonstrate the effectiveness of the proposals. The results show that integrating sSimSub into typical query methods, e.g., KNN query, can achieve higher accuracy of these methods in simplified trajectory databases compared with other well-known trajectory simplification algorithms.