ComputingComputer ScienceMeteorologyInformation RetrievalSequence AnalysisTime Series AnalysisComputational Time Series AnalysisDynamic Time WarpingNearest Neighbor SearchSequence Similarity SearchTime Series AnalyticsTime Series ModelingDistance MeasuresFast Dynamic Time WarpingPruned Dynamic Time WarpingSimilarity SearchTime Series Similarity SearchTime Warping
Time-series data naturally arise in countless domains, such as meteorology, astrophysics, geology, multimedia, and economics. Similarity search is very popular, and DTW (Dynamic Time Warping) is one of the two prevailing distance measures. Although DTW incurs a heavy computation cost, it provides scaling along the time axis. In this paper, we propose FTW (Fast search method for dynamic Time Warping), which guarantees no false dismissals in similarity query processing. FTW efficiently prunes a significant number of the search cost. Experiments on real and synthetic sequence data sets reveals that FTW is significantly faster than the best existing method, up to 222 times.
20
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
Fast subsequence matching in time-series databases
Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos · 1994 · 1.7K citations · Full text
Locally adaptive dimensionality reduction for indexing large time series databases
Eamonn Keogh, Kaushik Chakrabarti, Michael J. Pazzani et al. · 2001 · 873 citations