Mining very long sequences in large databases with PLWAPLong

ABSTRACT

Position Coded Pre-order Linked Web Access Pattern (PLWAP) mining algorithm is one of the existing efficient web sequential pattern mining algorithms, which stores the frequent sequences of the entire sequential database in a compressed tree form with position coded nodes. However, for very long sequences exceeding thirty two nodes, the number of bits an integer position code can hold, the PLWAP algorithm's performance begins to degrade because it employs linked lists to store conjunctions of long position codes and the linked list traversals slow down the algorithm both during tree construction and mining. PLWAP algorithm also uses each and every node in the frequent 1-item event queue to test for that event inclusion in the suffix tree root set during mining.

This paper proposes (1) using a different position code numbering scheme where each node is assigned two numeric codes (startPosition, endPosition) instead of one, (2) using pre-knowledge of "Last Descendant" of each tree branch to lower the cost of creating the suffix tree root sets during mining. Experiments show that the proposed new scheme, the PLWAPLong outperforms the PLWAP for long sequences and large databases as well as regular databases.

REFERENCES

• 1: R. S. R. Agrawal. Mining sequential patterns: Generalizations and performance improvements. In Proceedings of the Fifth International Conference On Extending Database Technology (EDBT '96) Avignon France, pages 3--17, 1996.
• 2: C. Ezeife and Y. Lu. Mining web log sequential patterns with position coded pre-order linked wap-tree. International Journal of Data Mining and Knowledge Discovery (DMKD) Kluwer Publishers, 10(1):5--38, 2005.
• 3: C. Ezeife, Y. Lu, and Y. Liu. Plwap sequential mining: Open source code. In Proceedings of the ACM SIGKDD's Open Source Data Mining Workshop on Frequent Pattern Mining Implementations, Chicago, pages 26--29. ACM, August 2005.
• 4: J. Han, J. Pei, Y. Yin, and R. Mao. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. International Journal of Data Mining and Knowledge Discovery, 8(1):53--87, Jan 2004.
• 5: T. Imielinski, A. Swami, and R. Agarwal. Mining association rules between sets of items in large databases. In Proceedings of the ACM SIGMOD conference on management of data, pages 207--216. ACM, 1993.
• 6: Y. Lu and C. Ezeife. Position coded pre-order linked wap-tree for web log sequential pattern mining. In Proceedings of the 7th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2003), pages 337--349. Springer, May 2003.
• 7: N. Mabroukeh and C. Ezeife. Taxonomy of sequential pattern mining algorithms. ACM Computing Surveys Journal, 2009.
• 8: J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M. Hsu. Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. In 2001 International Conference on Data Engineering (ICDE'01), Heidelberg, Germany, pages 215--224, 2001.
• 9: J. Pei, J. Han, B. Mortazavi-Asl, and H. Zhu. Mining access patterns efficiently from web logs. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'00) Kyoto Japan, 2000.
• 10: M. J. Zaki. Spade: An efficient algorithm for mining frequent sequences. Machine Learning, 42:32--60, 2001.

INDEX TERMS

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

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Design, Performance

Keywords:
PLWAP mining, association rule mining, data mining, long sequences