SparseDTW: A Novel Approach to Speed up Dynamic Time Warping

Autor:	Al-Naymat, Ghazi, Chawla, Sanjay, Taheri, Javid
Rok vydání:	2012
Předmět:	Computer Science - Databases Computer Science - Data Structures and Algorithms
Zdroj:	Al-Naymat, G., S. Chawla, and J. Taheri, "SparseDTW: A Novel Approach to Speed up Dynamic Time Warping", The 2009 Australasian Data Mining, vol. 101, Melbourne, Australia, ACM Digital Library, pp. 117-127, 12/2009
Druh dokumentu:	Working Paper
Popis:	We present a new space-efficient approach, (SparseDTW), to compute the Dynamic Time Warping (DTW) distance between two time series that always yields the optimal result. This is in contrast to other known approaches which typically sacrifice optimality to attain space efficiency. The main idea behind our approach is to dynamically exploit the existence of similarity and/or correlation between the time series. The more the similarity between the time series the less space required to compute the DTW between them. To the best of our knowledge, all other techniques to speedup DTW, impose apriori constraints and do not exploit similarity characteristics that may be present in the data. We conduct experiments and demonstrate that SparseDTW outperforms previous approaches. Comment: 17 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1201.2969 Zobrazit plný text záznamu View this record from Arxiv