Context-Aware Systems and Applications. 5th International Conference, ICCASA 2016, Thu Dau Mot, Vietnam, November 24-25, 2016, Proceedings

Research Article

An Efficient Method for Time Series Join on Subsequence Correlation Using Longest Common Substring Algorithm

Download
194 downloads
  • @INPROCEEDINGS{10.1007/978-3-319-56357-2_13,
        author={Vo Vinh and Nguyen Chau and Duong Anh},
        title={An Efficient Method for Time Series Join on Subsequence Correlation Using Longest Common Substring Algorithm},
        proceedings={Context-Aware Systems and Applications. 5th International Conference, ICCASA 2016, Thu Dau Mot, Vietnam, November 24-25, 2016, Proceedings},
        proceedings_a={ICCASA},
        year={2017},
        month={6},
        keywords={Time series Subsequence join Longest common substring Correlation coefficient},
        doi={10.1007/978-3-319-56357-2_13}
    }
    
  • Vo Vinh
    Nguyen Chau
    Duong Anh
    Year: 2017
    An Efficient Method for Time Series Join on Subsequence Correlation Using Longest Common Substring Algorithm
    ICCASA
    Springer
    DOI: 10.1007/978-3-319-56357-2_13
Vo Vinh1,*, Nguyen Chau1,*, Duong Anh2,*
  • 1: Ton Duc Thang University
  • 2: Ho Chi Minh City University of Technology
*Contact email: voducvinh@tdt.edu.vn, 51303240@student.tdt.edu.vn, dtanh@cse.hcmut.edu.vn

Abstract

Joining two time series on subsequence correlation provides useful information about the synchronization of the time series. However, finding the exact subsequence which are most correlated is an expensive computational task. Although the current efficient exact method, JOCOR, requires (

    ), where  is the length of the time series, it is still very time-consuming even for time series datasets with medium length. In this paper, we propose an approximate method, LCS-JOCOR, in order to reduce the runtime of JOCOR. Our proposed method consists of three steps. First, two original time series are transformed into two corresponding strings by PAA transformation and SAX discretization. Second, we apply an algorithm to efficiently find the longest common substrings (LCS) of two strings. Finally, the resulting LCSs are mapped back to the original time series to find the most correlated subsequence by JOCOR method. In comparison to JOCOR, our proposed method performs much faster while high accuracy is guaranteed.