TK-RNSP: Efficient Top-K Repetitive Negative Sequential Pattern mining

作     者：Lan, Dun Sun, Chuanhou Dong, Xiangjun Qiu, Ping Gong, Yongshun Liu, Xinwang Fournier-Viger, Philippe Zhang, Chengqi 

作者机构：Qilu Univ Technol Shandong Comp Ctr Key Lab Comp Power Network & Informat Secur Natl Supercomp Ctr JinanShandong Acad SciMinist Jinan 250353 Peoples R China Shandong Fundamental Res Ctr Comp Sci Shandong Prov Key Lab Comp Power Internet & Serv C Jinan 250101 Peoples R China Nanjing Univ Posts & Telecommun Sch Internet Things Nanjing 210023 Peoples R China Shandong Univ Sch Software Jinan 250100 Peoples R China Natl Univ Def Technol Sch Comp Changsha 410003 Hunan Peoples R China Shenzhen Univ Coll Comp Sci & Software Engn Shenzhen 518060 Peoples R China Hong Kong Polytech Univ Dept Data Sci & Artificial Intelligence Hong Kong 100872 Peoples R China 

出 版 物：《INFORMATION PROCESSING & MANAGEMENT》 (Inf. Process. Manage.)

年 卷 期：2025年第62卷第3期

核心收录：

学科分类：1205[管理学-图书情报与档案管理] 12[管理学] 120502[管理学-情报学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [62202270, 62076143] Fundamental Research Promotion Plan of Qilu University of Technology (Shandong Academy of Sciences, China) [2021JC02009] Shandong Excellent Young Scientists Fund (Oversea) , China [2022HWYQ-044] Taishan Scholar Project of Shandong Province, China [tsqn202306066] 

主　　题：Sequential pattern mining Negative sequential pattern Top-K repetitive negative sequential patterns Nonoverlapping 

摘      要：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 bitmapbased Depth-First Backtracking Search (DFBS) strategy to decrease the heavy computational burden by increasing the speed of support calculation. Finally, we propose the algorithm TKRNSP 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.