Advanced search
Start date
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Speeding up similarity search under dynamic time warping by pruning unpromising alignments

Full text
Silva, Diego F. [1, 2] ; Giusti, Rafael [1] ; Keogh, Eamonn [3] ; Batista, Gustavo E. A. P. A. [1]
Total Authors: 4
[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

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: 13/26151-5 - Time series analysis by similarity in large scale
Grantee:Diego Furtado Silva
Support type: Scholarships in Brazil - Doctorate
FAPESP's process: 12/08923-8 - Times Series Classification Using Different Data Representations and Ensembles
Grantee:Rafael Giusti
Support type: Scholarships in Brazil - Doctorate
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 type: Research Grants - eScience and Data Science Program - Regular Program Grants