MNSPM: Merging-based nonoverlapping gap-constrained sequential pattern mining

Gap-constrained sequential pattern mining (Gap-SPM) discovers meaningful patterns by imposing gap constraints between consecutive pattern items. Among three widely-used support calculation conditions, the nonoverlapping condition has attracted significant research attention because it satisfies the Apriori property for efficient candidate pruning. However, existing nonoverlapping Gap-SPM methods primarily adopt the pattern join strategy for candidate generation and construct patterns through item-by-item extension. This approach results in extensive repetitive pattern construction during the mining process, leading to computational inefficiency. To address this challenge, this paper proposes MNSPM, a Merging-based Nonoverlapping Gap-Constrained Sequential Pattern Mining algorithm that ensures both pattern completeness and high efficiency. Utilizing 2-patterns as building blocks, we design a novel pattern construction mechanism that generates longer patterns by iteratively merging 2-subpatterns. We then propose HB-TableSet, an indexed structure that compactly stores pattern occurrences and enables rapid support calculation. Additionally, a common-position-based pruning strategy (CPS) is developed to identify infrequent candidates early, particularly for long-sequence datasets. Extensive experiments on eight real-world datasets demonstrate that MNSPM significantly outperforms NOSEP in mining efficiency, achieving speedups predominantly ranging from 2.3 ×  to 6.4 × .