Efficient All-Pairwise Dynamic Time Warping Matrix Calculation
Explore a groundbreaking approach to speeding up all-pairwise dynamic time warping matrix calculation, essential for time series analysis. This method reduces runtime by up to 50%, showing significant advancements in handling large time series datasets efficiently. Discover the latest research findings and techniques in this innovative field.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation Diego F. Silva, Gustavo E. A. P. A. Batista Proceedings of the 2016 SIAM International Conference on Data Mining May 5-7, 2016, Miami, Florida, USA Presenter: Shan-Ru Liu Date: 2018/10/30 1
Abstract (1/2) Dynamic Time Warping (DTW) is certainly the most relevant distance for time series analysis. However, its quadratic time complexity may hamper its use, mainly in the analysis of large time series data. All the recent advances in speeding up the exact DTW calculation are confined to similarity search. However, there is a significant number of important algorithms including clustering and classification that require the pairwise distance matrix for all time series objects. The only techniques available to deal with this issue are constraint bands and DTW approximations. 2
Abstract (2/2) In this paper, we propose the first exact approach for speeding up the all-pairwise DTW matrix calculation. Our method is exact and may be applied in conjunction with constraint bands. We demonstrate that our algorithm reduces the runtime in approximately 50% on average and up to one order of magnitude in some datasets. 3
PrunedDTW (DTW with Pruned Warping Paths) 1. Being similar or considerably faster than DTW 2. Always returning the optimal path between two time series 5
Result (2/4) 10
Result (3/4) 11
Result (4/4) 12
