If I have a time series set such as x=[0,2,5,2,3,1,0] that represents an artifact.

What is the best way to match a similar set as x in a larger data set y?


A few approaches come to mind but this list is far from exhaustive:

  • Andreas Brandmaier's permutation distribution clustering is a method rooted in the dissimilarities between time series, formalized as the divergence between their permutation distributions. Personally, I think this is your "best" option


  • Eamonn Keogh's SAX (Symbolic Aggregate Approximation) and iSAX routines develop "shape clustering" for time series


  • There are approaches based on text compression algorithms that remove the redundancy in a sequence of characters (or numbers), creating a kind of distance or density metric that can be used as inputs to clustering

see, e.g., http://link.springer.com/chapter/10.1007/978-0-387-84816-7_4

  • This paper by Rob Hyndman Dimension Reduction for Clustering Time Series Using Global Characteristics, discusses compressing a time series down to a small set of global moments or metrics and clustering on those:


  • Chapter 15 in Aggarwal and Reddy's excellent book, Data Clustering, is devoted to a wide range (a laundry list, really) of time-series clustering methods (pps 357-380). The discussion provides excellent background to many of the issues specific to clustering a time series"



You can do this in R. Your time series data is represented by v and the pattern you wish to match by p. Returns match indices.

> v<-c(1,2,3,4,5,6,7,8,9,1,2,3,4,6,7,5,8,1,2,3,4,5)
> p<-"123"
> gregexpr(p,paste(v,collapse = ""))

[1]  1 10 18
[1] 3 3 3
[1] TRUE
  • $\begingroup$ I am not looking for a complete match. I am looking for a similar match (like a fussy match), complete match is easy it is just a easy for loop. $\endgroup$ – ccsv Feb 3 '15 at 22:18
  • $\begingroup$ This wasn't explained very clearly in the question. I think you also mean fuzzy matching, not fussy. You need to clarify the degree of 'fuzzyness', i.e. how many insertions, deletions or substitutions you are willing to accept and still call a match. see here $\endgroup$ – christopherlovell Feb 4 '15 at 10:26
  • $\begingroup$ If you meant fuzzy, update your question. Otherwise I've answered it in its present form $\endgroup$ – christopherlovell Apr 13 '15 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.