Incremental mining of high utility sequential patterns in incremental databases

Jun Zhe Wang, Jiun-Long Huang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

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 computations, we propose a tighter upper bound of the utility of a sequence, called TSU, and then design a novel data structure, called the candidate pattern tree, to maintain the sequences whose TSU values are greater than or equal to the minimum utility threshold. Accordingly, to avoid keeping a huge amount of utility information for each sequence, a set of auxiliary utility information is designed to be stored in each tree node. Moreover, for those nodes whose utilities have to be updated, a strategy is also proposed to reduce the amount of computation, thereby improving the mining efficiency. Experimental results on three real datasets show that IncUSP-Miner is able to efficiently mine HUSPs incrementally.

Original languageEnglish
Title of host publicationCIKM 2016 - Proceedings of the 2016 ACM Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Pages2341-2346
Number of pages6
ISBN (Electronic)9781450340731
DOIs
StatePublished - 24 Oct 2016
Event25th ACM International Conference on Information and Knowledge Management, CIKM 2016 - Indianapolis, United States
Duration: 24 Oct 201628 Oct 2016

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings
Volume24-28-October-2016

Conference

Conference25th ACM International Conference on Information and Knowledge Management, CIKM 2016
CountryUnited States
CityIndianapolis
Period24/10/1628/10/16

Keywords

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

Fingerprint Dive into the research topics of 'Incremental mining of high utility sequential patterns in incremental databases'. Together they form a unique fingerprint.

Cite this