Sequential PAttern mining using a bitmap representation
Jay Ayres, Jason A. Flannick, Johannes E. Gehrke et al. · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · 2002
We introduce a new algorithm for mining sequential patterns. Our algorithm is especially efficient when the sequential patterns in the database are very long. We introduce a novel depth-first search strategy that integrates a depth-first traversal of the search space with effective pruning mechanisms.Our implementation of the search strategy combines a vertical bitmap representation of the database with efficient support counting. A salient feature of our algorithm is that it incrementally outputs new frequent itemsets in an online fashion.In a thorough experimental evaluation of our algorithm on standard benchmark data from the literature, our algorithm outperforms previous work up to an order of magnitude.
Cited by 1,082 works. doi:10.1145/775047.775109
Authors
References
- Fast Algorithms for Mining Association Rules in Large Databases
- Mining sequential patterns
- Mining sequential patterns: Generalizations and performance improvements
- Efficiently mining long patterns from databases
- Discovery of Frequent Episodes in Event Sequences
- Discovering Frequent Episodes in Sequences.
- PrefixSpan,: mining sequential patterns efficiently by prefix-projected pattern growth
- SPADE: An Efficient Algorithm for Mining Frequent Sequences
- Efficient mining of partial periodic patterns in time series database
- MAFIA: a maximal frequent itemset algorithm for transactional databases