Mining and Maintenance of Sequential Patterns using a Backward Generation Framework

摘要

Common sequential pattern mining algorithms handle static databases. Once the database updates, previous mining results would be incorrect, and we need to restart the entire mining process from scratch. Previous approaches mine patterns in a forward manner in both static and incremental databases. Considering the incremental characteristics of sequence-merging, we propose a novel methodology, called backward mining, to update the patterns in an incremental sequence database. Stable sequences, whose support counts remain unchanged in the updated database, are identified and eliminated from the support counting process using the backward mining methodology. We develop both the BSpan algorithm within the pattern-growth framework and the BSPinc algorithm within the Apriori-based framework for incremental discovery of sequential patterns. BSpan prunes all the stable sequences and their super sequences so that database projections are minimized. BSPinc generates candidate sequences using backward extensions and mines patterns recursively within the ever-shrinking bit-sequence space. The experimental results using both synthetic and real-world datasets show that BSpan and BSPinc work an average of 4 times faster than the well-known IncSpan algorithm. In comparison to re-mining, the average improvement is 6 times faster.