DBScholar

Back to papers

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

Summary: Generic subtrajectory search over road-network trajectories for any weighted edit distance, subsuming EDR/ERP via user-defined costs. Subsequence filtering with a 2-approximate selection algorithm and bidirectional-trie verification exploits shared paths and network sparsity. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
ha689d1a5566e5edf
Venue
VLDB
Year
2020
Pagerank
6.2341162e-05
Overall Rank
5,190 | 65.12%
DOI
10.14778/3407790.3407818
PDF
Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{koide_vldb20,
        title = {{Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints}},
        author = {Koide, Satoshi and Xiao, Chuan and Ishikawa, Yoshiharu},
        journal = {PVLDB},
        series = {{VLDB} '20},
        volume = {13},
        number = {11},
        pages = {2188--2201},
        doi = {10.14778/3407790.3407818},
        url = {https://doi.org/10.14778/3407790.3407818},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank Citing Paper Year Venue Pagerank
6,737 Trajectory Similarity Measurement: An Efficiency Perspective 2024 VLDB 5.6912817e-05
8,884 The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem 2022 VLDB 5.2552942e-05
8,905 Ghost: A General Framework for High-Performance Online Similarity Queries over Distributed Trajectory Streams 2023 SIGMOD 5.2534908e-05
11,263 SimRN: Trajectory Similarity Learning in Road Networks based on Distributed Deep Reinforcement Learning 2025 VLDB 4.9769913e-05
11,348 SIMformer: Single-Layer Vanilla Transformer Can Learn Free-Space Trajectory Similarity 2025 VLDB 4.9769913e-05
11,774 Efficient Non-Learning Similar Subtrajectory Search 2023 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
108 Approximate String Joins in a Database (Almost) for Free 2001 VLDB 0.00033040246
197 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025572265
227 Robust and Fast Similarity Search for Moving Object Trajectories 2005 SIGMOD 0.00023924262
306 On The Marriage of Lp-norms and Edit Distance 2004 VLDB 0.00021565993
929 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00013014029
1,062 VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams 2007 VLDB 0.00012208031
1,390 Finding Time Period-Based Most Frequent Path in Big Trajectory Data 2013 SIGMOD 0.00010812806
2,023 Distributed Trajectory Similarity Search 2017 VLDB 9.167612e-05
2,147 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 8.9566452e-05
2,198 DITA: Distributed In-Memory Trajectory Analytics 2018 SIGMOD 8.8738834e-05
2,494 An Efficient and Accurate Method for Evaluating Time Series Similarity 2007 SIGMOD 8.385219e-05
3,256 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4855571e-05
3,512 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 7.2405277e-05
6,099 Trajectory Similarity Join in Spatial Networks 2017 VLDB 5.8851737e-05
6,608 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.73402e-05
8,971 ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases 2012 VLDB 5.2472845e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 9,289 Efficient Algorithms for Finding Optimal Meeting Point on Road Networks 2011 VLDB
2 953 Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation 2012 VLDB
3 4,353 Searching Trajectories by Locations - An Efficiency Study 2010 SIGMOD
4 6,131 Compression of Uncertain Trajectories in Road Networks 2020 VLDB
5 7,704 EDS: A Segment-based Distance Measure for Sub-trajectory Similarity Search 2014 SIGMOD
6 5,014 Fast Large-Scale Trajectory Clustering 2020 VLDB
7 6,099 Trajectory Similarity Join in Spatial Networks 2017 VLDB
8 227 Robust and Fast Similarity Search for Moving Object Trajectories 2005 SIGMOD
9 4,907 Diversified Top-k Route Planning in Road Network 2022 VLDB
10 11,774 Efficient Non-Learning Similar Subtrajectory Search 2023 VLDB