%0 Journal Article %1 Keogh2002 %A Keogh, Eamonn %D 2002 %K B_scanpathsimilarity distancemeasure dynamictimewarping editdistance timeseries %T Exact indexing of dynamic time warping %U citeseer.ist.psu.edu/article/keogh02exact.html %X The problem of indexing time series has attracted much research interest in the database community. Most algorithms used to index time series utilize the Euclidean distance or some variation thereof. However is has been forcefully shown that the Euclidean distance is a very brittle distance measure. Dynamic Time Warping (DTW) is a much more robust distance measure for time series, allowing similar shapes to match even if they are out of phase in the time axis. Because of this flexibility, DTW is widely used in science, medicine, industry and finance. Unfortunately however, DTW does not obey the triangular inequality, and thus has resisted attempts at exact indexing. Instead, many researchers have introduced approximate indexing techniques, or abandoned the idea of indexing and concentrated on speeding up sequential search. In this work we introduce a novel technique for the exact indexing of DTW. We prove that our method guarantees no false dismissals and we demonstrate its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken.

@article{Keogh2002, abstract = {The problem of indexing time series has attracted much research interest in the database community. Most algorithms used to index time series utilize the Euclidean distance or some variation thereof. However is has been forcefully shown that the Euclidean distance is a very brittle distance measure. Dynamic Time Warping (DTW) is a much more robust distance measure for time series, allowing similar shapes to match even if they are out of phase in the time axis. Because of this flexibility, DTW is widely used in science, medicine, industry and finance. Unfortunately however, DTW does not obey the triangular inequality, and thus has resisted attempts at exact indexing. Instead, many researchers have introduced approximate indexing techniques, or abandoned the idea of indexing and concentrated on speeding up sequential search. In this work we introduce a novel technique for the exact indexing of DTW. We prove that our method guarantees no false dismissals and we demonstrate its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken. }, added-at = {2007-02-17T12:59:51.000+0100}, author = {Keogh, Eamonn}, biburl = {https://www.bibsonomy.org/bibtex/2f20e09e3ada7200aed0d7cfb87096940/tmalsburg}, description = {Exact Indexing of Dynamic Time Warping - Keogh (ResearchIndex)}, interhash = {e301ab7813e30066d7199f8eb89cbc66}, intrahash = {f20e09e3ada7200aed0d7cfb87096940}, keywords = {B_scanpathsimilarity distancemeasure dynamictimewarping editdistance timeseries}, text = {E. J. Keogh. Exact indexing of dynamic time warping. In VLDB 2002.}, timestamp = {2007-10-04T14:22:31.000+0200}, title = {Exact indexing of dynamic time warping}, url = {citeseer.ist.psu.edu/article/keogh02exact.html}, year = 2002 }