Dynamisk Tid Warping (DTW) har en kvadratisk tid och utrymme komplexitet som begränsar dess användning till små tidsserier. I detta dokument introducerar vi FastDTW, en approximation av DTW som har en linjär tid och utrymme komplexitet. FastDTW använder en flernivåstrategi som rekursivt projicerar en lösning från en grövre upplösning och förfinar den projicerade lösningen. Vi bevisar den linjära tids- och rymdkomplexiteten hos FastDTW både teoretiskt och empiriskt. Vi analyserar också noggrannheten hos FastDTW genom att jämföra den med två andra typer av befintliga ungefärliga DTW algoritmer: begränsningar (såsom Sakoe-Chiba Bands) och abstraktion. Våra resultat visar en stor förbättring av noggrannheten jämfört med befintliga metoder.
Märkligt arbete för att förbättra prestanda DTW har också utförts av Salvador och Chan, som föreslog en approximation av DTW med linjär tid och utrymme komplexitet REF.
Toward accurate dynamic time warping in linear time and space
{'venue': 'Intell. Data Anal.', 'journal': 'Intell. Data Anal.', 'mag_field_of_study': ['Computer Science']}