Fast Subtrajectory Similarity Search In Road Networks Under Weighted Edit Distance Constraints
2020 · Satoshi Koide, Chuan Xiao, Yoshiharu Ishikawa
Abstract
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-appr
Authors
(none)
Tags
Stats
Related papers
- Exact Trajectory Similarity Search With N-tree: An Efficient Metric Index For Knn And Range Queries (2024)0.00
- Geopth: A Lightweight Approach To Category-based Trajectory Retrieval Via Geometric Prototype Trajectory Hashing (2025)0.00
- A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories (2020)6.34
- Towards Robust Trajectory Embedding For Similarity Computation: When Triangle Inequality Violations In Distance Metrics Matter (2025)0.00
- Embassi: Embedding Assignment Costs For Similarity Search In Large Graph Databases (2021)2.26
- Simple Distances For Trajectories Via Landmarks (2018)4.52
- Hetfs: A Method For Fast Similarity Search With Ad-hoc Meta-paths On Heterogeneous Information Networks (2025)4.52
- Sublinear Time Nearest Neighbor Search Over Generalized Weighted Manhattan Distance (2021)0.00