Abstract
Moving average transform is known to reduce the effect of noise and has been used in many areas such as econometrics. Previous subsequence matching methods with moving average transform, however, would incur index overhead both in storage space and in update maintenance since the methods should build multiple indexes for supporting arbitrary orders. To solve this problem, we propose a single index approach for subsequence matching that supports moving average transform of arbitrary order. For a single index approach, we first provide the notion of poly-order moving average transform by generalizing the original definition of moving average transform. We then formally prove correctness of the poly-order transform-based subsequence matching. By using the poly-order transform, we also propose two different subsequence matching methods that support moving average transform of arbitrary order. Experimental results for real stock data show that our methods improve average performance significantly, by 22.4 ~ 33.8 times, over the sequential scan.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Faloutsos, C., Swami, A.: Efficient Similarity Search in Sequence Databases. In: Proc. the 4th Int’l Conf. on Foundations of Data Organization and Algorithms, Chicago, Illinois, October 1993, pp. 69–84 (1993)
Beckmann, N., Kriegel, H.-P., Schneider, R., Seeger, B.: The R∗-tree: An Efficient and Robust Access Method for Points and Rectangles. In: Proc. Int’l Conf. on Management of Data, ACM SIGMOD, Atlantic City, NJ, May 1990, pp. 322–331 (1990)
Chatfield, C.: The Analysis of Time Series: An Introduction, 3rd edn. Chapman and Hall, Boca Raton (1984)
Faloutsos, C., Ranganathan, M., Manolopoulos, Y.: Fast Subsequence Matching in Time-Series Databases. In: Proc. Int’l Conf. on Management of Data, ACM SIGMOD, Minneapolis, MN, May 1994, pp. 419–429 (1994)
Kendall, M.: Time-Series, 2nd edn. Charles Griffin and Company, London (1976)
Loh, W.-K., Kim, S.-W.: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases Using Index Interpolation. In: Proc. of the 12th Australasian Database Conference (ADC 2001), Queensland, Australia, January 2001, pp. 37–44 (2001)
Loh, W.-K., Kim, S.-W., Whang, K.-Y.: A Subsequence Matching Algorithm that Supports Normalization Transform in Time-Series Databases. Data Mining and Knowledge Discovery 9(1), 5–28 (2004)
Moon, Y.-S., Whang, K.-Y., Loh, W.-K.: Duality-Based Subsequence Matching in Time-Series Databases. In: Proc. the 17th Int’l Conf. on Data Engineering (ICDE), April 2001, pp. 263–272. IEEE, Heidelberg (2001)
Moon, Y.-S., Whang, K.-Y., Han, W.-S.: General Match: A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows. In: Proc. Int’l Conf. on Management of Data, ACM SIGMOD, Madison, WI, June 2002, pp. 382–393 (2002)
Rafiei, D., Mendelzon, A.O.: Querying Time Series Data Based on Similarity. IEEE Trans. on Knowledge and Data Engineering 12(5), 675–693 (2000)
Wu, H., Salzberg, B., Zhang, D.: Online Event-driven Subsequence Matching Over Financial Data Streams. In: Proc. of Int’lConf. on Management of Data, ACM SIGMOD, Paris, France, June 2004, pp. 23–34 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Moon, YS., Kim, J. (2006). A Single Index Approach for Time-Series Subsequence Matching That Supports Moving Average Transform of Arbitrary Order. In: Ng, WK., Kitsuregawa, M., Li, J., Chang, K. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2006. Lecture Notes in Computer Science(), vol 3918. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11731139_86
Download citation
DOI: https://doi.org/10.1007/11731139_86
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33206-0
Online ISBN: 978-3-540-33207-7
eBook Packages: Computer ScienceComputer Science (R0)