Affiliations: [a] Innovative Information Industry Research Center, Harbin Institute of Technology Shenzhen Graduate School, HIT Campus Shenzhen University Town, Xili, Shenzhen, China | [b] Shenzhen Key Laboratory of Internet Information Collaboration, School of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School, HIT Campus Shenzhen University Town, Xili, Shenzhen, China | [c] Department of Computer Science and Information Engineering, National University of Kaohsiung, Kaohsiung, Taiwan | [d] Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan | [e] Department of Computer Science and Information Engineering, National Cheng Kung University, Tainan, Taiwan | [f] Department of Industrial and Information Management, National Cheng Kung University, Tainan, Taiwan
Correspondence:
[*]
Corresponding author: Jerry Chun-Wei Lin, Innovative Information Industry Research Center, School of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School, HIT Campus Shenzhen University Town, Xili, Shenzhen 518055, China. E-mail:jerrylin@ieee.org
Abstract: One of the major concerns with Sequential-pattern
mining (SPM) is how to discover frequent sequences from transactional
databases. Most SPM algorithms can only handle static databases, which is
not practical in real-life situations. The Fast UPdated 2 (FUP2) algorithm
was proposed to maintain and update the discovered association rules for
transaction deletion. This algorithm can also be extended to SPM for
maintaining the discovered frequent sequences, especially when some
sequential records are deleted from their original databases. The original
database is, however, required to be rescanned if the maintained sequences
are small in the deleted sequential records. In the past, a pre-large
concept was proposed to reduce the computational cost of database rescans
until the number of deleted customers of the deleted sequential records
achieves the designed safety bound. In this paper, a PreFUSP-TREE-DEL
algorithm is proposed to adopt a pre-large FUSP-tree structure and the
pre-large concept is used for maintaining and updating the discovered
sequential patterns with record deletion. The proposed algorithm first
partitions the discovered sequential patterns into three parts with nine
cases. The discovered sequential patterns of each case are then maintained
and updated by the designed procedure. Based on the proposed
PreFUSP-TREE-DEL algorithm, it is unnecessary to rescan the original
database until the cumulative number of deleted customers achieves the
designed safety bound. The conducted experiments show that that the proposed
PreFUSP-TREE-DEL algorithm has good performance when compared to other
batch-mode algorithms or other maintenance algorithms.
Keywords: Record deletion, sequential patterns, pre-large concept, dynamic database, FUSP tree
