TALENT: Targeted Mining of Non-overlapping Sequential Patterns
Zefeng Chen, Wensheng Gan, Gengsen Huang, Zhenlian Qi, Yan Li, Philip S. Yu · ACM Transactions on Management Information Systems · 2025
With the widespread application of sequential pattern mining (SPM) algorithms, sequential patterns that allow gap constraints are valuable for discovering knowledge from biological data such as DNA and protein sequences and some non-biological data. This approach achieves a balance between contiguous constraint SPM and traditional SPM, enabling the discovery of a wider range of patterns while accommodating user-defined gaps as needed. Among all kinds of gap-constrained mining, non-overlapping SPM, which involves discovering interesting patterns where occurrences do not overlap with each other, satisfies the anti-monotonic property (the Apriori property, i.e., the support of a pattern is not larger than that of its sub-patterns). However, existing algorithms do not search for target sequential patterns, resulting in unnecessary and redundant pattern generation. Targeted pattern mining is a technique employed to discover itemsets or sequential patterns that are directly related to items of interest to the user. In this article, we define and formalize the problem of targeted non-overlapping SPM and propose an algorithm named TALENT ( TA rgeted mining of Sequentia L Patt E r N with Cons T raints). Two search methods, including breadth-first and depth-first searching, are designed to address the generation of patterns. Furthermore, several pruning strategies are presented to reduce the reading of sequences and items in the data and terminate redundant pattern extensions. Finally, we conduct extensive experiments to compare the TALENT algorithm with the existing algorithms for mining non-overlapping sequential patterns. The experimental results demonstrate that TALENT has excellent mining efficiency and can deal efficiently with different query settings. In the best-case scenario, TALENT exhibits a three-order-of-magnitude reduction in time and a memory decrease to 20% of the original consumption compared to the baseline algorithm, NOSEP \(\rm _{Ta}\) .