Online Exploration of Time Series
Introduction
The ability to find similar trends among time series data is crucial in various disciplines ranging from financial analytics to medical diagnosis. Evaluation of similarity between time series with different lengths and those with temporal misalignment using robust measurement such as dynamic time warping (DTW) is computationally expensive. To overcome this challenge, we propose a paradigm which utilizes a one-time preprocessing step to supports rapid subsequent data exploration. Our work rests on the novel idea that we can encode the similarity relationships in the preprocessing step using the inexpensive Euclidean Distance into compact clusters, on which we can perform very fast online time warped matching using the more expensive DTW.
Based upon this idea, we implement an Online Time Series Exploration system (ONEX) that helps analysts perform similar search at any length on time series datasets. The system also comes with an interactive interface for better visualization of the results. Additionally, the successor of ONEX, called K-ONEX, can perform fast ranked search, returning the top k most similar time series.
Publications
- Neamtu, R., Ahsan, R., Rundensteiner, E., & Sarkozy, G. (2016). Interactive time series exploration powered by the marriage of similarity distances. Proceedings of the VLDB Endowment, 10(3), 169-180. (pdf)
- Neamtu, R., Ahsan, R., Lovering, C., Nguyen, C., Rundensteiner, E., & Sarkozy, G. (2017, May). Interactive Time Series Analytics Powered by ONEX. In Proceedings of the 2017 ACM International Conference on Management of Data (pp. 1595-1598). ACM. (pdf)
- Nguyen, C., Lovering, C., & Neamtu, R. Ranked Time Series Matching by Interleaving Similarity Distances. 4th Workshop on Advances in Software and Hardware for Big Data to Knowledge Discovery 2017. IEEE Big Data 2017. (pdf)
Datasets
Our systems are evaluated on datasets from the UCR Time Series Classification Archive.Projects
ONEX
Backend system: sourceK-ONEX
Our proposed method K-ONEX, uses a preprocess-once and query-many-times paradigm that interleaves the inexpensive Euclidean distance with the robust Dynamic Time Warping (DTW), to retrieve the k most similar matches to a given sample sequence. We first reduce the data cardinality by generating Euclidean-based groups of similar time series. Then these groups are further explored using the elastic DTW to find similar sequences of any length and temporal alignment. Our evaluation shows that our framework is 2-3 orders of magnitude faster than benchmark methods while achieving 100% accuracy by exploring on average less than 0.5% of the sequences in each dataset.
