Speeding up All-Pairwise Dynamic Time Warping distance matrix for time series mining

• Grant number: 15/07628-0
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• Start date: September 01, 2015
• End date: August 31, 2016
• Field of knowledge: Physical Sciences and Mathematics - Computer Science
• Principal Investigator: Gustavo Enrique de Almeida Prado Alves Batista
• Grantee: Diego Furtado Silva
• Supervisor: Eamonn John Keogh
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Institution abroad: University of California, Riverside (UCR), United States
• Associated to the scholarship: 13/26151-5 - Time series analysis by similarity in large scale, BP.DR

Abstract

Dynamic Time Warping (DTW) is certainly the most relevant distance for time series analysis. The main issue with DTW is its computational time complexity, which is quadratic to the number of observations. Given the importance of DTW to time series mining, a large body of research has been proposed to accelerate DTW calculations. However, all the recent advances in speeding up DTW are confined to similarity search. We note that there are a significant number of data mining algorithms that require the all-pairwise distance matrix, including clustering, anomaly detection and classification. For those algorithms, none of the speed-up methods available in the literature, based on lower bounding, are applicable. The main objective of this project is to develop the first exact method to speed-up the all-pairwise DTW distance matrix. (AU)