FSMDTW: A Fast Index-free Subsequence Matching Algorithm for Dynamic Time Warping

Summary: Index-free subsequence matching under DTW accelerated by novel lower bounds and data structures that reduce per-candidate lower-bound cost from O(m) to average O(log m). FSMDTW combines these subsequence-aware bounds and pruning to achieve 2.6x–10x speedups on real and synthetic data. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13987
Venue: VLDB
Year: 2025
Pagerank: 4.1945683e-05
Overall Rank: 10,691 | 25.63%
DOI: 10.14778/3748191.3748220

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,061	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00014368716
3,540	Scalable, Variable-Length Similarity Search in Data Series: The ULISSE Approach	2018	VLDB	6.9943185e-05
8,778	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB	4.4543399e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,983	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	4.8732757e-05
699	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00018015254
2,943	An Efficient and Accurate Method for Evaluating Time Series Similarity	2007	SIGMOD	7.8399495e-05
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00062029383
12,133	sDTW: Computing DTW Distances using Locally Relevant Constraints based on Salient Feature Alignments	2012	VLDB	4.1945683e-05
5,878	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	5.2916009e-05
8,139	Anticipatory DTW for Efficient Similarity Search in Time Series Databases	2009	VLDB	4.5770301e-05
3,294	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.2619257e-05
3,518	FTW: Fast Similarity Search under the Time Warping Distance	2005	PODS	7.0153323e-05
8,778	The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem	2022	VLDB	4.4543399e-05