期刊
DATA MINING AND KNOWLEDGE DISCOVERY
卷 32, 期 4, 页码 988-1016出版社
SPRINGER
DOI: 10.1007/s10618-018-0557-y
关键词
Time series; Similarity search; Dynamic time warping
资金
- Sao Paulo Research Foundation (FAPESP) [2012/08923-8, 2013/26151-5, 2016/04986-6]
- National Council for Scientific and Technological Development (CNPq) [306631/2016-4]
- Fundacao de Amparo a Pesquisa do Estado de Sao Paulo (FAPESP) [12/08923-8] Funding Source: FAPESP
Similarity search is the core procedure for several time series mining tasks. While different distance measures can be used for this purpose, there is clear evidence that the Dynamic Time Warping (DTW) is the most suitable distance function for a wide range of application domains. Despite its quadratic complexity, research efforts have proposed a significant number of pruning methods to speed up the similarity search under DTW. However, the search may still take a considerable amount of time depending on the parameters of the search, such as the length of the query and the warping window width. The main reason is that the current techniques for speeding up the similarity search focus on avoiding the costly distance calculation between as many pairs of time series as possible. Nevertheless, the few pairs of subsequences that were not discarded by the pruning techniques can represent a significant part of the entire search time. In this work, we adapt a recently proposed algorithm to improve the internal efficiency of the DTW calculation. Our method can speed up the UCR suite, considered the current fastest tool for similarity search under DTW. More important, the longer the time needed for the search, the higher the speedup ratio achieved by our method. We demonstrate that our method performs similarly to UCR suite for small queries and narrow warping constraints. However, it performs up to five times faster for long queries and large warping windows.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据