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.2135023e-05
Overall Rank
5,215 | 65.05%
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,756 Trajectory Similarity Measurement: An Efficiency Perspective 2024 VLDB 5.6724628e-05
8,905 The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem 2022 VLDB 5.2379169e-05
8,925 Ghost: A General Framework for High-Performance Online Similarity Queries over Distributed Trajectory Streams 2023 SIGMOD 5.2361195e-05
11,319 SimRN: Trajectory Similarity Learning in Road Networks based on Distributed Deep Reinforcement Learning 2025 VLDB 4.9605343e-05
11,401 SIMformer: Single-Layer Vanilla Transformer Can Learn Free-Space Trajectory Similarity 2025 VLDB 4.9605343e-05
11,818 Efficient Non-Learning Similar Subtrajectory Search 2023 VLDB 4.9605343e-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.00032945275
192 Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling 2013 SIGMOD 0.00025740385
229 Robust and Fast Similarity Search for Moving Object Trajectories 2005 SIGMOD 0.00023850907
307 On The Marriage of Lp-norms and Edit Distance 2004 VLDB 0.00021496009
934 Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints 2008 VLDB 0.00012973416
1,068 VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams 2007 VLDB 0.00012170201
1,395 Finding Time Period-Based Most Frequent Path in Big Trajectory Data 2013 SIGMOD 0.00010777052
2,035 Distributed Trajectory Similarity Search 2017 VLDB 9.1372983e-05
2,158 Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently 2008 SIGMOD 8.9272802e-05
2,210 DITA: Distributed In-Memory Trajectory Analytics 2018 SIGMOD 8.844541e-05
2,502 An Efficient and Accurate Method for Evaluating Time Series Similarity 2007 SIGMOD 8.3580269e-05
3,270 Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme 2011 SIGMOD 7.4613275e-05
3,522 Efficient Approximate Entity Extraction with Edit Distance Constraints 2009 SIGMOD 7.2167201e-05
6,116 Trajectory Similarity Join in Spatial Networks 2017 VLDB 5.8657138e-05
6,617 A Pivotal Prefix Based Filtering Algorithm for String Similarity Search 2014 SIGMOD 5.7150599e-05
8,991 ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases 2012 VLDB 5.2299338e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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