Frequency-based Constrained Sampling for Interval Patterns
2026-06-08 • Artificial Intelligence
Artificial Intelligence
AI summaryⓘ
The authors present CFips, a method to efficiently sample patterns that fit certain rules from a large set of possibilities. Instead of looking through all patterns, CFips directly includes user-defined rules in the sampling process, making it faster and more focused. They prove that CFips fairly samples patterns based on how often they appear within the allowed rules. Tests show that their method can finish tasks quicker than traditional approaches that don’t use these rules during sampling.
pattern miningsamplinginterval patternssyntactic constraintsmulti-step samplingfrequencypattern spaceconstraint decompositionexact sampling
Authors
Djawad Bekkoucha, Abdelkader Ouali, Bruno Crémilleux
Abstract
Output space pattern sampling is a powerful alternative to exhaustive pattern mining for exploring large pattern spaces, as it enables users to focus on representative patterns drawn according to a chosen interestingness measure. In this paper, we address the problem of sampling interval patterns under user-defined syntactic constraints. We introduce CFips, a sampling approach that incorporates constraints directly into the sampling procedure. The approach relies on a multi-step sampling framework and supports several syntactic constraints by decomposing them into elementary predicates on interval bounds while preserving exact sampling guarantees. We formally prove that CFips samples interval patterns proportionally to their frequency within the constrained pattern space. The experimental results show that integrating constraints into the sampling procedure enables to complete mining tasks that would otherwise fail within a given time out.