  High-utility sequential pattern mining (HUSPM) has emerged as an important
topic due to its wide application and considerable popularity. However, due to
the combinatorial explosion of the search space when the HUSPM problem
encounters a low utility threshold or large-scale data, it may be
time-consuming and memory-costly to address the HUSPM problem. Several
algorithms have been proposed for addressing this problem, but they still cost
a lot in terms of running time and memory usage. In this paper, to further
solve this problem efficiently, we design a compact structure called sequence
projection (seqPro) and propose an efficient algorithm, namely discovering
high-utility sequential patterns with the seqPro structure (HUSP-SP). HUSP-SP
utilizes the compact seq-array to store the necessary information in a sequence
database. The seqPro structure is designed to efficiently calculate candidate
patterns' utilities and upper bound values. Furthermore, a new upper bound on
utility, namely tighter reduced sequence utility (TRSU) and two pruning
strategies in search space, are utilized to improve the mining performance of
HUSP-SP. Experimental results on both synthetic and real-life datasets show
that HUSP-SP can significantly outperform the state-of-the-art algorithms in
terms of running time, memory usage, search space pruning efficiency, and
scalability.
