Acelerando o cálculo da matriz de distância Dynamic Time Warping entre todos os pares para mineração de séries temporais

• Processo: 15/07628-0
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Data de Início da vigência: 01 de setembro de 2015
• Data de Término da vigência: 31 de agosto de 2016
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação
• Pesquisador responsável: Gustavo Enrique de Almeida Prado Alves Batista
• Beneficiário: Diego Furtado Silva
• Supervisor: Eamonn John Keogh
• Instituição Sede: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brasil
• Instituição Anfitriã: University of California, Riverside (UCR), Estados Unidos
• Vinculado à bolsa: 13/26151-5 - Análise de séries temporais por similaridade em larga escala, BP.DR
• Assunto(s): Análise de séries temporais Mineração Mineração de dados
• Palavra(s)-Chave do Pesquisador: dynamic time warping | larga escala | mineracao | Séries Temporais | Mineração de Dados

Resumo

Dynamic Time Warping (DTW) é, certamente, a distância mais relevante para a análise de séries temporais. O principal problema com DTW é a sua complexidade de tempo computacional, que é quadrática em relação ao número de observações. Dada a importância da DTW à mineração de séries temporais, uma vasta quantidade de técnicas tem sido proposta para acelerar cálculos DTW. No entanto, todos os recentes avanços na aceleração da DTW estão confinados à busca por similaridade. Entretanto, há um número significativo de algoritmos de mineração de dados que exigem a matriz de distância de todos os pares, incluindo agrupamento, detecção de anomalias e classificação. Para esses algoritmos, nenhum dos métodos de aceleração disponíveis na literatura são aplicáveis. O principal objetivo deste projeto é desenvolver o primeiro método exato para acelerar a matriz de distância de todos os pares DTW. (AU)