Improved sequential pattern mining using an extended bitmap representation

Chien Liang Wu, Jia Ling Koh, Pao Ying An

Research output: Contribution to journalConference article

5 Citations (Scopus)

Abstract

The main challenge of mining sequential patterns is the high processing cost of support counting for large amount of candidate patterns. For solving this problem, SPAM algorithm was proposed in SIGKDD'2002, which utilized a depth-first traversal on the search space combined with a vertical bitmap representation to provide efficient support counting. According to its experimental results, SPAM outperformed the previous works SPADE and PrefixSpan algorithms on large datasets. However, the SPAM algorithm is efficient under the assumption that a huge amount of main memory is available such that its practicability is in question. In this paper, an Improved-version of SPAM algorithm, called I-SPAM, is proposed. By extending the structures of data representation, several heuristic mechanisms are proposed to speed up the efficiency of support counting further. Moreover, the required memory size for storing temporal data during mining process of our method is less than the one needed by SPAM. The experimental results show that I-SPAM can achieve the same magnitude efficiency and even better than SPAM on execution time under about half the maximum memory requirement of SPAM.

Original languageEnglish
Pages (from-to)776-785
Number of pages10
JournalLecture Notes in Computer Science
Volume3588
DOIs
Publication statusPublished - 2005 Jan 1
Event16th International Conference on Database and Expert Systems Applications, DExa 2005 - Copenhagen, Denmark
Duration: 2005 Aug 222005 Aug 26

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved sequential pattern mining using an extended bitmap representation'. Together they form a unique fingerprint.

  • Cite this