Faster retrieval with a two-pass dynamic-time-warping lower bound
Faster retrieval with a two-pass dynamic-time-warping lower bound
复制标题
DOI：
10.1016/j.patcog.2008.11.030
复制
发表时间：
2009-09-01
影响因子：
8
通讯作者：
Lemire, Daniel
中科院分区：
文献类型：
--
作者：
Lemire, Daniel
动态时间规整（DTW）是一种流行的时间序列相似性度量方法。DTW不满足三角不等式，其计算需要二次时间。因此，为了快速找到最近的邻居，我们使用边界技术。我们可以用一个便宜的下限（LB_Keogh）来避免大多数DTW计算。我们将LB_Keogh与更严格的下限（LB_Improved）进行比较。我们发现基于LB_Improved的搜索速度更快。例如，我们的方法比随机行走和形状时间序列快2-3倍。(C)2008爱思唯尔有限公司版权所有。
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. (C) 2008 Elsevier Ltd. All rights reserved.