| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Incremental, Online, and Merge Mining of Partial Periodic Patterns in Time-Series Databases
March 2004 (vol. 16 no. 3)
pp. 332-342
Abstract—Mining of periodic patterns in time-series databases is an interesting data mining problem. It can be envisioned as a tool for forecasting and prediction of the future behavior of time-series data. Incremental mining refers to the issue of maintaining the discovered patterns over time in the presence of more items being added into the database. Because of the mostly append only nature of updating time-series data, incremental mining would be very effective and efficient. Several algorithms for incremental mining of partial periodic patterns in time-series databases are proposed and are analyzed empirically. The new algorithms allow for online adaptation of the thresholds in order to produce interactive mining of partial periodic patterns. The storage overhead of the incremental online mining algorithms is analyzed. Results show that the storage overhead for storing the intermediate data structures pays off as the incremental online mining of partial periodic patterns proves to be significantly more efficient than the nonincremental nononline versions. Moreover, a new problem, termed merge mining, is introduced as a generalization of incremental mining. Merge mining can be defined as merging the discovered patterns of two or more databases that are mined independently of each other. An algorithm for merge mining of partial periodic patterns in time-series databases is proposed and analyzed.
[1] 332 R. Agrawal, C. Faloutsos, and A. Swami, Efficient Similarity Search in Sequence Databases Proc. Fourth Int'l Conf. Foundations of Data Organization and Algorithms, 1993.[2] R. Agrawal, K. Lin, H. Sawhney, and K. Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases Proc. 21st Int'l Conf. Very Large Databases, 1995.[3] R. Agrawal and G. Psaila, Active Data Mining Proc. First Int'l Conf. Knowledge Discovery and Data Mining, 1995.[4] R. Agrawal, G. Psaila, E. Wimmers, and M. Zait, Querying Shapes of Histories Proc. 21st Int'l Conf. Very Large Databases, 1995.[5] R. Agrawal and R. Srikant, Fast Algorithms for Mining Association Rules Proc. 20th Int'l Conf. Very Large Databases, 1994.[6] R. Agrawal and R. Srikant, “Mining Sequential Patterns,” Proc. 1995 Int'l Conf. Data Eng., pp. 3-14, Mar. 1995.[7] C. Bettini, X.S. Wang, S. Jajodia, and J.-L. Lin, “Discovering Frequent Event Patterns with Multiple Granularities in Time Sequences,” IEEE Trans. Knowledge and Data Eng., vol. 10, no. 2, 1998.[8] K.P. Chan and A. Fu, “Efficient Time Series Matching by Wavelets,” Proc. Int'l Conf. Data Eng., 1999.[9] D. Cheung, J. Han, V. Ng, and C.Y. Wong, Maintenance of Discovered Association Rules in Large Databases: An Incremental Updating Technique Proc. 1996 Int'l Conf. Data Eng., pp. 106-114, Feb. 1996.[10] M. Ester, H. Kriegel, J. Sander, M. Wimmer, and X. Xu, Incremental Clustering for Mining in a Data Warehousing Environment Proc. 24th Int'l Conf. Very Large Databases, 1998.[11] C. Faloutsos, M. Ranganathan, and Y. Manolopoulos, Fast Subsequence Matching in Time-Series Databases Proc. ACM SIGMOD Int'l Conf. Management of Data, 1994.[12] Advances in Knowledge Discovery and Data Mining, U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, eds. AAAI/MIT Press, 1996.[13] R. Feldman, Y. Aumann, A. Amir, and H. Mannila, Efficient Algorithms for Discovering Frequent Sets in Incremental Databases Proc. SIGMOD Workshop Data Mining and Knowledge Discovery, 1997.[14] V. Ganti, J. Gehrke, and R. Ramakrishnan, DEMON: Mining and Monitoring Evolving Data Proc. 16th Int'l Conf. Data Eng., 2000.[15] M. Garofalakis, R. Rastogi, and K. Shim, SPIRIT: Sequential Pattern Mining with Regular Expression Constraints Proc. 25th Int'l Conf. Very Large Databases, 1999.[16] J. Gehrke, V. Ganti, R. Ramakrishnan, and W.-Y. Loh, BOAT: Optimistic Decision Tree Construction Proc. ACM SIGMOD Int'l Conf. Management of Data, 1999.[17] J. Han, G. Dong, and Y. Yin, Efficient Mining of Partial Periodic Patterns in Time Series Database Proc. 15th Int'l Conf. Data Eng., pp. 106-115, Mar. 1999.[18] J. Han, W. Gong, and Y. Yin, Mining Segment-Wise Periodic Patterns in Time-Related Databases Proc. Fourth Int'l Conf. Knowledge Discovery and Data Mining, 1998.[19] C. Hidber, Online Association Rule Mining Proc. ACM SIGMOD Int'l Conf. Management of Data, 1999.[20] H. Mannila, H. Toivonen, and A. Verkamo, Discovering Frequent Episodes in Sequences Proc. First Int'l Conf. Knowledge Discovery and Data Mining, 1995.[21] J. Quinlan, Induction of Decision Trees Machine Learning, vol. 1, pp. 81-106, 1986.[22] D. Rafiei, “On Similarity-Based Queries for Time Series Data,” Proc. 15th Int'l Conf. Data Eng., pp. 410-417, 1999.[23] R. Srikant and R. Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements Proc. Fifth Int'l Conf. Extending Database Technology, 1996.[24] S. Thomas, S. Bodagala, K. Alsabti, and S. Ranka, An Efficient Algorithm for the Incremental Updation of Association Rules in Large Databases Proc.Third Int'l Conf. Knowledge Discovery and Data Mining, 1997.[25] P. Utgoff, ID5: An Incremental ID3 Proc. Fifth Int'l Conf. Machine Learning, pp. 107-120, 1988.[26] K. Wang and J. Tan, Incremental Discovery of Sequential Patterns Proc. SIGMOD Data Mining Workshop Research Issues on Data Mining and Knowledge Discovery, 1996.
Index Terms:
Data mining, time-series databases, incremental mining, online mining.
Citation:
Walid G. Aref, Mohamed G. Elfeky, Ahmed K. Elmagarmid, "Incremental, Online, and Merge Mining of Partial Periodic Patterns in Time-Series Databases," IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 3, pp. 332-342, Mar. 2004, doi:10.1109/TKDE.2003.1262186
