Affiliations: [a] Department of Computer Science and Engineering, York University, Toronto, ON, Canada | [b] Department of Computer Science, National Chiao Tung University, Taiwan | [c] Smart Network System Institute, Institute for Information Industry, Taipei, Taiwan
Correspondence:
[*]
Corresponding author: Morteza Zihayat, Department of Computer Science and Engineering,York University, Toronto, ON, Canada. E-mail:zihayatm@cse.yorku.ca
Abstract: High utility sequential pattern (HUSP) mining has emerged as
a novel topic in data mining. Although some preliminary works have
been conducted on this topic, they incur the problem of producing a large search space for high utility sequential patterns. In addition, they mainly focus on mining HUSPs in
static databases and do not take streaming data into
account, where unbounded data come continuously and often at a
high speed. To efficiently deal with
both problems, we propose a novel framework for mining high utility sequential patterns over static and streaming databases. In this regard, two efficient data structures named ItemUtilLists (Item Utility Lists) and HUSP-Tree (High Utility Sequential Pattern Tree) are proposed to maintain essential information for mining HUSPs in both offline and online fashions.
In addition, a novel utility model called Sequence-Suffix
Utility is proposed for effectively pruning the search space in
HUSP mining. We propose an algorithm named HUSP-Miner (High Utility Sequential Pattern Miner) to find HUSPs in static databases efficiently. Then, a one-pass algorithm named HUSP-Stream (High Utility Sequential Pattern mining over Data Streams) is proposed to incrementally update ItemUtilLists and HUSP-Tree online and find HUSPs over data streams.
To the best of our knowledge, HUSP-Stream is the first method to find HUSPs over data streams.
Experimental results on both real and synthetic datasets show that
HUSP-Miner outperforms the compared
algorithms substantially in terms of execution time, memory usage
and number of generated candidates.
The experiments also demonstrate impressive performance of HUSP-Stream to update the data structures and discover HUSPs over data streams.
Keywords: High utility sequential pattern mining, data streams, sliding window
