FTW: Fast Similarity Search under the Time Warping Distance

Summary: FTW: an exact DTW similarity-search method that guarantees no false dismissals by introducing a novel, highly effective pruning scheme exploiting time-warp invariance. Empirically prunes many candidates and achieves up to 222× speedup versus prior SOTA. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1365
Venue: PODS
Year: 2005
Pagerank: 7.5816553e-05
Overall Rank: 3,267 | 77.59%
DOI: 10.1145/1065167.1065210

Incoming Non-self Citations Over Time

Authors

1. Yasushi Sakurai (Nippon Telegraph and Telephone Corporation)
2. Masatoshi Yoshikawa (Nagoya University)
3. Christos Faloutsos (Carnegie Mellon University)

BibTeX Citation

@inproceedings{sakurai_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{FTW: Fast Similarity Search under the Time Warping Distance}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065210},
        doi = {10.1145/1065167.1065210},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sakurai, Yasushi and Yoshikawa, Masatoshi and Faloutsos, Christos},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,467	An Efficient and Accurate Method for Evaluating Time Series Similarity	2007	SIGMOD	8.5390765e-05
3,440	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.4142918e-05
4,234	GRAIL: Efficient Time-Series Representation Learning	2019	VLDB	6.8171563e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
7,309	Set-based Similarity Search for Time Series	2016	SIGMOD	5.649535e-05
8,107	Anticipatory DTW for Efficient Similarity Search in Time Series Databases	2009	VLDB	5.4851245e-05
8,229	Mining Approximate Top-K Subspace Anomalies in Multi-Dimensional Time-Series Data	2007	VLDB	5.4620216e-05
10,069	Mining and Forecasting of Big Time-series Data	2015	SIGMOD	5.1643809e-05
10,863	TMLKD: Few-shot Trajectory Metric Learning via Knowledge Distillation	2025	VLDB	5.093636e-05
11,179	High Precision ≠ High Cost: Temporal Data Fusion for Multiple Low-Precision Sensors	2024	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046675394
46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00044853085
190	Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases	2001	SIGMOD	0.00026105472
371	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB	0.00019869565
468	Fast Time Sequence Indexing for Arbitrary Lp Norms	2000	VLDB	0.00017986163
601	Exact Indexing of Dynamic Time Warping	2002	VLDB	0.00015870156
864	The Pyramid-Technique: Towards Breaking the Curse of Dimensionality	1998	SIGMOD	0.00013522522
1,046	Warping Indexes with Envelope Transforms for Query by Humming	2003	SIGMOD	0.00012440091
3,125	General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows	2002	SIGMOD	7.7344198e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,467	An Efficient and Accurate Method for Evaluating Time Series Similarity	2007	SIGMOD
2	6,756	On Efficiently Searching Trajectories and Archival Data for Historical Similarities	2008	VLDB
3	6,517	Interactive Time Series Exploration Powered by the Marriage of Similarity Distances	2017	VLDB
4	601	Exact Indexing of Dynamic Time Warping	2002	VLDB
5	371	Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases	1995	VLDB
6	7,309	Set-based Similarity Search for Time Series	2016	SIGMOD
7	3,440	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD
8	810	Similarity-Based Queries for Time Series Data	1997	SIGMOD
9	10,938	FSMDTW: A Fast Index-free Subsequence Matching Algorithm for Dynamic Time Warping	2025	VLDB
10	8,107	Anticipatory DTW for Efficient Similarity Search in Time Series Databases	2009	VLDB