A hybrid approach to mining frequent sequential patterns

ABSTRACT

The mining of frequent sequential patterns has been a hot and well studied area---under the broad umbrella of research known as KDD (Knowledge Discovery and Data Mining)---for well over a decade. Yet researchers are still uncovering interesting problems, new algorithms, and ways to improve upon existing methods. In this paper, we marry state-of-the-art frequent sequential pattern mining algorithms (e.g., SPAM, FOF, PrefixSpan), data structures (e.g., aggregate tree, bitmap), and other tried-and-true methods for candidate generation (e.g., apriori), in an attempt to derive a new algorithm with the best qualities of the aforementioned algorithms. In this paper, we disseminate the new algorithm created, lessons learned, and future work to be done.

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: Jay Ayres , Jason Flannick , Johannes Gehrke , Tomi Yiu, Sequential PAttern mining using a bitmap representation, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775109]
• 3: Jiawei Han , Jian Pei , Behzad Mortazavi-Asl , Qiming Chen , Umeshwar Dayal , Mei-Chun Hsu, FreeSpan: frequent pattern-projected sequential pattern mining, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.355-359, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347167]
• 4: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, ACM SIGMOD Record, v.29 n.2, p.1-12, June 2000
• 5: Jian Pei , Jiawei Han , Behzad Mortazavi-Asl , Helen Pinto , Qiming Chen , Umeshwar Dayal , Meichun Hsu, PrefixSpan: Mining Sequential Patterns by Prefix-Projected Growth, Proceedings of the 17th International Conference on Data Engineering, p.215-224, April 02-06, 2001
• 6: Erich A. Peterson , Peiyi Tang, Mining frequent sequential patterns with first-occurrence forests, Proceedings of the 46th Annual Southeast Regional Conference on XX, March 28-29, 2008, Auburn, Alabama [doi>10.1145/1593105.1593115]
• 7: 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
• 8: P. Tang, M. P. Turkia, and K. 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.
• 9: Mohammed J. Zaki, SPADE: an efficient algorithm for mining frequent sequences, Machine Learning, v.42 n.1/2, p.31-60, Jan. 2001 [doi>10.1023/A:1007652502315]

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
apriori, frequent patterns, pattern growth, projection database