Faster retrieval with a two-pass dynamic-time-warping lower bound |
| |
Authors: | Daniel Lemire [Author Vitae] |
| |
Affiliation: | LICEF, Université du Québec à Montréal (UQAM), 100 Sherbrooke West, Montreal (Quebec), Canada H2X 3P2 |
| |
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. |
| |
Keywords: | Time series Very large databases Indexing Classification |
本文献已被 ScienceDirect 等数据库收录! |