Incremental update on sequential patterns in large databases by implicit merging and efficient counting

作者:

Highlights:

摘要

Current approaches for sequential pattern mining usually assume that the mining is performed in a static sequence database. However, databases are not static due to update so that the discovered patterns might become invalid and new patterns could be created. In addition to higher complexity, the maintenance of sequential patterns is more challenging than that of association rules owing to sequence merging. Sequence merging, which is unique in sequence databases, requires the appended new sequences to be merged with the existing ones if their customer ids are the same. Re-mining of the whole database appears to be inevitable since the information collected in previous discovery will be corrupted by sequence merging. Instead of re-mining, the proposed IncSP (Incremental Sequential Pattern Update) algorithm solves the maintenance problem through effective implicit merging and efficient separate counting over appended sequences. Patterns found previously are incrementally updated rather than re-mined from scratch. Moreover, the technique of early candidate pruning further speeds up the discovery of new patterns. Empirical evaluation using comprehensive synthetic data shows that IncSP is fast and scalable.

论文关键词:Data mining,Sequential patterns,Incremental update,Sequence discovery,Sequence merging

论文评审过程:Received 6 February 2002, Revised 20 December 2002, Accepted 2 April 2003, Available online 30 May 2003.

论文官网地址:https://doi.org/10.1016/S0306-4379(03)00036-X