| Full text | |
| Author(s): |
Total Authors: 4
|
| Affiliation: | [1] Univ Sao Paulo, Inst Ciencias Matemat & Comp, Sao Carlos, SP - Brazil
[2] Univ Fed Sao Carlos, Dept Comp, Sao Carlos, SP - Brazil
[3] Univ Calif Riverside, Dept Comp Sci & Engn, Riverside, CA 92521 - USA
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | DATA MINING AND KNOWLEDGE DISCOVERY; v. 32, n. 4, p. 988-1016, JUL 2018. |
| Web of Science Citations: | 9 |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 16/04986-6 - Intelligent traps and sensors: an innovative approach to control insect pests and disease vectors |
| Grantee: | Gustavo Enrique de Almeida Prado Alves Batista |
| Support Opportunities: | Research Grants - eScience and Data Science Program - Regular Program Grants |
| FAPESP's process: | 12/08923-8 - Times Series Classification Using Different Data Representations and Ensembles |
| Grantee: | Rafael Giusti |
| Support Opportunities: | Scholarships in Brazil - Doctorate |
| FAPESP's process: | 13/26151-5 - Time series analysis by similarity in large scale |
| Grantee: | Diego Furtado Silva |
| Support Opportunities: | Scholarships in Brazil - Doctorate |