A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases
Ung-Gi No, Sanguk Kim, Gyu-Yeong Hwang, Kyuseok Shim · 2000
In this paper, we propose a subsequence matching algorithm that supports moving average transform of arbitrary order in time-series databases. Moving average transform reduces the effect of noise and has been used in many areas such as econometrics since it is useful in finding the overall trends in the time-series data. The moving average order to be used varies, since the users want to control the degree of noise reduction and the frequency of analysis depending on the applications and the characteristics of data sequences. The proposed matching algorithm supports moving average transform of arbitrary order by extending the existing subsequence matching algorithm. If we applied the existing subsequence matching algorithm without any extension, we would have to generate an index per each moving average order. Thus, supporting an arbitrary moving average order would cause serious overhead on storage space and insertion/deletion of data sequences. The proposed algorithm can use only one index for a preselected moving average order k and performs subsequence matching for an arbitrary order m(k). We prove that the proposed algorithm causes no false dismissal, i.e., it does not miss part of the final search result. The proposed algorithm can also use more than one index for improving search performance. We have evaluated the performance of the proposed algorithm through experiments. The results show that the proposed algorithm improves the performance by up to 2.7 times on the average compared with the sequential scan algorithm. Since the proposed subsequence matching algorithm works better with smaller selectivities, it is suitable for practical applications. The proposed algorithm can be applied in a variety of areas that use the moving average transform. They include finding stock items with similar trends in prices, estimation of sales for a Product, and weather forecast through temperature data analysis.