Incremental Discovery of Sequential Patterns Using a Backward Mining Approach

摘要

Common sequential pattern mining algorithms handle static databases. Once the data change, the previous mining result will be incorrect, and we need to restart the entire mining process for the new updated sequence database. Previous approaches, within either Apriori-based or projection-based framework, mine patterns in a forward manner. Considering the incremental characteristics of sequence-merging, we develop a novel technique, called backward mining, for efficient incremental pattern discovery. We propose an algorithm, called BSPinc, for incremental mining of sequential patterns using a backward mining strategy. Stable sequences, whose support counts remain unchanged in the updated database, are identified and eliminated from the support counting process. Candidate sequences generated using backward extensions can be mined recursively within the ever-shrinking space of the projected sequences. The experimental results show that BSPinc worked an average of 2.5 times faster than the well-known IncSpan algorithm and outperformed SPAM an average of 3 times faster.