Optimization of Post - Processing for Subsequence Matching in Time - Series Databases


The KIPS Transactions:PartD, Vol. 9, No. 4, pp. 555-560, Aug. 2002
10.3745/KIPSTD.2002.9.4.555,   PDF Download:

Abstract

Subsequence matching, which consists of index searching and post-processing 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 post- processing for subsequence matching. The common problem occurred in post-processing of previous methods is to compare the candidate subsequence with the query sequence for discarding false alarms whenever each candidate subsequence appears during index searching. This makes a sequence containing candidate subsequences to be accessed multiple times from disk, and also have a candidate subsequence to be compared with the query sequence multiple times. These redundancies cause 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 index searching into a binary search tree, and performs post-processing in a batch fashion after finishing the index searching. 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.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. W. Kim, "Optimization of Post - Processing for Subsequence Matching in Time - Series Databases," The KIPS Transactions:PartD, vol. 9, no. 4, pp. 555-560, 2002. DOI: 10.3745/KIPSTD.2002.9.4.555.

[ACM Style]
Sang Wook Kim. 2002. Optimization of Post - Processing for Subsequence Matching in Time - Series Databases. The KIPS Transactions:PartD, 9, 4, (2002), 555-560. DOI: 10.3745/KIPSTD.2002.9.4.555.