The Inherent Time Complexity and An Efficient Algorithm for Subsequence Matching Problem

Summary: SETH-based lower bound: subsequence matching requires ω(n^(1−δ)) time; no O(n^(1−δ)) algorithm even with polynomial preprocessing. Proposes a fast algorithm with a new summarization and index for time-series; supports Euclidean and DTW with/without z-normalization; yields up to 3-10x and 7-12x speedups over state of the art. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12653
Venue: VLDB
Year: 2022
Pagerank: 4.4500701e-05
Overall Rank: 8,775 | 39.02%
DOI: 10.14778/3523210.3523222

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,991	TSM-Bench: Benchmarking Time Series Database Systems for Monitoring Applications	2023	VLDB	4.4113784e-05
10,699	FSMDTW: A Fast Index-free Subsequence Matching Algorithm for Dynamic Time Warping	2025	VLDB	4.1905499e-05
11,025	CIVET: Exploring Compact Index for Variable-Length Subsequence Matching on Time Series	2024	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00061977022
251	Robust and Fast Similarity Search for Moving Object Trajectories	2005	SIGMOD	0.00030589775
358	On The Marriage of Lp-norms and Edit Distance	2004	VLDB	0.00026059337
1,060	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00014359912
1,157	A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series	2013	VLDB	0.00013600695
3,418	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.1129681e-05
3,629	The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art	2019	VLDB	6.8997167e-05
5,297	Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints	2020	VLDB	5.5772847e-05
5,883	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	5.2865165e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,300	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD	4.5392079e-05
11,025	CIVET: Exploring Compact Index for Variable-Length Subsequence Matching on Time Series	2024	VLDB	4.1905499e-05
11,259	Efficient Non-Learning Similar Subtrajectory Search	2023	VLDB	4.1905499e-05
5,314	Online Event-driven Subsequence Matching over Financial Data Streams	2004	SIGMOD	5.5702825e-05
8,140	Anticipatory DTW for Efficient Similarity Search in Time Series Databases	2009	VLDB	4.5726407e-05
65	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00061977022
6,982	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	4.8685999e-05
3,297	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.2549403e-05
5,883	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB	5.2865165e-05
10,699	FSMDTW: A Fast Index-free Subsequence Matching Algorithm for Dynamic Time Warping	2025	VLDB	4.1905499e-05