Mining frequent sequential patterns with first-occurrence forests

ABSTRACT

In this paper, a new pattern-growth algorithm is presented to mine frequent sequential patterns using First-Occurrence Forests (FOF). This algorithm uses a simple list of pointers to the first-occurrences of a symbol in the aggregate tree [1], as the basic data structure for database representation, and does not rebuild aggregate trees for projection databases. The experimental evaluation shows that our new FOF mining algorithm outperforms the PLWAP-tree mining algorithm [2] and the FLWAP-tree mining algorithm [3], both in the mining time and the amount of memory used.

REFERENCES

• 1: Myra Spiliopoulou , Lukas Faulstich, WUM - A Tool for WWW Ulitization Analysis, Selected papers from the International Workshop on The World Wide Web and Databases, p.184-103, March 27-28, 1998
• 2: C. I. Ezeife , Yi Lu, Mining Web Log Sequential Patterns with Position Coded Pre-Order Linked WAP-Tree, Data Mining and Knowledge Discovery, v.10 n.1, p.5-38, January 2005 [doi>10.1007/s10618-005-0248-3]
• 3: Peiyi Tang, Markus P. Turkia, and Kyle A. Gallivan. Mining web access patterns with first-occurrence linked WAP-trees. In Proceedings of the 16th International Conference on Software Engineering and Data Engineering (SEDE'07), pages 247--252, Las Vegas, USA, July 2007.
• 4: Ramakrishnan Srikant , Rakesh Agrawal, Mining Sequential Patterns: Generalizations and Performance Improvements, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.3-17, March 25-29, 1996
• 5: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Hua Zhu, Mining Access Patterns Efficiently from Web Logs, Proceedings of the 4th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Current Issues and New Applications, p.396-407, April 18-20, 2000
• 6: 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

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
frequent patterns, projection database