TK-RNSP : efficient top-k repetitive negative sequential pattern mining

Abstract

Repetitive Negative Sequential Patterns (RNSPs) can provide critical insights into the importance of sequences. However, most current RNSP mining methods require users to set an appropriate support threshold to obtain the expected number of patterns, which is a very difficult task for the users without prior experience. To address this issue, we propose a new algorithm, TK-RNSP, to mine the Top-K RNSPs with the highest support, without the need to set a support threshold. In detail, we achieve a significant breakthrough by proposing a series of definitions that enable RNSP mining to satisfy anti-monotonicity. Then, we propose a bitmap-based Depth-First Backtracking Search (DFBS) strategy to decrease the heavy computational burden by increasing the speed of support calculation. Finally, we propose the algorithm TK-RNSP in an one-stage process, which can effectively reduce the generation of unnecessary patterns and improve computational efficiency comparing to those two-stage process algorithms. To the best of our knowledge, TK-RNSP is the first algorithm to mine Top-K RNSPs. Extensive experiments on eight datasets show that TK-RNSP has better flexibility and efficiency to mine Top-K RNSPs.