Effective resolving of false-alarms in subsequence matching of time-series data: a method and its performance results

摘要

Subsequence matching, which consists of index searching and false-alarms steps, is an operation that finds those subsequences whose changing patterns are similar to that of a given query sequence from a time-series database. This paper discusses optimization of resolution for subsequence matching. The common problem occurred in false-alarms of previous methods is to compare the candidate subsequence with the query sequence for discarding false-alarms whenever each candidate subsequence appears during the index searching step. This makes a sequence containing candidate subsequences to be accessed multiple times from disk. This redundancy causes the performance of subsequence matching to degrade seriously. In this paper, we propose a new optimal method for resolving the problem. The proposed method stores all the candidate subsequences returned by the index searching into a binary search tree, and performs false-alarms in a batch fashion after finishing the index searching step. By this method, we are able to completely eliminate the redundancies mentioned above. For verifying the performance improvement effect of the proposed method, we perform extensive experiments using a real-life stock data set. The results reveal that the proposed method achieves 55 times to 156 times speedup over the previous methods.