Scaling up dynamic time warping to massive dataset

摘要

There has been much recent interest in adapting data mining algorithms t time series databases.Many of these algorithms need to compare time series Typically some variation or extension of Euclidean distance is used.However,as w demonstrate in this paper,Euclidean distance can be an extremely brittle distance measure.Dynamic time warping (DTW) has been suggested as a technique to allow more robust distance calculations,however it is computationally expensive.In this paper we introduce a modificatin of DTW which operates on a higher level abstraiction of the data,in particular,a piecewise linear representation.We demonstrate that our approach allows us to outperform DTW by one to three orders o magnitude.We experimentally evaluate our approach on medical,astronomical and sign language data.