🤖 AI

Frequency-based Constrained Sampling for Interval Patterns

This paper introduces CFips, a frequency-based constrained sampling approach that integrates user-defined syntactic constraints directly into the sampling procedure to efficiently generate representative interval patterns with exact frequency guarantees, enabling mining tasks that would otherwise fail due to time constraints.

Original authors: Djawad Bekkoucha, Abdelkader Ouali, Bruno Crémilleux

Published 2026-06-09

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Djawad Bekkoucha, Abdelkader Ouali, Bruno Crémilleux

Original paper licensed under CC BY 4.0 (http://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

Imagine you are a data detective trying to find specific clues hidden inside a massive, chaotic warehouse filled with millions of boxes. Each box contains a pattern (a set of rules describing numbers), and some boxes are very common (frequent), while others are rare.

Your boss (the data analyst) gives you a very specific list of rules: "Only bring me boxes that contain the number 6, but never boxes that contain the number 12, and the box must be bigger than size 5."

The Old Way: The "Throw and Check" Method

In the past, if you wanted to find these specific boxes, you had two bad options:

The Exhaustive Search: You open every single box in the warehouse, check if it fits your boss's rules, and then pick the ones you need. This takes forever. If the warehouse is huge, you might die of old age before you finish.
The "Throw and Check" Sampling: You grab a box at random. You check the rules. If it fits, you keep it. If it doesn't, you throw it back and grab another one.
- The Problem: If your rules are strict (like "no number 12"), you might grab 99 boxes that have a 12 in them before you finally find one that works. This is called a high rejection rate. You waste a massive amount of time throwing boxes back.

The New Solution: CFips (The "Smart Filter" Method)

The authors of this paper, Bekkoucha, Ouali, and Crémilleux, invented a new method called CFips. Instead of grabbing a box and then checking if it fits, CFips changes the way you grab the box so that you only ever pick boxes that are guaranteed to fit the rules.

Here is how CFips works, using a simple analogy:

1. The "Smart Map" (NIPQ)

Before you even start grabbing boxes, CFips creates a special map of the warehouse. This map doesn't list every single box. Instead, for every location in the warehouse, it calculates: "If I stand here, how many valid boxes can I reach that satisfy my boss's rules?"

It does this by breaking the boss's complex rules down into tiny, simple checks for the top and bottom edges of the boxes (the interval bounds).

Analogy: Imagine the boss says, "The box must be between 3 and 6 inches tall." CFips looks at the warehouse and instantly knows, "Okay, for this specific spot, I can only pick boxes that start at 3, 4, or 5 inches, and end at 6 inches." It ignores all the other impossible sizes immediately.

2. The Two-Step Dance

CFips picks a pattern in two smooth steps:

Step 1: It picks a location in the warehouse based on the "Smart Map." It is more likely to pick a location where there are many valid boxes (because those patterns are more "frequent" or common).
Step 2: Once it picks a location, it randomly selects a specific box from only the valid ones available at that spot.

Because the "Smart Map" already filtered out the impossible boxes, every single box CFips picks is guaranteed to satisfy the boss's rules. There is zero time wasted throwing boxes back.

Why This Matters

The paper tested this against the old "Throw and Check" methods (called Fips and Uniform) using real data sets like medical records (cancer, diabetes) and glass properties.

The Result: When the rules got strict (many constraints), the old methods started failing. They would spend minutes or even hours just throwing boxes back, eventually giving up (timeout) without finding enough valid patterns.
The CFips Advantage: CFips stayed fast and steady. It didn't matter how strict the rules were; it found the valid patterns instantly.
The "Empty Room" Check: If there are no boxes in the warehouse that fit the rules, CFips knows this immediately and tells the analyst, "No solution exists," so the analyst doesn't have to wait for a long process to fail.

The Bottom Line

The paper claims that CFips is the first method that can efficiently sample numerical patterns (like ranges of numbers) while strictly following user rules, without wasting time on patterns that don't fit. It does this by baking the rules directly into the selection process, ensuring that every sample you get is both interesting (frequent) and valid.

Technical Summary: Frequency-based Constrained Sampling for Interval Patterns

Problem Statement
In the domain of numerical data mining, the search space for interval patterns is exponentially large, making exhaustive enumeration impractical. While output-space pattern sampling offers a solution by selecting patterns based on an interestingness measure (such as frequency), standard sampling methods often struggle when user-defined syntactic constraints are introduced. Naive approaches, such as sampling followed by post-processing rejection, suffer from prohibitively high rejection rates when constraints are restrictive, often failing to return results within reasonable time limits. Furthermore, existing constrained sampling methods for numerical data are limited; many cannot integrate constraints directly into the sampling procedure without losing exact sampling guarantees or requiring exhaustive enumeration.

Methodology: CFips
The paper proposes CFips (Constrained Frequency-based Interval Pattern Sampling), the first approach designed to sample interval patterns from numerical data proportionally to their frequency while satisfying a conjunction of syntactic constraints directly during the sampling process.

The methodology relies on a multi-step sampling framework that avoids explicit enumeration of the constrained pattern space. The core innovation is the NIPQ (Number of Interval Patterns Query) function, a constrained counting mechanism.

Constraint Decomposition: Syntactic constraints (e.g., inclusion, exclusion, bounds) are decomposed into elementary predicates applied to the lower and upper bounds of interval patterns.
NIPQ Function: For each object $g$ in the dataset, NIPQ calculates the exact number of valid interval patterns that cover $g$ and satisfy the query $Q$ . It does this by determining the set of admissible lower bounds ( $L_Q$ ) and upper bounds ( $J_Q$ ) for each attribute based on the object's value and the query predicates. The count is the product of the sizes of these sets across all attributes.
Two-Step Sampling:
- Step 1: An object $g$ is drawn from the dataset with a probability proportional to its NIPQ weight (the number of valid patterns covering it).
- Step 2: Given the selected object, an interval pattern is drawn uniformly from the set of valid patterns covering that object. This is achieved by independently selecting a lower bound from $L_Q$ and an upper bound from $J_Q$ for each attribute.

Key Contributions

Direct Constraint Integration: CFips is the first method to incorporate syntactic constraints directly into the sampling procedure for numerical interval patterns, eliminating the need for rejection-based post-processing.
Exact Sampling Guarantees: The authors formally prove that CFips samples interval patterns proportionally to their frequency within the constrained pattern space ( $LV_Q$ ), provided the constraints can be decomposed into predicates on interval bounds.
Instant Failure Detection: Unlike rejection-based methods that may loop indefinitely, CFips can instantly determine if the constrained pattern space is empty (if NIPQ returns 0 for all objects), allowing the system to immediately report the absence of a solution.
Handling Numerical Data: The approach preserves the original information of numerical data by using interval patterns, avoiding the information loss associated with binarization.

Experimental Results
The evaluation compares CFips against Fips (frequency-based sampling with post-processing rejection) and Uniform (uniform sampling with post-processing rejection) across five numerical datasets (cancer, diabetes, glass, AP, NT).

Rejection Rates: Classical methods (Fips and Uniform) exhibited extremely high rejection rates (often exceeding 90% and reaching 99.98%) as the number of constraints increased. Fips, in particular, struggled with exclusion constraints due to its bias toward frequent patterns (which tend to have wider intervals).
Computational Time: As the number of constraints increased, the CPU time for Fips and Uniform grew significantly, often exceeding the two-minute timeout limit before the required number of valid patterns could be obtained. In contrast, CFips maintained a constant and significantly lower computational time regardless of the number of constraints.
Scalability: CFips successfully completed mining tasks that failed for the baseline methods within the given time limits, demonstrating its ability to handle complex constraint conjunctions efficiently.

Significance and Claims
The paper claims that integrating constraints directly into the sampling procedure is essential for efficient pattern mining in numerical data. By avoiding the "long-tail phenomenon" of rejecting invalid samples, CFips enables analysts to explore constrained subspaces that would otherwise be inaccessible due to time constraints. The authors emphasize that this approach allows for the immediate detection of empty search spaces and ensures that the sampling distribution remains mathematically exact within the constrained space.

Future Directions
The authors identify several avenues for future work, including:

Integrating CFips into interactive mining settings for real-time analyst feedback.
Extending the range of supported constraints to include complex measures like frequency thresholds or hypervolume, which are difficult to decompose into elementary predicates.
Investigating additional interestingness measures for numerical data, such as density.