Efficient algorithms for stream mining of constrained frequent patterns in a limited memory environment

ABSTRACT

As technology advances, streams of data can be rapidly generated in many real-life applications. This calls for stream mining, which searches for implicit, previously unknown, and potentially useful information---such as frequent patterns---that might be embedded in continuous data streams. However, most of the existing algorithms do not allow users to express the patterns to be mined according to their intentions, via the use of constraints. As a result, these unconstrained mining algorithms can yield numerous patterns that are not interesting to the users. Moreover, many existing tree-based algorithms assume that all the trees constructed during the mining process can fit into memory. While this assumption holds for many situations, there are many other situations in which it does not hold. Hence, in this paper, we develop efficient algorithms for stream mining of constrained frequent patterns in a limited memory environment. Our algorithms allow users to impose a certain focus on the mining process, discover from data streams all those frequent patterns that satisfy the user constraints, and handle situations where the available memory space is limited.

REFERENCES

• 1: 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
• 2: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 3: James Bailey , Thomas Manoukian , Kotagiri Ramamohanarao, Fast Algorithms for Mining Emerging Patterns, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.39-50, August 19-23, 2002
• 4: Roberto J. Bayardo, Jr. , Rakesh Agrawal , Dimitrios Gunopulos, Constraint-Based Rule Mining in Large, Dense Databases, Data Mining and Knowledge Discovery, v.4 n.2-3, p.217-240, July 2000 [doi>10.1023/A:1009895914772]
• 5: Jean-Francois Boulicaut , Baptiste Jeudy, Mining Free Itemsets under Constraints, Proceedings of the International Database Engineering & Applications Symposium, p.322-329, July 16-18, 2001
• 6: Yun Chi , Haixun Wang , Philip S. Yu , Richard R. Muntz, Moment: Maintaining Closed Frequent Itemsets over a Stream Sliding Window, Proceedings of the Fourth IEEE International Conference on Data Mining, p.59-66, November 01-04, 2004
• 7: M. El-Hajj and O. R. Zaïane. COFI-tree mining: a new approach to pattern growth with reduced candidacy generation. In Proc. FIMI 2003.
• 8: Mohamed Medhat Gaber , Arkady Zaslavsky , Shonali Krishnaswamy, Mining data streams: a review, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083789]
• 9: C. Giannella et al. Mining frequent patterns in data streams at multiple time granularities. In Data Mining: Next Generation Challenges and Future Directions, AAAI/MIT Press, 2004, ch. 6.
• 10: Efficient Mining of Constrained Correlated Sets, Proceedings of the 16th International Conference on Data Engineering, p.512, February 28-March 03, 2000
• 11: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 12: Nan Jiang , Le Gruenwald, Research issues in data stream association rule mining, ACM SIGMOD Record, v.35 n.1, p.14-19, March 2006 [doi>10.1145/1121995.1121998]
• 13: Richard M. Karp , Scott Shenker , Christos H. Papadimitriou, A simple algorithm for finding frequent elements in streams and bags, ACM Transactions on Database Systems (TODS), v.28 n.1, p.51-55, March 2003 [doi>10.1145/762471.762473]
• 14: Maria Kontaki , Apostolos N. Papadopoulos , Yannis Manolopoulos, Efficient Incremental Subspace Clustering in Data Streams, Proceedings of the 10th International Database Engineering and Applications Symposium, p.53-60, December 11-14, 2006 [doi>10.1109/IDEAS.2006.19]
• 15: Laks V. S. Lakshmanan , Carson Kai-Sang Leung , Raymond T. Ng, Efficient dynamic mining of constrained frequent sets, ACM Transactions on Database Systems (TODS), v.28 n.4, p.337-389, December 2003 [doi>10.1145/958942.958944]
• 16: Carson Kai-Sang Leung, Interactive Constrained Frequent-Pattern Mining System, Proceedings of the International Database Engineering and Applications Symposium, p.49-58, July 07-09, 2004 [doi>10.1109/IDEAS.2004.37]
• 17: Carson Kai-Sang Leung , Dale A. Brajczuk, Efficient Mining of Frequent Itemsets from Data Streams, Proceedings of the 25th British national conference on Databases: Sharing Data, Information and Knowledge, July 07-10, 2008, Cardiff, Wales, UK [doi>10.1007/978-3-540-70504-8_2]
• 18: Carson Kai-Sang Leung , Quamrul I. Khan, DSTree: A Tree Structure for the Mining of Frequent Sets from Data Streams, Proceedings of the Sixth International Conference on Data Mining, p.928-932, December 18-22, 2006 [doi>10.1109/ICDM.2006.62]
• 19: Carson Kai-Sang Leung , Quamrul I. Khan, Efficient Mining of Constrained Frequent Patterns from Streams, Proceedings of the 10th International Database Engineering and Applications Symposium, p.61-68, December 11-14, 2006 [doi>10.1109/IDEAS.2006.20]
• 20: C. K.-S. Leung et al. A tree-based approach for frequent pattern mining from uncertain data. In Proc. PAKDD 2008, pp. 653--661.
• 21: Carson Kai-Sang Leung , Mark Anthony F. Mateo , Andrew J. Nadler, An EffectiveMulti-Layer Model for Controlling the Quality of Data, Proceedings of the 11th International Database Engineering and Applications Symposium, p.28-36, September 06-08, 2007 [doi>10.1109/IDEAS.2007.12]
• 22: Carson Kai-Sang Leung , Quamrul I. Khan , Tariqul Hoque, CanTree: A Tree Structure for Efficient Incremental Mining of Frequent Patterns, Proceedings of the Fifth IEEE International Conference on Data Mining, p.274-281, November 27-30, 2005 [doi>10.1109/ICDM.2005.38]
• 23: C. K.-S. Leung et al. FIsViz: a frequent itemset visualizer. In Proc. PAKDD 2008, pp. 644--652.
• 24: Wolfgang Lindner , Jorg Meier, Securing the Borealis Data Stream Engine, Proceedings of the 10th International Database Engineering and Applications Symposium, p.137-147, December 11-14, 2006 [doi>10.1109/IDEAS.2006.40]
• 25: Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.13-24, June 01-04, 1998, Seattle, Washington, United States
• 26: Jeffery Xu Yu , Zhihong Chong , Hongjun Lu , Aoying Zhou, False positive or false negative: mining frequent itemsets from high speed transactional data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.204-215, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Human Factors, Management, Performance, Theory

Keywords:
constraints, data mining, data streams, frequent itemsets, limited memory space