Revisiting Techniques for Lowerbounding the Dynamic Time Warping Distance

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Revisiting Techniques for Lowerbounding the Dynamic Time Warping Distance

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Revisiting Techniques for Lowerbounding the Dynamic Time Warping Distance

Popis výsledku anglicky

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

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2012

Kód důvěrnosti údajů

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

Název periodika

Lecture Notes in Computer Science

ISSN

0302-9743

e-ISSN

—

Svazek periodika

7404

Číslo periodika v rámci svazku

2012

Stát vydavatele periodika

DE - Spolková republika Německo

Počet stran výsledku

17

Strana od-do

192-208

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—