Online Top-k Similar Time-Lagged Pattern Pair Search in Multiple Time Series

We extract the relation among multiple time series in which a characteristic pattern in a time series follows a similar pattern in another time series. We call this a ‘post-hoc-relation’. For extracting many post-hoc-relations from a large number of time series, we investigated the problem of reducing the cost of online searching for the top-k similar time-lagged pattern pairs in multiple time series, where k is the query size. We propose an online top-k similar time-lagged pattern pair search method that manages the candidate cache in preparation for the top-k pair update and defines the upper bound distance for each arrival time of pattern pairs. Our method also prunes dissimilar pattern pairs by using an index and the upper bound distance. Experimental results show that our method successfully reduces the number of distance computations for a top-k similar pattern update.