An efficient algorithm to maintain the discovered frequent sequences with record deletion

摘要

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.