Exact indexing of dynamic time warping
Exact indexing of dynamic time warping
复制标题
DOI：
10.1007/s10115-004-0154-9
复制
发表时间：
2005-03-01
影响因子：
2.7
通讯作者：
Ratanamahatana, CA
中科院分区：
文献类型：
--
作者：
Keogh, E;Ratanamahatana, CA
索引时间序列的问题引起了极大的兴趣。用于索引时间序列的大多数算法都利用欧几里得距离或某些变化。但是，已经有力地表明欧几里得距离是非常脆弱的距离。动态时间翘曲（DTW）是时间序列的更强大的距离度量，即使在时间轴中不相相，相似的形状也可以匹配。由于这种灵活性，DTW广泛用于科学，医学，工业和金融。但是，不幸的是，DTW并未遵守三角形不平等，因此拒绝了精确索引的尝试。取而代之的是，许多研究人员已经引入了近似索引技术，或者放弃了索引的想法，并集中于加速顺序搜索。在这项工作中，我们介绍了一种新颖的技术，以确切的DTW索引。我们证明，我们的方法不能保证错误的解雇，并且在有史以来最大，最全面的时间序列索引实验中，我们证明了其与所有竞争方法相比。
The problem of indexing time series has attracted much interest. Most algorithms used to index time series utilize the Euclidean distance or some variation thereof. However, it has been forcefully shown that the Euclidean distance is a very brittle distance measure. Dynamic time warping (DTW) is a much more robust distance measure for time series, allowing similar shapes to match even if they are out of phase in the time axis. Because of this flexibility, DTW is widely used in science, medicine, industry and finance. Unfortunately, however, DTW does not obey the triangular inequality and thus has resisted attempts at exact indexing. Instead, many researchers have introduced approximate indexing techniques or abandoned the idea of indexing and concentrated on speeding up sequential searches. In this work, we introduce a novel technique for the exact indexing of DTW. We prove that our method guarantees no false dismissals and we demonstrate its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken.