Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints

In this paper, we address a similarity search problem for spatial trajectories in road networks. In particular, we focus on the subtrajectory similarity search problem, which involves finding in a database the subtrajectories similar to a query trajectory. A key feature of our approach is that we do not focus on a specific similarity function; instead, we consider weighted edit distance (WED), a class of similarity functions which allows user-defined cost functions and hence includes several important similarity functions such as EDR and ERP. We model trajectories as strings, and propose a generic solution which is able to deal with any similarity function belonging to the class of WED. By employing the filter-and-verify strategy, we introduce subsequence filtering to efficiently prunes trajectories and find candidates. In order to choose a proper subsequence to optimize the candidate number, we model the choice as a discrete optimization problem (NP-hard) and compute it using a 2-approximation algorithm. To verify candidates, we design bidirectional tries, with which the verification starts from promising positions and leverage the shared segments of trajectories and the sparsity of road networks for speed-up. Experiments are conducted on large datasets to demonstrate the effectiveness of WED and the efficiency of our method for various similarity functions under WED.