Continuous Trajectory Similarity Search for Online Outlier Detection
Dongxiang Zhang, Zhihao Chang, Sai Wu, Ye Yuan, Kian‐Lee Tan, Gang Chen
Abstract
In this paper, we study a new variant of trajectory similarity search from the context of continuous query processing. Given a moving object from <inline-formula><tex-math notation="LaTeX">$s$</tex-math></inline-formula> to <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula> , following a reference route <inline-formula><tex-math notation="LaTeX">$T_r$</tex-math></inline-formula> , we monitor the trajectory similarity between the reference route and the current partial route at each timestamp for online detour detection. Since existing trajectory distance measures fail to adequately capture the deviation between a partial route and a complete route, we propose a partial trajectory similarity measure to bridge the gap. In particular, we enumerate all the possible routes extended from the partial route to reach the destination <inline-formula><tex-math notation="LaTeX">$d$</tex-math></inline-formula> and calculate their minimum distance to <inline-formula><tex-math notation="LaTeX">$T_r$</tex-math></inline-formula> . We consider deviation calculation in both euclidean space and road networks. In euclidean space, we can directly infer the optimal future path with the minimum trajectory distance. In road networks, we propose an efficient expansion algorithm with a suite of pruning rules. Furthermore, we propose efficient incremental processing strategies to facilitate continuous query processing for moving objects. Our experiments are conducted on multiple real datasets and the experimental results verify the efficiency of our query processing algorithms.