estWin: adaptively monitoring the recent change of frequent itemsets over online data streams

ABSTRACT

Knowledge embedded in a data stream is likely to be changed as time goes by. Consequently, identifying the recent change of the knowledge quickly can provide valuable information for the analysis of the data stream. However, most of mining algorithms or frequency approximation algorithms for a data stream do not able to extract the recent change of information in a data stream adaptively. This paper proposes a sliding window-based method that finds recently frequent itemsets over an online data stream adaptively. The size of a window defines a desired life-time of the information in a newly generated transaction. Consequently, only recently generated transactions in the range of the window are considered to find the frequent itemsets of a data stream.

REFERENCES

• 1: G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proc. of the 28th Int'l Conference on Very Large Databases, Hong Kong, China, Aug. 2002.
• 2: Chang-Hung Lee , Cheng-Ru Lin , Ming-Syan Chen, Sliding-window filtering: an efficient algorithm for incremental mining, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502630]
• 3: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 4: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 5: Christian Hidber, Online association rule mining, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.145-156, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
data streams, delayed-insertion, pruning, recent change of frequent itemsets, sliding window