  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.
