Time Series Join on Subsequence Correlation
Authors:
- Abdullah MueenAMAbdullah Mueen
- Hossein HamooniHHHossein Hamooni
- Trilce EstradaTETrilce Estrada
- 1 December 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15504786,p. 450-459
Abstract
We consider the problem of joining two long time series based on their most correlated segments. Two time series can be joined at any locations and for arbitrary length. Such join locations and length provide useful knowledge about the synchrony of the two time series and have applications in many domains including environmental monitoring, patient monitoring and power monitoring. However, join on correlation is a computationally expensive task, specially when the time series are large. The naive algorithm requires O (n4) computation where n is the length of the time series. We propose an algorithm, named Jocor, that uses two algorithmic techniques to tackle the complexity. First, the algorithm reuses the computation by caching sufficient statistics and second, the algorithm prunes unnecessary correlation computation by admissible heuristics. The algorithm runs orders of magnitude faster than the naive algorithm and enables us to join long time series as well as many small time series. We propose a variant of Jocor for fast approximation and an extension to a GPU-based parallel method to bring down the running-time to interactive level for analytics applications. We show three independent uses of time series join on correlation which are made possible by our algorithm.Keywords
This publication has 19 references indexed in Scilit:
- Discovering longest-lasting correlation in sequence databasesProceedings of the VLDB Endowment, 2013
- A shapelet transform for time series classification2012
- Searching and mining trillions of time series subsequences under dynamic time warping2012
- Logical-shapelets2011
- Identifying physiological origins of baroreflex dysfunction in salt-sensitive hypertension in the Dahl SS ratPhysiological Genomics, 2010
- Subseries Join: A Similarity-Based Time Series Match ApproachLecture Notes in Computer Science, 2010
- Exact Discovery of Time Series Motifs2009
- Finding anomalous periodic time seriesMachine Learning, 2008
- A Survey of Join Processing in Data Streams2007
- Compensation of Horizontal Temperature and Salinity Gradients in the Ocean Mixed LayerScience, 1999