Rapid High Utility Sequential Pattern Mining With Negative and Positive Values

ABSTRACT High Utility Sequential Pattern Mining (HUSPM) can evaluate the practical value of patterns while capturing temporal relationships. However, negative utility items (such as discounts, returns, and wastage) prevalent in real‐world applications pose two major challenges to existing methods: Firstly, negative utility items complicate the construction of projection databases and utility calculations. Traditional structures often require multiple accesses to the original sequence, incurring high time and memory costs; secondly, existing upper bounds often prove insufficiently compact when both positive and negative utilities coexist, thereby diminishing pruning effectiveness and inducing candidate explosion. To address these issues, this paper proposes the Rapid mining High Utility Sequential Pattern with Negative items (RHUSN) algorithm. This algorithm designs a compact data structure, Neg‐Seq‐Pro, which employs a shared negative sequence array and explicit projection lists to achieve unified modeling and rapid computation of both positive and negative utilities. Concurrently, it introduces a tighter utility upper bound, NTRSU, alongside a corresponding two‐tier pruning strategy comprising ‘prefix‐level pruning’ and ‘item‐level pruning’. This approach significantly reduces candidate expansion and redundant computation while ensuring result completeness. Extensive experimental results demonstrate that RHUSN achieves notable advantages over existing representative methods in terms of runtime, memory consumption, and the number of candidate patterns. This validates the effectiveness and scalability of the proposed data structure and upper bound pruning strategy in negative utility scenarios.