Frequency-based Constrained Sampling for Interval Patterns Djawad Bekkoucha1,2 , Abdelkader Ouali2 , and Bruno Crémilleux2 Laboratoire Interdisciplinaire des Sciences du Numérique (LISN), Université Paris-Saclay, CNRS, 91405 Orsay, France [email protected] 2 Université Caen Normandie, ENSICAEN, CNRS, Normandie Univ, GREYC UMR6072, F-14000 Caen, France [email protected]
arXiv:2606.09666v1 [cs.AI] 8 Jun 2026
1
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 multistep 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. Keywords: Data Mining · Numerical Data · Output Space Pattern Sampling · Constrained Sampling
1
Introduction
Data scientists have a central role for knowledge discovery from data. In practice, analysts want to interact (visualize, select, explore) not only with the data, but also with the patterns or models supported by the data. To carry out such processes, the field of pattern mining has shifted to user-centered methods [1]. For that purpose, it is essential to produce high quality results within a very short time to ensure a tight coupling between the system and the analyst. Pattern sampling is one solution to this challenge [2–4]. Pattern sampling aims to randomly select a pattern V with probability proportional to its interestingness measure m(V). For example, when using frequency as the interestingness measure, a pattern V1 that is twice as frequent as a pattern V2 is twice as likely to be sampled [3]. Unfortunately, pattern sampling often tends to focus on parts of the search space with a high density
2
D. Bekkoucha et al.
of uninteresting patterns (i.e., many patterns with low values for m) because these subspaces contain many patterns. For example, in the case of sequential data and the frequency interestingness measure, there is a large number of long patterns with a low frequency. To minimize this phenomenon, known as the "long-tail phenomenon", Diop et al. [5] proposed adding a maximum length constraint to the sampling process. Still for frequency measure but for Boolean data, Soulet [6] defined a generic sampling method that incorporates a minimum frequency threshold to remove infrequent patterns. The idea of combining constraints and sampling seems natural. Indeed, there is no reason not to immediately remove from the search space any patterns that do not satisfy the constraints, i.e., patterns that do not satisfy the analyst’s conditions. However, this is not necessarily simple. For example, even for the simple frequency constraint, it is necessary to consider not only a pattern but also its support, which makes the work more difficult. A naive method that consists of drawing a pattern and then rejecting it if it does not satisfy the constraint can lead to a large number of rejections. An exhaustive extraction of all patterns followed by post-processing does not scale and loses the advantages of the sampling. To the best of our knowledge, there are very few works combining sampling while pushing the constraint into the extraction process [5, 7, 6]. In this paper, we define CFips the first sampling approach that incorporates constraints directly into the sampling procedure for numerical data. We choose to keep the complete original information expressed by the numerical data by using Interval Patterns [8]. This approach prevents the loss of information that occurs when data are converted into a binary representation [9]. CFips relies on a multi-step sampling framework [3]. The key principle is N IPQ , a constrained counting function that computes, for each object, the exact number of interval patterns covering it while satisfying the constraints, without explicit pattern enumeration. CFips handles queries made of conjunctions of syntactic constraints by decomposing them into elementary predicates on interval bounds. We formally prove that CFips samples interval patterns proportionally to their frequency within the constrained pattern space. If no pattern satisfies the query, CFips instantly indicates that there is no solution. The analyst does not have to wait for a process that could take a long time to end. The experimental results show the interest of integrating constraints into the sampling process. Among other things, this makes it possible to complete mining tasks that would otherwise fail within a given time out. Contrary to Boolean data, syntactic constraints with interval patterns cannot be handled by a preprocessing step [10] because these constraints also affect the support for an interval pattern. Therefore, the task is harder for interval patterns. The remainder of this paper is organized as follows. Section 2 introduces the preliminaries and formalizes the constrained interval pattern sampling problem. Section 3 reviews related work on pattern sampling and their ability to incorporate constraints. Section 4 presents CFips, our approach for sampling interval patterns under constraints, and its theoretical properties. Section 5 describes the syntactic constraints supported by the method. Section 6 reports the exper-
Frequency-based Constrained Sampling for Interval Patterns
3
imental evaluation. Finally, Section 7 concludes the paper and outlines future research directions.
2
Preliminaries
2.1
Numerical Dataset
A numerical dataset N is defined by a set of objects G where each object is described by a set of attributes M. Each attribute m ∈ M has a range Nm which is a finite set containing all the values of the data occurring in attribute m. An object g ∈ G is defined by a vector of numerical values < vg ,m >∀m∈M . A dataset where the values of all attributes are binary Nm = {0, 1}, ∀m ∈ M, is a special case of a numerical dataset and referred as a binary dataset. Example 1. Table 1 shows a running example of a numerical dataset containing 5 objects G = {g1 , g2 , g3 , g4 , g5 }, each object is described by 3 attributes M = {m1 , m2 , m3 }.
g1 g2 g3 g4 g5
m1 m2 m3 2 8 130 4 12 102 3 7 91 2 9 101 6 12 110
Table 1: A running example of a numerical dataset N
2.2
Interval Patterns
Patterns in numerical datasets can be represented in many ways, we use the notion of Interval Pattern [8] to prevent the loss of information that occurs when data are converted into a binary representation [9]. An Interval Pattern is defined as a vector of intervals V = ⟨[am , bm ]⟩∀m∈M , where am , bm ∈ Nm and am ≤ bm . Each dimension of the vector V corresponds to an attribute following a canonical order on the set of attributes M. We denote B[g] = ⟨[vg ,m , vg ,m ]⟩∀m∈M as the vector of intervals corresponding to an object identified by g. An object g is an occurrence of the interval pattern V if each interval in the vector B[g] is included in the interval of V, i.e. B[g] ⊑ V ⇐⇒ [vg ,m , vg ,m ] ⊆ [am , bm ], ∀m ∈ M. The cover of V in N is the set of objects g ∈ G occurring in V, i.e. cover (V) = {g ∈ G | B[g] ⊑ V}. Example 2. In the example dataset of Table 1, V = ⟨[3, 4], [7, 12], [91, 130]⟩ is an interval pattern covering the objects {g2 , g3 }. B[g2 ]= ⟨[4, 4], [12, 12], [102, 102]⟩ is the vector of intervals identified by the object g2 and an occurrence of V.
4
D. Bekkoucha et al.
The frequency of V is the cardinality of its cover, i.e. freq(V) = |cover (V)|. Given a minimum frequency threshold θ, the interval pattern V is frequent if and only if freq(V) ≥ θ. The smallest description of a subset of objects G ⊆ G is the smallest interval pattern covering the set of objects G. Formally the smallest description of G is the interval pattern V such that for each g ∈ G, g is an occurrence of V, i.e. desc(G) = ⟨[am , bm ]⟩∀m∈M such that am = min({vg ,m | g ∈ G}) and bm = max({vg ,m | g ∈ G}). Let LV be the language of interval patterns, which corresponds to the set of all possible interval patterns. The size of the search space is the product of the total number of possible intervals for each attribute. Formally this is given by: m| Y |N X
m∈M k=1
k=
Y |Nm |(|Nm | + 1) 2
m∈M
Consider the database presented in Table 1. The total number of interval patterns in the search space is given by: 4×5 4×5 5×6 × × = 1500 interval patterns 2 } | {z 2 } | {z 2 } | {z m1
m2
m3
This example illustrates the rapid growth of the interval pattern search space. In practice, users are interested in patterns satisfying specific constraints, which define a small subspace of interest. Exhaustive extraction followed by postprocessing does not scale, and rejection-based sampling may lead to prohibitively high rejection rates. This motivates integrating constraints directly into pattern sampling procedure, enabling efficient exploration of the search space while ensuring that sampled patterns satisfy user-defined constraints.
2.3
Problem Statement
Let N be a numerical database and LV the language of interval patterns defined over N . Let q1 = {intervals of m1 containing a given value} and q2 = {intervals of m2 with lower bound greater than 12} be example constraints. We denote by Q = {qi ∧ . . . ∧ qn } a query corresponding to a conjunction of n constraints. We denote by LVQ ⊆ LV the set of interval patterns satisfying Q. Let f be an interestingness measure defined over LV . The constrained interval pattern sampling problem consists in sampling V1 , . . ., Vk ∈ LVQ independently with replacement according to a probability distribution proportional to f , without enumerating the constrained pattern space. In this work, we focus on frequency-based sampling and aim to push syntactic constraints directly into the sampling procedure while preserving exact sampling guarantees and avoiding rejection-based post-processing.
Frequency-based Constrained Sampling for Interval Patterns
3
5
Related Works
The literature on output-space pattern sampling can be broadly categorized into three families. Stochastic methods. These methods rely on random sampling procedures such as Markov chain Monte Carlo (MCMC) algorithms. Alhassan et al. [2] introduced this family for sampling graph patterns proportionally to their frequency. Boley et al. [11] extended these ideas to itemsets, considering positive interestingness measures. Bendimerad et al. [12] sampled tiles proportionally to a subjective interest measure. Despite their accuracy, slow convergence remains a common limitation. Declarative methods. In this family, combinatorial solvers are leveraged to sample patterns. Dzyuba et al. [4] pioneered SAT-based sampling of itemsets over multiple interestingness measures. Extending these methods to other pattern languages requires adapting the encoding for each language, limiting their applicability. Multi-step methods. Methods in this family perform sequential sampling by decomposing the interestingness measure across dataset objects. Boley et al. [3] proposed a two-step procedure that first draws an object from the dataset, then samples a pattern covering it. Diop et al. [5] extended this framework to three-step sampling for sequential patterns under maximum length constraints. Soulet [6] enforced minimum frequency constraints for itemsets, while Diop [7] sampled high average-utility itemsets under length constraints using a two-step procedure. Formal guarantees on the resulting sampling distribution are obtained when an appropriate decomposition of the interestingness measure is performed. Sampling patterns from numerical data. Numerical pattern sampling approaches remain limited. Giacometti et al. [13] sample neighborhood patterns in a continuous space according to a density measure. Bekkoucha et al. [14] introduced interval pattern sampling proportionally to measures such as frequency or frequency × hypervolume. Constraints in pattern sampling. The presented methods differ in their capacity to handle constraints. Stochastic methods enforce constraints via rejection or penalty mechanisms, which can severely slow convergence when constraints are highly restrictive. Declarative approaches allow straightforward incorporation of constraints, but scalability issues arise due to exhaustive solvers. Multi-step methods only handle a few types of constraints, such as length or frequency constraints [5, 7, 6]. Integrating other types requires problem-specific decompositions. To the best of our knowledge, existing approaches for numerical pattern sampling do not incorporate constraints directly into the sampling procedure. This motivates CFips, the first pattern sampling approach from numerical data to incorporate syntactic constraints while preserving exact sampling guarantees.
6
4
D. Bekkoucha et al.
Frequency-based Interval Pattern Sampling under Syntactic Constraints
This section introduces CFips, a method for sampling interval patterns proportionally to their frequency while satisfying a query Q, which is a conjunction of syntactic constraints.
4.1
CFips Key Ideas
A naive approach for sampling interval patterns satisfying a query Q proportionally to their frequency would consist in first mining all interval patterns, filtering through post-processing those that do not satisfy Q, and finally drawing the remaining patterns according to their associated frequency. However, due to the size of the interval pattern search space, this approach is impractical. Multi-step sampling procedures address the problem of sampling patterns according to a predefined probability distribution without enumerating the pattern space. These approaches sample patterns by traversing the database through its objects rather than exploring the entire pattern space. They rely on decomposing the chosen interestingness measure into a sum of utilities defined over the objects of the database [15]. This decomposition enables a successive sampling procedure in which an object is first drawn according to its weight, and a pattern covering this object is then sampled according to its utility for this object. The combination of these successive steps then leads to samples that follow the targeted distribution. However, these approaches do not provide a direct way to incorporate constraints into the sampling procedure. Our idea is to incorporate directly into the utility function the constraints of Q. In CFips, patterns violating at least one constraint are assigned zero utility and therefore cannot be sampled. Formally, for an interval pattern V ∈ LV and an object g ∈ N , the constrained utility function is defined as: ( u(V, g, Q) =
1 if g ∈ cover N (V) and V satisfies Q, 0 otherwise.
This formulation ensures that patterns violating at least one constraint in Q contribute neither to object weights nor to the sampling probability. Consequently, constraints are enforced implicitly through the utility function, without requiring rejection-based sampling. The frequency measure can be decomposed as a sum over the objects of the database [3]. This decomposition relies on a counting function that computes the number of interval patterns covering a given object while satisfying the query Q. Building on this principle, we introduce N IPQ , a decomposition of the frequency measure into object utilities designed to handle constraints in a numerical setting.
Frequency-based Constrained Sampling for Interval Patterns
4.2
7
Counting Valid Interval Patterns Under Syntactic Constraints
To sample patterns that satisfy a query Q composed of syntactic constraints proportionally to their frequency, we restrict the computation of frequency-based P weights to valid patterns LVQ (i.e. V∈LVQ freq(V, N )). To avoid an explicit enumeration of this constrained pattern space, we follow the principle of the NIP function proposed in [14]. We define the counting function N IPQ : g 7→ N, which directly incorporates constraints in the counting function and returns, for each object g ∈ G, the exact number of interval patterns satisfying the constraints Q and covering g. To incorporate c into N IPQ , c is decomposed into two predicates PvLgc,m and PvJgc,m : the first filters candidate lower bounds LQ (vg ,m ), the second candidate upper bounds JQ (vg ,m ). Formally, N IPQ is defined as: Y N IPQ (g) = |LQ (vg ,m )| · |JQ (vg ,m )| (1) m∈M
where: o n V|Q| Lci – LQ (vg ,m ) = v ∈ Nm | v ≤ vg ,m i=1 Pvg ,m (v) denotes the set of admissible values according to Q that can serve as lower bounds. Each predicate L ci (v) checks whether value v satisfies constraint ci when considered as a Pvg ,m lower bound.n o V|Q| Jci – JQ (vg ,m ) = v ∈ Nm | v ≥ vg ,m i=1 Pvg ,m (v) denotes the set of admissible values according to Q that can serve as upper bounds. Each predicate J ci Pvg ,m (v) checks whether value v satisfies constraint ci when considered as an upper bound. For each attribute m, Equation 1 evaluates the number of admissible lower bounds and upper bounds for an interval containing the value vg ,m . The product of these two terms gives the number of valid intervals on m containing vg ,m and satisfying Q. By multiplying the results across all attributes, N IPQ (g) returns the total number of interval patterns covering g while satisfying all syntactic constraints in Q. A particularly interesting result is that N IPQ identifies situations in which no pattern satisfies Q: if N IPQ (g) = 0 for all g ∈ G, then the constrained pattern space LVQ is empty. This property allows CFips to immediately report that no interval pattern satisfying Q exists and thus the sampling can be stopped contrary to rejection-based strategies that would endlessly try to draw patterns. Example 3. Consider a numerical database N , object g3 ∈ G, attribute m1 ∈ M 1 (see Table 1), and a query Q = {Incm 6 } requiring that every pattern include the value 6 in the interval associated with attribute m1 . The value of m1 for g3 is 3. The valid intervals containing 3 and satisfying 1 Incm are [2, 6] and [3, 6], i.e., two intervals in total. Hence, for m1 : 6 LQ (3) = {2, 3}
and
JQ (3) = {6}
8
D. Bekkoucha et al.
These sets are obtained by incorporating the predicates associated with the constraint into each term: LIncm1
Pvg ,m 6 (v) : m = m1 ∧ 6 ≤ vg ,m ⇒ v ≤ 6 JIncm1
Pvg ,m 6 (v) : m = m1 ∧ 6 ≥ vg ,m ⇒ v ≥ 6 A value v is a valid lower bound LQ (3) if it is less than or equal to the object’s LIncm1
value 3 for m1 and satisfies Pvg ,m 6 (v). Here, 6 ≤ 3 is false, so the predicate’s premise does not apply, and the predicate is always true. The valid lower bounds are thus determined solely by v ≤ 3 in Nm1 , i.e., {2, 3}. For upper bounds, a value v is admissible JQ (3) if it is greater than or equal JIncm1
to 3 and satisfies Pvg ,m 6 (v). Since 6 ≥ 3 holds, the predicate enforces v ≥ 6, restricting valid upper bounds to {6}. Thus, |LQ (3)| × |JQ (3)| = 2 × 1 = 2. Attributes m2 and m3 are unconstrained, admitting 4 and 5 valid intervals respectively. The total number of interval patterns covering g3 and satisfying Q is: N IPQ (g3 ) = 2 × 4 × 5 = 40 4.3
CFips Sampling Algorithm
We now describe the CFips sampling procedure (see Algorithm 1). The algorithm begins by determining the number of interval patterns satisfying the constraints in Q that cover each object in the numerical database N (line 5). This step relies on the N IPQ function (Section 4.2). Line 8 implements the first step of the two-step sampling procedure: an object g is drawn with probability proportional to the number of interval patterns covering it and satisfying Q. The draw is therefore biased towards objects covered by a high number of patterns respecting the query constraints. In the second step (line 11), an interval pattern satisfying all constraints in Q and covering at least the selected object g is drawn uniformly. Specifically, for each attribute m ∈ M, two values am and bm are drawn uniformly from LQ (vg ,m ) (admissible lower values) and JQ (vg ,m ) (admissible upper values), respectively. These values form the bounds of the interval associated with attribute m in the sampled pattern. A sample of k patterns is obtained by executing k times Algorithm 1. In the next section, we show that CFips draws patterns proportionally to their frequency. 4.4
CFips Sampling Distribution
We show that interval patterns produced by CFips are sampled proportionally to their frequency.
Frequency-based Constrained Sampling for Interval Patterns
9
Algorithm 1: Interval pattern sampling proportional to frequency under syntactic constraints (CFips) 1 2
Input: numerical database N ; conjunction of syntactic constraints Q ; Output: a valid interval pattern V ∗ satisfying Q, sampled proportionally to its frequency;
4 5
Preprocessing: compute wF (g) = N IPQ (g) for each object g ∈ G ;
7 8
Step 1: g ∼ wF (g) wF
;
// Draw object g proportionally to its weight
10
Step 2: ; /* Draw uniformly an interval pattern V ∗ covering g and satisfying Q */ ∗ 12 V ←− ⟨⟩ ; // Interval pattern under construction 13 foreach attribute m ∈ M do 14 am ←− uniformly draw a value from LQ (vg ,m ); 15 bm ←− uniformly draw a value from JQ (vg ,m ); 16 V ∗ ←− V ∗ + +[am , bm ];
11
18 19
Return V ∗ ;
Property 1. For a numerical database N , Algorithm 1 draws each interval pattern V with probability proportional to its frequency among patterns satisfying each constraint from the query Q. Proof. Let LVQ ⊆ LV beP the subspace of all interval patterns satisfying the user query Q, and let Z = V∈LVQ |cover (V, N )| be the normalization constant, representing the sum of the frequencies of all interval patterns in LVQ . Let g ∗ ∈ G be an object drawn randomly in Step 1 of Algorithm 1, and let V ∗ be an interval pattern drawn in Step 2 of the same algorithm. We then have:
P [V ∗ = V] =
X
P [V ∗ = V ∧ g ∗ = g]
g∈G
=
X g∈cover (V,N )
=
X g∈cover (V,N )
1 N IPQ (g) · N IPQ (g) Z 1 |cover (V, N )| f req(V, N ) = = Z Z Z
P P where Z = g∈G N IPQ (g), which is equal to Z = V∈LVQ |cover (V, N )|, since each interval pattern contributes once for each object in its cover.
10
4.5
D. Bekkoucha et al.
Time Complexity Analysis of CFips
We analyze the time complexity of CFips, including the preprocessing phase and the sampling procedure. Property 2. The overall time complexity of CFips for sampling a single interval pattern is: O(|G|2 · |M| · γ + (log |G| + |M|)) where γ is the worst-case complexity of evaluating the predicates associated with syntactic constraints over all distinct values. Proof. Let N be a numerical database with |G| objects and |M| attributes. In the worst case, each attribute contains |G| distinct values, and each value participates in an unbounded number of constraints. The preprocessing complexity relies on the N IPQ function applied to each object g ∈ G. For each attribute m ∈ M and each distinct value vg ,m appearing in g, the sets LQ (vg ,m ) and JQ (vg ,m ) are constructed by filtering admissible bounds using the predicates defined by the syntactic constraints. Let γ denote the worst-case complexity of evaluating all predicates for a value. The cost of constructing each set is O(|G|2 · |M| · γ). Sampling a pattern with Algorithm 1 is done in two steps. The first draws an object proportionally to its weight using a binary search of complexity O(log |G|). The second draws a pattern covering this object uniformly from LQ (vg ,m ) and JQ (vg ,m ) in O(|M|). Thus, the overall complexity for sampling a single pattern (including preprocessing) is: O(|G|2 · |M| · γ + log |G| + |M|). To sample k interval patterns, the preprocessing is performed once, and each draw costs O(log |G| + |M|). Therefore, the total complexity is: O(|G|2 · |M| · γ + k(log |G| + |M|)).
5
Examples of Admissible Constraints
We illustrate examples of admissible syntactic constraints in CFips. These constraints can be expressed as independent predicates on the lower and upper bounds of interval patterns, making them directly integrable into the sampling procedure. Table 2 provides a set of syntactic constraints that can be incorporated into the interval pattern sampling procedure. A user can specify a conjunction of these constraints in a query to sample patterns according to its interest. To enable integration of these constraints in CFips, they are decomposed into elementary predicates applied to each bound, as detailed in Table 3. Time complexity to evaluate each syntactic constraint. All predicates composing the constraints in Table 3 can be evaluated in constant time, O(1),
Frequency-based Constrained Sampling for Interval Patterns Constraint Description
11
Formal Definition
′ Inclusion: ensures that a value v ′ ∈ Nm is included in Incm v ′ (V) ≡ am ≤ v ≤ bm with am , bm ∈ Nm the interval [am , bm ] associated with attribute m. ′ Exclusion: ensures that a value v ′ ∈ Nm is excluded Excm < am ) ∨ (bm < v ′ ) with v ′ (V) ≡ (v from the interval [am , bm ] associated with attribute m. am , bm ∈ Nm ′ Strictly greater than: ensures that the interval Supm v ′ (V) ≡ v < am ≤ bm with am , bm ∈ Nm [am , bm ] associated with attribute m is strictly greater than a value v ′ ∈ Nm .
Greater than or equal: ensures that the interval SupEqvm′ (V) ≡ v ′ ≤ am ≤ bm with am , bm ∈ [am , bm ] associated with attribute m is greater than or Nm equal to a value v ′ ∈ Nm . Strictly less than: ensures that the interval [am , bm ] Infvm′ (V) ≡ am ≤ bm < v ′ with am , bm ∈ Nm associated with attribute m is strictly less than a value v ′ ∈ Nm . Less than or equal: ensures that the interval [am , bm ] Inf Eqvm′ (V) ≡ am ≤ bm ≤ v ′ with am , bm ∈ associated with attribute m is less than or equal to a Nm value v ′ ∈ Nm .
Table 2: Examples of syntactic constraints defined over interval patterns
since they rely only on simple comparisons between the value vg ,m , the distinct value under consideration v ∈ Nm , and constants defined in the query (m and m′ ). Therefore, the total cost to construct the sets LQ (vg ,m ) and JQ (vg ,m ) is linear in the number of distinct values, which, in the worst case, is O(|G|).
6
Experimental Evaluation
In this section, we evaluate the efficiency of CFips compared to classical sampling approaches followed by rejection-based post-processing to discard patterns that do not satisfy the constraints. We address the following resarch questions: 1. What is the rejection rate observed for classical sampling approaches combined with post-processing which rejects patterns that do not satisfy the constraints to obtain the exact number of valid patterns for a query Q? 2. In terms of computational time, how efficient is CFips compared to classical sampling approaches relying on post-processing to reject invalid patterns? 6.1
Experimental Protocol
Compared approaches. We compare CFips with Fips and Uniform. The two latter approaches were proposed in [14] for the interval pattern language.
12
D. Bekkoucha et al.
Constraint
Term
Predicates L
′ Incm′
LQ (vg ,m ) Pvg ,m v (v) : m = m′ ∧ v ′ ≤ vg ,m ⇒ v ≤ v ′
′
Inclusion (Incm v ′ (v))
J
′ Incm′
JQ (vg ,m ) Pvg ,mv (v) : m = m′ ∧ v ′ ≥ vg ,m ⇒ v ≥ v ′ L
′ Excm′
LQ (vg ,m ) Pvg ,m v (v) : m = m′ ∧ v ′ ≤ vg ,m ⇒ v > v ′
′ Exclusion (Excm v ′ (v))
J
′ Excm′
JQ (vg ,m ) Pvg ,m v (v) : m = m′ ∧ v ′ ≥ vg ,m ⇒ v < v ′ L ′
Strictly greater than (Supm v ′ (v))
′ Supm′
LQ (vg ,m ) Pvg ,m v (v) : m = m′ ⇒ v > v ′ J
′ Supm′
JQ (vg ,m ) Pvg ,m v (v) : m = m′ ⇒ ⊤ L ′
Greater or equal (SupEqvm′ (v))
′ SupEQm′ v
LQ (vg ,m ) Pvg ,m
′ SupEQm′ v vg ,m
JQ (vg ,m ) P
J ′ Strictly less than (Infvm′ (v))
(v) : m = m′ ⇒ v ≥ v ′
J
(v) : m = m′ ⇒ ⊤
′ Inf m′
LQ (vg ,m ) Pvg ,m v (v) : m = m′ ⇒ ⊤ L
Inf m′
′
JQ (vg ,m ) Pvg ,m v (v) : m = m′ ⇒ v < v ′ J ′
Less or equal (Inf Eqvm′ (v))
′ Inf EQm′ v
LQ (vg ,m ) Pvg ,m
(v) : m = m′ ⇒ ⊤
L
′ Inf EQm′ v vg ,m
JQ (vg ,m ) P
(v) : m = m′ ⇒ v ≤ v ′
Table 3: Instantiation of predicates corresponding to the constraints presented in Table 2.
Fips samples interval patterns proportionally to their frequency, while Uniform samples interval patterns uniformly. As both methods do not handle constraints, a post-processing step is required to check whether the sampled patterns satisfy the constraints specified in the query Q. This post-processing step consists in testing each sampled pattern against Q: if the pattern satisfies the constraints, it is retained; otherwise, it is rejected. The sampling process is repeated until the required number of valid patterns is obtained. Datasets. The experimental evaluation is conducted on five numerical datasets: cancer, diabetes, glass, AP, and NT. Their characteristics are reported in Table 4. Constraint generation. For each dataset, a set of ten constraints is generated according to a protocol designed to simulate user behavior. An attribute m is first drawn uniformly at random. If the number of distinct values |Wm | exceeds five, we assume that the user is interested in intervals located above or below a given threshold. In this case, a constraint is drawn uniformly from the set {“greater than v”, “less than v”, “greater than or equal to v”, “less than or equal to v”}, where v ∈ Wm . If the attribute m contains at most five distinct values, we assume that the user wishes to explicitly enforce or forbid the presence of certain values due to
Frequency-based Constrained Sampling for Interval Patterns
13
NT AP Cancer Glass Diabetes |M| 3 5 9 9 8 |G| 130 135 116 214 768 |Distinct values| 67 674 900 939 1254
Table 4: Dataset characteristics |M| denotes the number of attributes, |G| the number of objects, and |Distinct values| the total number of distinct values across all attributes.
their semantic importance in the application domain. In this case, the constraint is chosen uniformly between {“inclusion”, “exclusion”}. Finally, experiments are conducted by progressively adding constraints. The experiment starts with a single constraint; then a second constraint is added and the experiment is repeated with these two constraints. This process continues until all ten constraints are included. For each constraint set and each approach, 100 interval patterns are sampled. A time limit of two minutes is imposed for each run. Both computation time and rejection rate are averaged over ten repetitions. The source code, the datasets and the experimental results are available at https://anonymous.4open.science/r/Constraint-Based-Sampling-6B83 6.2
Rejection Rate Evaluation
This section addresses Question 1, regarding the rejection rate observed for Fips and Uniform methods. This rate corresponds to the proportion of sampled patterns that are invalid with respect to the query Q. Formally: |K| × 100, Rejection rate = 1 − NumberDraws where |K| denotes the required number of patterns (fixed to 100 in our experiments), and NumberDraws is the total number of draws needed to obtain |K| patterns satisfying all constraints of the query Q. As presented on the right-hand side of Figure 1, Fips produces the required 100 patterns for up to 4 constraints on the diabetes database, 5 on cancer, and 6 on glass. However, the rejection rates are high, particularly on cancer and diabetes, with values ranging from 65.80% to 99.98%. Beyond these thresholds, the method fails to generate the required number of patterns within the allocated time. An exception is observed for AP, where Fips succeeds in sampling 100 patterns satisfying Q even with up to 10 constraints. Nevertheless, the rejection rate still substantially increases with the number of constraints, rising from 74.12% with 2 constraints to 99.88% with 10. This can be explained by the interestingness measure of Fips, which tend to sample frequent patterns. This bias leads to producing patterns whose intervals contain a large number of distinct values, thus increasing the probability of including values that do not satisfy the constraints in Q.
14
D. Bekkoucha et al.
Uniform generally presents lower rejection rates than Fips, but still suffers from substantial rejection rates, from 23% to 99% on glass, from 53% to 99% on cancer, from 85% to 99% on diabetes, and from 54% to 97% on AP. For the latter database, Uniform is able to generate the 100 required patterns regardless of the number of constraints. This behavior can be explained by the fact that Uniform tends to produce lower-frequency patterns [14], with smaller intervals that are therefore less likely to violate the constraints in Q. 6.3
CPU Times Evaluation
In this section, we address Question 2, which concerns the CPU time required to sample the desired number of patterns satisfying the constraints of the query Q. We compare CFips with Fips and Uniform. As presented on the left-hand side of Figure 1, for queries containing one to two constraints, the CPU times of Fips and Uniform are sometimes lower than those of CFips, in particular on the AP and glass databases. However, as the number of constraints increases, the CPU time of CFips remains constant and becomes significantly lower than the CPU time of Fips and Uniform, for which computation times grow substantially due to the increasing rejection rate. From four or five constraints upward, Fips and Uniform are no longer able to sample the required number of patterns within the allocated time, indicating a substantial increase in the number of rejected patterns. In an interactive context, these methods would not return solutions to an analyst within the allocated time. Generally, Fips has the highest CPU times. This can be explained by its bias toward frequent patterns, which is more likely to violate the constraints in Q. This results in higher rejection rates and, consequently, longer computation times. Note that interestingness measures affect the rejection rate in a constraintdependent manner. Fips, which samples patterns according to frequency, produces wide intervals, which are more likely to include forbidden values and therefore violate exclusion-type constraints, while it can better satisfy inclusion-type constraints. Conversely, Uniform samples patterns uniformly, producing narrow intervals across diverse regions of the search space [14]; this reduces violations for exclusion constraints but may increase rejections for inclusion constraints, as it is less likely that the required values fall within the sampled intervals. By integrating constraints directly into the sampling procedure, CFips avoids these edge effects entirely.
7
Conclusion and Perspectives
In this paper, we presented CFips, the first constrained output-space interval pattern sampling approach from numerical data. CFips samples interval patterns proportional to their frequency while ensuring their validity with respect to a conjunction of constraints Q. Through N IPQ , we illustrated how constraints can be incorporated directly into the sampling procedure by decomposing them
Frequency-based Constrained Sampling for Interval Patterns Constraints number 1 2 3 4 5 6 7 8 9 10
15
Fips Uniform 9.50 23.13 17.89 28.05 95.63 90.71 96.79 92.59 96.82 92.77 99.97 99.89 TO TO TO TO TO TO TO TO
Rejection rate (%) — glass Constraints number 1 2 3 4 5 6 7 8 9 10
Fips Uniform 65.80 53.66 99.69 97.96 99.93 99.38 99.98 99.75 99.98 99.74 TO 99.91 TO TO TO TO TO TO TO TO
Rejection rate (%) — cancer Constraints number 1 2 3 4 5 6 7 8 9 10
Fips Uniform 95.03 85.72 98.02 91.64 98.63 93.96 99.81 98.60 TO 99.85 TO TO TO TO TO TO TO TO TO TO
Rejection rate (%) — diabetes Constraints number 1 2 3 4 5 6 7 8 9 10
Fips Uniform 0 0 74.12 54.87 89.21 73.62 93.24 78.19 93.90 79.18 97.50 87.22 97.51 87.60 97.52 87.35 98.05 89.11 99.88 97.92
Rejection rate (%) — AP
Fig. 1: Evaluation of CPU times and rejection rates for the CFips, Fips, and Uniform
16
D. Bekkoucha et al.
into independent predicates, ensuring that patterns are drawn according to the desired distribution in the constrained search space. Consequently, CFips can instantly indicate the absence of a solution, meaning the analyst does not have to wait. We theoretically proved that CFips samples patterns proportionally to their frequency in the constrained pattern space and experimentally demonstrated its advantages over post-processing rejection strategies. This work opens several research directions. A first direction is the integration of CFips into interactive pattern mining settings, where it could quickly return patterns matching an analyst’s preferences. Another direction is to extend the range of constraints supported by CFips. The current approach handles syntactic constraints that can be decomposed into elementary predicates on interval bounds. Extending it to more complex constraints, such as frequency thresholds or hypervolume, which cannot be easily decomposed, remains an open challenge. Finally, investigating additional interestingness measures for numerical data, such as density, constitutes another promising direction.
References 1. M. van Leeuwen, Interactive data exploration using pattern mining, in: Interactive Knowledge Discovery and Data Mining in Biomedical Informatics - State-of-theArt and Future Challenges, 2014. doi:10.1007/978-3-662-43968-59. 2. M. Al Hasan, M. J. Zaki, Output space sampling for graph patterns, Proc. VLDB Endow. 2 (1) (2009) 730–741. doi:10.14778/1687627.1687710. 3. M. Boley, C. Lucchese, D. Paurat, T. Gärtner, Direct local pattern sampling by efficient two-step random procedures, in: ACM SIGKDD, 2011, pp. 582–590. doi:10.1145/2020408.2020500. 4. V. Dzyuba, M. van Leeuwen, L. D. Raedt, Flexible constrained sampling with guarantees for pattern mining, Data Min. Knowl. Discov. 31 (5) (2017) 1266–1293. doi:10.1007/S10618-017-0501-6. 5. L. Diop, C. T. Diop, A. Giacometti, D. Li, A. Soulet, Sequential pattern sampling with norm-based utility, Knowl. Inf. Syst. (2020). 6. A. Soulet, Echantillonnage de motifs avec une contrainte de fréquence, in: EGC 2023, Lyon, France, 2023. 7. L. Diop, High average-utility itemset sampling under length constraints, in: 26th Pacific-Asia Conference, PAKDD, 2022. doi:10.1007/978-3-031-05936-0_11. 8. M. Kaytoue, S. O. Kuznetsov, A. Napoli, Revisiting numerical pattern mining with formal concept analysis, in: IJCAI 2011, 2011. doi:10.5591/978-1-57735-5168/IJCAI11-227. 9. J. Dougherty, R. Kohavi, M. Sahami, Supervised and unsupervised discretization of continuous features, in: Proceedings of the twelfth international conference on Machine Learning, Morgan Kaufmann, 1995, pp. 194–202. 10. F. Bonchi, F. Giannotti, A. Mazzanti, D. Pedreschi, Exante: Anticipated data reduction in constrained pattern mining, in: PKDD 2003, 7th European Conf. on Principles and Practice of Knowledge Discovery in Databases, Cavtat-Dubrovnik, Croatia, Vol. 2838, Springer, 2003, pp. 59–70. doi:10.1007/978-3-540-39804-2_8. 11. M. Boley, T. Gärtner, H. Grosskreutz, Formal concept sampling for counting and threshold-free local pattern mining, in: SDM 2010, USA, 2010.
Frequency-based Constrained Sampling for Interval Patterns
17
12. A. Bendimerad, J. Lijffijt, M. Plantevit, C. Robardet, T. De Bie, Gibbs sampling subjectively interesting tiles, in: IDA 2020, Germany„ 2020. 13. A. Giacometti, A. Soulet, Dense neighborhood pattern sampling in numerical data, in: SDM 2018 USA, 2018. 14. D. Bekkoucha, L. Diop, A. Ouali, B. Crémilleux, P. Boizumault, Efficiently sampling interval patterns from numerical databases, Data & Knowledge Engineering 163 (2026) 102566. doi:https://doi.org/10.1016/j.datak.2026.102566. 15. L. Diop, Echantillonnage sous contraintes de motifs structures. (constrained sampling of structured patterns), Ph.D. thesis (2020). URL https://tel.archives-ouvertes.fr/tel-02948509