Toward accurate dynamic time warping in linear time and space

Article type: Research Article

Authors: Salvador, Stan^{a; *} | Chan, Philip^b

Affiliations: [a] General Dynamics, Armament and Technical Products, 4205 Westinghouse Commons Dr., Charlotte, NC 28269, USA | [b] Department of Computer Sciences, Florida Institute of Technology, 150 W University Blvd., Melbourne, FL 32901, USA. E-mail: pkc@cs.fit.edu

Correspondence: [*] Corresponding author. 3639 Robin Ln., Charlotte, NC 28269, USA. Tel.: +1 704 599 2993; Fax: +1 980 235 2396; E-mail: ssalvador@gdatp.com.

Abstract: Dynamic Time Warping (DTW) has a quadratic time and space complexity that limits its use to small time series. In this paper we introduce FastDTW, an approximation of DTW that has a linear time and space complexity. FastDTW uses a multilevel approach that recursively projects a solution from a coarser resolution and refines the projected solution. We prove the linear time and space complexity of FastDTW both theoretically and empirically. We also analyze the accuracy of FastDTW by comparing it to two other types of existing approximate DTW algorithms: constraints (such as Sakoe-Chiba Bands) and abstraction. Our results show a large improvement in accuracy over existing methods.

Keywords: Dynamic time warping, time series, time series alignment, time series similarity

DOI: 10.3233/IDA-2007-11508

Journal: Intelligent Data Analysis, vol. 11, no. 5, pp. 561-580, 2007