Efficient algorithm for a novel pattern of time series

摘要

In this paper, a novel kind of threshold similarity query is introduced. It reports a threshold if exceeding which the queried time series has the most similar time intervals compared to that of the given query time series above its query threshold, and the extent of the similarity between the two time interval sequences should be within a user-specified range. We present an efficient method composed by two steps to solve the query. The first step is to dramatically narrow the search space into a quite small subspace without false dismissals, and the second to search iteratively in the subspace. In more detail, a lower bounding distance function is described, which guarantees no false dismissals during the first step. Furthermore, we use binary search to quickly locate the solution within the subspace based on the continuity and monotone of the length function of time intervals, which are proved in this paper. We implemented our method on traffic data and discovered some useful knowledge. We also carried out experiments on diverse time series data to compare our method with brute force method. The results were excellent: our method accelerated the search time from 10 times up to 150 times.