Constraint-Based Sequential Pattern Mining with Decision Diagrams

Amin Hosseininasab, Willem-Jan van Hoeve, André A. CiréAAAI 2019 · DOI

Introduction

Sequential Pattern Mining (SPM) is a cornerstone of data analysis, enabling researchers to identify recurring sequences in complex datasets—from user navigation paths on websites to genomic sequences. However, standard SPM often generates an overwhelming number of patterns, many of which lack practical significance. To address this "data deluge," Constraint-Based Sequential Pattern Mining (CSPM) was developed to filter results based on user-defined criteria.

The Challenge of Non-Monotone Constraints

While constraints such as sequence length are easily handled through early pruning (anti-monotone properties), more complex "non-monotone" constraints—such as average price or median value—present a significant computational challenge. In these cases, adding an item to a sequence might temporarily invalidate a constraint, only for a subsequent item to make it valid again. Traditionally, this has forced researchers to use inefficient "generate-and-check" methods that mine all possible patterns before filtering, leading to massive memory consumption and slow execution times.

Methodology: MDD-Based Representation

The authors introduce a novel approach using Multi-valued Decision Diagrams (MDDs) to represent the entire sequence database. An MDD is a layered, directed acyclic graph where paths from the root to the terminal node represent valid sequences. This structure is inherently compact, exploiting symmetries and redundancies within the data.

Figure 2: Comparison between an original MDD and one with imposed constraints, showing how the search space is reduced.

By constructing the MDD using backward induction, the algorithm can store "metadata" at each node. This metadata acts as a look-ahead mechanism; for instance, a node might store the maximum possible sum reachable from that point. If the metadata indicates that no future extension of a path can satisfy a constraint, that branch is pruned immediately.

The MPP Algorithm

The core contribution is the MDD Prefix-Projection (MPP) algorithm. Unlike previous methods, MPP integrates constraint reasoning directly into the mining process. It provides specific logic for pruning based on Span, Sum, Average, and Median—the latter two being notoriously difficult for existing CSPM tools. This "future knowledge" allows MPP to avoid exploring vast portions of the search space that are guaranteed to fail.

Experimental Evaluation

The researchers tested MPP against state-of-the-art Constraint Programming (CP) solvers and standard prefix-projection methods using five real-world click-stream datasets, including the massive Kosarak and MSNBC sets. Since these datasets lacked numerical attributes, the authors synthetically added time, price, and quality metrics to test complex constraint reasoning.

Figure 6: Performance benchmarks on large datasets (Kosarak, MSNBC, BMSWebView2) showing MPP's efficiency across various support thresholds.

The results demonstrate that MPP is significantly more efficient than its predecessors. On the MSNBC dataset, MPP was approximately twice as fast as the standard PPCC approach. Furthermore, MPP exhibited remarkable memory efficiency; while competing CP solvers required up to 14GB of RAM on certain benchmarks, MPP consistently stayed under 1GB.

Conclusion

By leveraging the structural advantages of Multi-valued Decision Diagrams, the MPP algorithm provides a scalable and memory-efficient solution for constraint-based sequential pattern mining. It is the first algorithm to successfully incorporate difficult non-monotone constraints like average and median directly into the mining process, paving the way for more sophisticated data analysis in large-scale sequential databases.

Summary updated

BibTeX
@inproceedings{hosseininasab2019constraint,
  author = {Amin Hosseininasab and Willem-Jan van Hoeve and André A. Ciré},
  title = {{Constraint-Based Sequential Pattern Mining with Decision Diagrams}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33011495},
}
Figure