💻 computer science

Mining Quantitative Top-k Sequential Patterns under Constraints

This paper introduces a novel Constraint Programming framework that efficiently mines top-k quantitative sequential patterns under flexible user-defined constraints by leveraging a global constraint for dynamic support filtering and dedicated search strategies to accelerate convergence.

Original authors: Amina Kemmar, Chahira Touati, Amel Mounia Djebbar

Published 2026-11-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amina Kemmar, Chahira Touati, Amel Mounia Djebbar

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast archives of modern life, data often arrives not as simple lists of items, but as stories with numbers attached. When a customer buys groceries, they do not just purchase "milk"; they buy two gallons. When a patient receives treatment, they are given a specific dosage of medication, not just the drug itself. For decades, computer scientists have developed ways to find repeating stories in these massive collections of data, looking for sequences that happen often enough to be considered significant. This field, known as sequential pattern mining, helps businesses understand shopping habits and doctors recognize common treatment paths. However, a persistent challenge has remained: how to find the absolute best stories when the data is filled with these specific quantities, and how to do so without getting lost in a sea of millions of possibilities. Traditional methods often require researchers to guess a cutoff point for what counts as "frequent," a trial-and-error process that can miss the most important patterns or drown analysts in irrelevant details.

A team of researchers has tackled this problem by introducing a new method that acts like a highly disciplined filter, designed to find the top ten, top one hundred, or top one thousand most significant stories without needing to guess a cutoff point. Their approach, detailed in a recent study, focuses on "quantitative sequential patterns," which are sequences where the order of events matters just as much as the specific amounts involved. Imagine a hospital record where a patient first receives a high dose of an antibiotic, followed by a moderate dose of pain relief, and finally a small dose of a blood thinner. The researchers wanted to find the most common versions of this specific sequence, including the exact amounts, across thousands of patient records. The difficulty lies in the sheer volume of combinations; with different dosages and varying lengths of treatment, the number of potential patterns can become overwhelming.

To solve this, the researchers turned to a powerful mathematical framework called constraint programming. Instead of building a custom tool for every new type of question, this method allows the computer to be told exactly what rules to follow, such as "the pattern must be at least three steps long" or "the total amount of medicine must be under a certain limit." The core of their innovation is a dynamic way of searching. Rather than sifting through every single possibility from the bottom up, their algorithm starts by looking for the most frequent patterns first. It uses a clever strategy to quickly identify the strongest candidates and then raises the bar for what counts as a "winner." As soon as it finds a certain number of top patterns, it uses the weakest of those winners as a new minimum standard, instantly ignoring any new patterns that cannot beat that score. This process prunes the search space, cutting away millions of dead ends before the computer even has to look at them.

The researchers tested this method on real-world data, including records of web browsing habits, book purchases, and medical treatments. They compared their new system against existing tools designed for similar tasks. The results were clear: their approach was significantly faster and more reliable, especially when asked to find a large number of top patterns. In tests where other methods failed to finish within a reasonable time limit, their system continued to deliver results efficiently. For instance, when analyzing a dataset of web clicks containing nearly seventy thousand sequences, their method could find thousands of top patterns in a matter of minutes, while older techniques struggled or gave up entirely. The study also demonstrated that the system could easily handle complex rules, such as requiring that a specific item appear only a certain number of times or that the quantities follow a specific mathematical relationship, without needing to rewrite the underlying code.

One of the most striking aspects of this work is its flexibility. Because the method is built on a declarative framework, users can ask very specific questions about the data without needing to be experts in computer science. A doctor could ask for the most common treatment sequences where the total dosage of a drug stays below a safety threshold, or a retailer could look for purchasing patterns where a customer buys exactly three items in a row. The system answers these questions by integrating the rules directly into the search process, ensuring that the results are not just frequent, but also relevant to the specific constraints of the question. The researchers found that while adding more rules does increase the time it takes to find an answer, the system remains stable and predictable, avoiding the chaotic slowdowns that often plague other data mining tools.

This research represents a significant step forward in making complex data analysis accessible and practical. By combining the ability to handle specific quantities with a smart, dynamic search strategy, the new method offers a way to cut through the noise of big data and find the stories that truly matter. It proves that we do not need to sacrifice detail for speed; instead, by using the right mathematical tools, we can find the most important patterns in massive datasets with precision and efficiency. The work suggests that in fields ranging from healthcare to e-commerce, the future of data analysis lies in systems that can adapt to the specific needs of the user, finding the best answers without requiring a complete overhaul of the technology every time a new question is asked.

Technical Summary: Mining Quantitative Top-k Sequential Patterns under Constraints

Problem Statement

The paper addresses the challenge of Quantitative Sequential Pattern Mining (QSPM) under heterogeneous constraints, specifically focusing on the extraction of the top-k most frequent patterns. Traditional QSPM often relies on a minimum support threshold, which can be tedious to tune and may result in an overwhelming number of patterns, many of which are redundant. Furthermore, existing methods struggle to simultaneously handle:

Quantitative attributes: Items associated with numerical values (e.g., dosages, quantities) where the subsequence relation requires the pattern's quantity to be less than or equal to the database instance's quantity.
Top-k extraction: Identifying the $k$ most frequent patterns without a priori knowledge of a suitable support threshold.
Heterogeneous constraints: Integrating user-defined structural constraints (e.g., length, membership, regular expressions) and quantitative constraints (e.g., sum, average) within a unified framework.

Current state-of-the-art algorithms (e.g., TKS) often lack native support for quantitative attributes or struggle to integrate complex constraints without algorithmic redesign. Conversely, Constraint Programming (CP) approaches often lack efficient mechanisms for dynamic top-k pruning in quantitative settings.

Methodology

The authors propose QPP-TOPK, a novel approach based on Constraint Programming (CP) that integrates a dynamic top-k pruning mechanism into a global constraint framework.

1. Core Modeling

The approach utilizes a CSP model where a quantitative pattern of maximum length $\ell$ is encoded by $2\ell$ variables (alternating item and quantity variables). Empty symbols ( $\square$ ) allow for variable-length patterns within a fixed-size representation.

Global Constraint: The method adapts the Q-Preﬁx-Projection global constraint (originally proposed in [7]) to enforce both the subsequence relation (considering quantities) and the frequency constraint.
Dynamic Support Raising: A key mechanism is the dynamic adjustment of the minsup threshold. The algorithm maintains a list of the current top- $k$ patterns. The minsup is set to the support of the $k$ -th best pattern found so far. Any candidate pattern with a support lower than this bound is pruned.

2. Search Strategies

To accelerate convergence toward the top- $k$ patterns, the paper proposes two initialization strategies:

Base-Line (BL): Performs a standard depth-first search, adding the first $k$ valid patterns found to the list. This is noted to be inefficient as it may discover low-support patterns early.
Increasing-Length (IL): A novel strategy that explores patterns by length, starting from the minimum length ( $\ell_{min}$ ) and incrementally increasing. Since shorter patterns are statistically more likely to be frequent, this strategy aims to discover high-support patterns early, rapidly raising the minsup threshold and pruning the search space more effectively.

3. Constraint Integration

The CP framework allows for the declarative addition of constraints without modifying the core search algorithm:

Structural Constraints: Minimum/maximum length, membership (items must/w must not appear), and regular expressions (via finite automata).
Quantitative Constraints: Constraints on the sum, average, or specific values of quantities (e.g., total quantity $> M$ , or quantities following a periodic expression).

Key Contributions

The paper outlines five main contributions:

Formalization: Formalizing the Top-k Quantitative Sequential Pattern Mining problem under heterogeneous constraints.
Adaptation: Adapting a quantitative global CP constraint to support dynamic top-k pruning via a dynamic support bound.
Strategies: Proposing two initialization strategies, with the Increasing-Length (IL) strategy specifically designed to accelerate support raising.
Scalability: Empirically demonstrating that the approach scales favorably compared to the state-of-the-art TKS algorithm, particularly for large values of $k$ .
Flexibility: Showing that CP enables the seamless integration of complex structural and quantitative constraints without algorithmic redesign.

Experimental Results

Experiments were conducted on six real-world datasets (Sign, Leviathan, FIFA, MSNBC, BIBLE, Kosarak) with synthetic quantitative attributes added.

Comparison of Strategies: QPP-TOPK-IL consistently outperformed QPP-TOPK-BL and the QPP-TOPK-NAIVE (which failed to produce results within time limits). The paper notes that the QPP-TOPK-BL method is approximately 1.5 to 3 times slower than QPP-TOPK-IL, and IL was the only method to handle all configurations (up to $k=3000$ ) successfully.
Comparison with State-of-the-Art: When compared to TKS (with quantities fixed to 1), QPP-TOPK-IL demonstrated superior scalability. As $k$ increased, the performance gap widened significantly. For example, on the FIFA dataset, QPP-TOPK-IL took 443.34 seconds for $k=3000$ , whereas TKS execution time "literally explodes" from 400 seconds to "more than 3000 seconds," exceeding the 1800-second time limit.
Constraint Handling: The approach successfully extracted top-k patterns under various constraints (fixed items, length limits, quantity sums, regular expressions). The results indicated that while constraints reduce the solution space semantically, they do not always linearly reduce execution time; complex combinations can impact pruning efficiency.

Significance and Claims

The paper claims that QPP-TOPK fills a critical gap in data mining by providing a unified framework that handles quantitative semantics, top-k extraction, and heterogeneous constraints simultaneously.

Declarative Power: Unlike ad-hoc algorithms that require specific implementations for each new constraint type, the CP-based approach allows users to define constraints declaratively.
Quantitative Semantics: The authors distinguish their work from approaches like Seq2Pat, noting that while Seq2Pat handles non-monotone constraints, it treats quantities as attributes for filtering rather than structural components of the pattern. QPP-TOPK embeds quantities directly into the pattern definition, enabling the discovery of patterns where semantics depend on quantitative values (e.g., dosage-dependent therapeutic pathways).
Practicality: The method offers a practical alternative for scenarios where the minimum support threshold is unknown or difficult to set, providing a manageable set of the most representative patterns.

The authors conclude that while the approach shows significant promise, future work will explore extensions to fuzzy and utility-based patterns, parallel search strategies, and the provision of public benchmarks.