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

Autor(es)

Silva, Diego F. ^{[1, 2]} ; Giusti, Rafael ^[1] ; Keogh, Eamonn ^[3] ; Batista, Gustavo E. A. P. A. ^[1]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: DATA MINING AND KNOWLEDGE DISCOVERY; v. 32, n. 4, p. 988-1016, JUL 2018.
• Citações Web of Science: 9

Resumo

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)

• Processo FAPESP: 16/04986-6 - Armadilhas e sensores inteligentes: uma abordagem inovadora para controle de insetos peste e vetores de doenças
• Beneficiário: Gustavo Enrique de Almeida Prado Alves Batista
• Linha de fomento: Auxílio à Pesquisa - Programa eScience e Data Science - Regular
• Processo FAPESP: 12/08923-8 - Classificação dè séries temporais utilizando diferentes representações dè dados e ensembles
• Beneficiário: Rafael Giusti
• Linha de fomento: Bolsas no Brasil - Doutorado
• Processo FAPESP: 13/26151-5 - Análise de séries temporais por similaridade em larga escala
• Beneficiário: Diego Furtado Silva
• Linha de fomento: Bolsas no Brasil - Doutorado