FastOPM—A practical method for partial match of time series

摘要

In applications like stock markets, engineering, medicine, etc., a large amount of time series data has been collected. Interrogating the data for patterns is important for analysis like event prediction and event investigation. A fundamental operation to support such analysis is query processing. In this paper, we aim to efficiently find the optimal match of a query in a timeseries when the match is calculated based on the trend and allows points to be skipped from the middle and ends of the sequences. This problem requires global optimization. The solutions in the literature have prohibitively high time complexities and are not practical for long timeseries. Our method consists of three parts. The first part is an efficiency improvement algorithm called FastOPM which applies the Dijkstra algorithm to get the optimal solution in an efficient manner. The second part derives bounds for optimal solutions. The third part is an algorithm for efficiently searching the target timeseries for the best optimal match of a query. Our experiments show that our method is faster than the baseline method, the bounds are effective, and the search algorithm can identify the best optimal match efficiently. Overall, our algorithm effectively outperforms the state-of-the-art algorithms DTW and MASS in retrieving target segments.