Iterative Deepening Dynamic Time Warping for Time Series

           by Selina Chu, Eamonn Keogh, David Hart, and Michael Pazzani

ABSTRACT: Similarity search in time series databases has attracted much research interest in the data mining community. Most algorithms used to compare time series utilize the Euclidean distance or some variation thereof. However, as we will demonstrate in our paper, Euclidean distance can be an extremely brittle distance measurement. A more robust form of similarity measure is Dynamic Time Warping (DTW). Although it has well documented advantages as a distance measure, it is computationally very expensive. Previous work has shown that approximations to the true DTW distance can be efficiently calculated, however the technique requires the careful choice of a critical parameter. It is unrealistic to expect an end user to be able to set this parameter correctly for the particular domain/dataset/query/task in question. In this paper, we introduce a framework that gives the user explicit control over the time/quality tradeoff. The user simply states their tolerance for the probability of false dismissal. The speedup over the classic algorithm depends on this tolerance. The surprising result is that even a small tolerance for false dismissal will result in very large gains in speedup. The underlying algorithm works by examining the data at increasingly finer levels of approximation until it determines that the probability of a false dismissal is acceptable. The algorithm may have to examine the same data several times, at different levels of abstraction. Because the time for the last iteration dwarfs all others, this apparent redundancy is inconsequential. Because this is the same argument for the classic AI algorithm, we call our approach Iterative Deepening Dynamic Time Warping (IDDTW).

Keywords: Data mining, time series, similarity measures, dimensionality reduction.

(available in ps and pdf formats)

Back
The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees