Ranked time series matching by interleaving similarity distances
Cuong Nguyen, Charles Lovering, Rodica Neamtu · 2017
Similarity analytics of time series data are critical for a wide range of applications ranging from medical to financial, and from weather forecasting to image processing. Yet these analytics tasks are known to be prohibitively expensive for large data sets, especially when accounting for varying temporal alignments and lengths. Our proposed framework tackles this challenge by adopting a preprocess-once and query-many-times paradigm. We extend a previous formal model interleaving the inexpensive Euclidean distance with the robust Dynamic Time Warping (DTW) to retrieve the k most similar matches to a given sample sequence. Our extended ONline EXploration of top k time series similarity system (K-ONEX) first encodes similarity relationships by compressing the raw time series into Euclidean-based groups; these groups are further explored using the elastic DTW to find similar sequences of any length and temporal alignment with response times that are almost as fast as retrieving only one best match. Our empirical results illustrate that K-ONEX provides response times that are 2-3 orders of magnitude faster than the benchmark and state-of-the-art methods while achieving 100% accuracy by exploring less than 0.5% of the sequences in each dataset.