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

Summary: Subtrajectory similarity search in road networks under WED, a framework for EDR/ERP with user-defined costs. Subsequence filtering with a 2-approx NP-hard subsequence selection and bidirectional tries for verification enable fast pruning for WED-based queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12108
Venue: VLDB
Year: 2020
Pagerank: 5.5826473e-05
Overall Rank: 5,291 | 63.20%
DOI: 10.14778/3407790.3407818

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,512	Trajectory Similarity Measurement: An Efficiency Perspective	2024	VLDB	5.0321577e-05
8,778	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB	4.4543399e-05
10,588	SimRN: Trajectory Similarity Learning in Road Networks based on Distributed Deep Reinforcement Learning	2025	VLDB	4.1945683e-05
10,709	SIMformer: Single-Layer Vanilla Transformer Can Learn Free-Space Trajectory Similarity	2025	VLDB	4.1945683e-05
11,201	Ghost: A General Framework for High-Performance Online Similarity Queries over Distributed Trajectory Streams	2023	SIGMOD	4.1945683e-05
11,257	Efficient Non-Learning Similar Subtrajectory Search	2023	VLDB	4.1945683e-05

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
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044847972
251	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.00030644658
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
358	On The Marriage of Lp-norms and Edit Distance	2004	VLDB	0.0002599481
1,115	Finding Time Period-Based Most Frequent Path in Big Trajectory Data	2013	SIGMOD	0.00013894562
1,202	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00013326298
1,234	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013122499
1,776	Distributed Trajectory Similarity Search	2017	VLDB	0.00010593716
2,192	DITA: Distributed In-Memory Trajectory Analytics	2018	SIGMOD	9.3185895e-05
2,193	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.3178557e-05
2,943	An Efficient and Accurate Method for Evaluating Time Series Similarity	2007	SIGMOD	7.8399495e-05
3,578	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	6.9503858e-05
3,774	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7757301e-05
6,595	Trajectory Similarity Join in Spatial Networks	2017	VLDB	4.9993852e-05
6,726	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9484027e-05
8,706	ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases	2012	VLDB	4.4642586e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,952	Efficient Algorithms for Finding Optimal Meeting Point on Road Networks	2011	VLDB	4.423107e-05
1,170	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013511856
4,112	Searching Trajectories by Locations - An Efficiency Study	2010	SIGMOD	6.4422697e-05
6,004	Compression of Uncertain Trajectories in Road Networks	2020	VLDB	5.2415551e-05
7,151	EDS: A Segment-based Distance Measure for Sub-trajectory Similarity Search	2014	SIGMOD	4.8154472e-05
5,508	Fast Large-Scale Trajectory Clustering	2020	VLDB	5.4713696e-05
6,595	Trajectory Similarity Join in Spatial Networks	2017	VLDB	4.9993852e-05
251	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.00030644658
4,621	Diversified Top-k Route Planning in Road Network	2022	VLDB	6.0426586e-05
11,257	Efficient Non-Learning Similar Subtrajectory Search	2023	VLDB	4.1945683e-05