On incremental high utility sequential patern mining

Jun Zhe Wang, Jiun-Long Huang

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


High utility sequential pattern (HUSP) mining is an emerging topic in pattern mining, and only a few algorithms have been proposed to address it. In practice, most sequence databases usually grow over time, and it is inefficient for existing algorithms to mine HUSPs from scratch when databases grow with a small portion of updates. In view of this, we propose the IncUSP-Miner+ algorithm to mine HUSPs incrementally. Specifically, to avoid redundant re-computations, we propose a tighter upper bound of the utility of a sequence, called Tight Sequence Utility (TSU), and then we design a novel data structure, called the candidate pattern tree, to buffer the sequences whose TSU values are greater than or equal to the minimum utility threshold in the original database. Accordingly, to avoid keeping a huge amount of utility information for each sequence, a set of concise utility information is designed to be stored in each tree node. To improve the mining efficiency, several strategies are proposed to reduce the amount of computation for utility update and the scopes of database scans. Moreover, several strategies are also proposed to properly adjust the candidate pattern tree for the support of multiple database updates. Experimental results on some real and synthetic datasets show that IncUSP-Miner+ is able to efficiently mine HUSPs incrementally.

Original languageEnglish
Article number55
JournalACM Transactions on Intelligent Systems and Technology
Issue number5
StatePublished - 1 Apr 2018


  • High utility sequential pattern mining
  • Incremental high utility sequential pattern mining
  • Incremental mining
  • Utility mining

Fingerprint Dive into the research topics of 'On incremental high utility sequential patern mining'. Together they form a unique fingerprint.

Cite this