Partial Elastic Matching of Time Series

IST Colloquium, Nov 18, 2005, 01:30PM – 03:00PM, Wachman 322

Partial Elastic Matching of Time Series

Qiang Wang, CIS Department, Temple University

We consider a problem of elastic matching of time series.We propose an algorithm that automatically determines a subsequence $b’$ of a target time series $b$ that best matches a query series $a$. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a DAG (directed acyclic graph). The proposed approach allows us to also compute the optimal scale and translation of time series values, which is a nontrivial problem in the case of subsequence matching. Our experimental results demonstrate that the proposed algorithm outperforms the commonly used Dynamic Time Warping and Longest Common Subsequence in retrieval accuracy.