Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Silva, Diego F. [1, 2] ; Giusti, Rafael [1] ; Keogh, Eamonn [3] ; Batista, Gustavo E. A. P. A. [1]
Número total de Autores: 4
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
Número total de Afiliações: 3
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