[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

Journal of Information Science and Engineering, Vol. 34 No. 5, pp. 1329-1349

Mining and Maintenance of Sequential Patterns using a Backward Generation Framework

1Department of Information Engineering and Computer Science
Feng Chia University

Taichung 407 Taiwan
2Department of Information Management
Chaoyang University of Technology

Taichung, 417 Taiwan
E-mail: linmy@mail.fcu.edu.tw, schsueh@cyut.edu.tw, zesiva01@hotmail.com

  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. 

Keywords: incremental discovery, sequential pattern, backward mining, stable sequence, sequence merging, incremental database

  Retrieve PDF document (JISE_201805_13.pdf)