2015 AcceleratingDynamicTimeWarpingC

• (Begum et al., 2015) ⇒ Nurjahan Begum, Liudmila Ulanova, Jun Wang, and Eamonn Keogh. (2015). “Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783286

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Accelerating+Dynamic+Time+Warping+Clustering+with+a+Novel+Admissible+Pruning+Strategy
• http://dl.acm.org/citation.cfm?id=2783258.2783286&preflayout=flat#citedby

Quotes

Author Keywords

• Anytime algorithms; clustering; data mining; time series

Abstract

Clustering time series is a useful operation in its own right, and an important subroutine in many higher-level data mining analyses, including data editing for classifiers, summarization, and outlier detection. While it has been noted that the general superiority of Dynamic Time Warping (DTW) over Euclidean Distance for similarity search diminishes as we consider ever larger datasets, as we shall show, the same is not true for clustering. Thus, clustering time series under DTW remains a computationally challenging task. In this work, we address this lethargy in two ways. We propose a novel pruning strategy that exploits both upper and lower bounds to prune off a large fraction of the expensive distance calculations. This pruning strategy is admissible; giving us provably identical results to the brute force algorithm, but is at least an order of magnitude faster. For datasets where even this level of speedup is inadequate, we show that we can use a simple heuristic to order the unavoidable calculations in a most-useful-first ordering, thus casting the clustering as an anytime algorithm. We demonstrate the utility of our ideas with both single and multidimensional case studies in the domains of astronomy, speech physiology, medicine and entomology.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 AcceleratingDynamicTimeWarpingC	Eamonn Keogh Jun Wang Nurjahan Begum Liudmila Ulanova			Accelerating Dynamic Time Warping Clustering with a Novel Admissible Pruning Strategy				10.1145/2783258.2783286		2015