SparseDTW: A novel approach to speed up dynamic time warping

Ghazi Al-Naymat, Sanjay Chawla, Javid Taheri

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

72 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAusDM'09 - Conferences in Research and Practice in Information TechnologyConferences in Research and Practice in Information Technology
Pages117-127
Number of pages11
StatePublished - 2009
Externally publishedYes
Event8th Australasian Data Mining Conference, AusDM 2009 - Melbourne, VIC, Australia
Duration: Dec 1 2009Dec 4 2009

Publication series

NameConferences in Research and Practice in Information Technology Series
Volume101
ISSN (Print)1445-1336

Conference

Conference8th Australasian Data Mining Conference, AusDM 2009
Country/TerritoryAustralia
CityMelbourne, VIC
Period12/1/0912/4/09

Keywords

  • Data mining
  • Dynamic time warping
  • Similarity measures
  • Time series

Fingerprint

Dive into the research topics of 'SparseDTW: A novel approach to speed up dynamic time warping'. Together they form a unique fingerprint.

Cite this