Open access research
publication repository

Faster retrieval with a two-pass dynamic-time-warping lower bound [r-libre/225]

Lemire, Daniel (2009). Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern Recognition, 42 (9). https://doi.org/10.1016/j.patcog.2008.11.030

File(s) available for this item:
[img]  PDF - 0811.3301v2.pdf  
Item Type: Journal Articles
Refereed: Yes
Status: Published
Abstract: The Dynamic Time Warping (DTW) is a popular similarity measure between time series. The DTW fails to satisfy the triangle inequality and its computation requires quadratic time. Hence, to find closest neighbors quickly, we use bounding techniques. We can avoid most DTW computations with an inexpensive lower bound (LB Keogh). We compare LB Keogh with a tighter lower bound (LB Improved). We find that LB Improved-based search is faster. As an example, our approach is 2-3 times faster over random-walk and shape time series.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Depositor: Lemire, Daniel
Owner / Manager: Daniel Lemire
Deposited: 22 Jul 2014 21:51
Last Modified: 16 Jul 2015 00:47

Actions (login required)