Revisiting Techniques for Lowerbounding the Dynamic Time Warping Distance

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10124012" target="_blank" >RIV/00216208:11320/12:10124012 - isvavai.cz</a>
Result on the web
<a href="http://www.springerlink.com/content/r18181338j358n00/" target="_blank" >http://www.springerlink.com/content/r18181338j358n00/</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-32153-5_14" target="_blank" >10.1007/978-3-642-32153-5_14</a>

Result language
angličtina
Original language name
Revisiting Techniques for Lowerbounding the Dynamic Time Warping Distance
Original language description
The dynamic time warping (DTW) distance has been used as a popular measure to compare similarities of numeric time series because it provides robust matching that recognizes warps in time, different sampling rate, etc. Although DTW computation can be optimized by dynamic programming, it is still expensive, so there have been many attempts proposed to speedup DTW-based similarity search by distance lowerbounding. Some approaches assume a constrained variant of DTW (i.e., fixed dimensions, warping windowconstraint, ground distance), while others do not. In this paper, we comprehensively revisit the problem of DTW lowerbounding, define a general form of DTW that fits all the existing variants and goes even beyond. For the constrained variants of generalDTW we propose a lowerbound construction generalizing the LB_Keogh that for particular ground distances offers speedup by up to two orders of magnitude. Furthermore, we apply metric and ptolemaic lowerbounding on unconstrained variants of
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)