Exact Mining of Dense Patterns via Direct Evaluation of Local Interval Frequency Using a Sliding Window
arXiv:2604.24122v1 [cs.DB] 27 Apr 2026
Taihei Takahashi1
Kanata Takayasu1 Satoshi Kurihara1
1 Keio University
Satoshi Suga2
2 Kansai University
Abstract Accurately extracting patterns that appear frequently only within specific time intervals, together with their dense intervals, is important in many applications such as understanding seasonal demand and detecting anomalous behavior. Frequent itemset mining evaluates support over the entire dataset and therefore cannot detect locally dense patterns. Existing methods for dense pattern mining with interval output estimate dense intervals through occurrence-gap constraints; however, since the gap constraint parameter governs both pattern identification accuracy and interval detection accuracy simultaneously, finding a parameter setting that achieves high accuracy for both objectives is difficult. In this paper, we propose Apriori-window, an exact algorithm that resolves this structural limitation. The proposed method directly evaluates local frequency within a sliding window and thus requires no gap constraint parameter, and it efficiently enumerates dense intervals through anti-monotonicity-based pruning of the search space and stride-skip reduction of the number of window scans. Experiments on three real-world datasets demonstrate that existing methods struggle to simultaneously achieve high accuracy in both pattern identification and dense interval detection, and scalability experiments on synthetic data confirm the practical applicability of the proposed method.
Keywords: dense pattern mining, frequent pattern mining, time series
1
Introduction
In diverse domains including retail, healthcare, and cybersecurity, large volumes of data are accumulated daily. The content recorded in such data varies over time due to trends, seasonal fluctuations, and the influence of external events. Extracting temporal characteristics from such data is important for understanding the nature of the data. Pattern mining encompasses numerous methods for extracting useful information from data. Frequent itemset mining (FIM) [1–3] is a representative approach in pattern mining that extracts combinations of items appearing frequently across the entire dataset as patterns. However, since this approach evaluates support over the entire dataset, it cannot account for locally varying occurrence frequencies. As a result, setting the minimum
1
support threshold high causes patterns that are densely concentrated within limited intervals to be excluded, while setting it low causes many non-dense patterns to be extracted alongside the dense ones. This dilemma is known as the rare item problem [7]. To address this problem, methods that simultaneously extract dense patterns—itemsets that exhibit high occurrence frequency only within specific intervals—together with their dense intervals have been proposed. LPFIM [34], LPPM [35], and RPM [36] all estimate dense intervals through occurrence-gap-based parameters, outputting patterns and their intervals simultaneously. However, in these methods the occurrence-gap parameter governs both pattern identification accuracy and interval detection accuracy, making it extremely difficult to find a parameter setting that maintains both at a high level simultaneously. In this paper, we propose Apriori-window, an exact algorithm that overcomes this limitation. The proposed method evaluates local frequency by directly counting occurrences within a sliding window, requiring no gap threshold and thus avoiding the parameter sensitivity problem. Combining anti-monotonicity-based pruning of pattern candidates and candidate intervals with stride adjustment, the method achieves comprehensive and exact extraction in practical execution time. This paper addresses the following research questions: RQ1 Is it possible to develop an exact algorithm that precisely identifies dense patterns and detects their dense intervals? RQ2 Can existing methods accurately identify dense patterns and detect their dense intervals? RQ3 How do the execution time and memory usage of the exact dense pattern algorithm scale with data characteristics? The main contributions of this paper are as follows: 1. We propose Apriori-window, an exact algorithm based on direct evaluation of local frequency via a sliding window. We prove the safety of the anti-monotonicity and the stride-skip mechanism, establishing the exactness of the extraction results (RQ1). 2. Through parameter grid search of existing methods on three real-world datasets, we demonstrate that existing methods struggle to simultaneously achieve high accuracy in both dense pattern identification and dense interval detection (RQ2). 3. Scalability experiments on synthetic data quantify the growth of execution time and memory usage with respect to data characteristics, confirming the practical applicability of the proposed method (RQ3).
2
Related Work
2.1
Frequent Itemset Mining
Frequent itemset mining (FIM) is the task of discovering itemsets whose support over the entire dataset meets a user-specified threshold [41]. Apriori [1] introduced a candidategeneration and pruning framework exploiting anti-monotonicity; ECLAT [2] improved 2
efficiency through a vertical data representation; and FP-Growth [3] achieved further speedup via a compressed tree structure that eliminates candidate generation. Surveys of these foundational methods and their extensions appear in [4–6]. Extensions of the FIM framework include high-utility itemset mining [8, 9], which replaces frequency with utility values such as profit. To improve computational efficiency or pattern quality, various approaches have also been proposed: direct rule extraction using autoencoders [10, 11], discovery of low-redundancy pattern sets via binarized neural networks [12], adaptive search using reinforcement learning [13], extraction of sequential and high-utility patterns via deep learning [14, 15], and approximate search using evolutionary computation [16, 17]. Since all of these methods evaluate support over the entire dataset, they cannot detect itemsets that occur at high frequency only within specific time intervals. Patterns that are globally infrequent but locally frequent are missed when the minimum support threshold is set high, and when it is set low, a large number of non-dense patterns are extracted alongside them (the rare item problem [7]). Deep learning-based methods contribute to scalability and rule-count reduction; however, their support evaluation framework is identical to that of FIM, and approximate results based on latent representations do not guarantee exhaustive and exact extraction.
2.2
Pattern Mining Considering Temporal Information
Several methods have been proposed that account for changes in frequency along the time axis rather than evaluating frequency over the entire dataset. TP-Mine [18] handles transitional patterns, detecting time points at which frequency changes dramatically; however, its output is change points rather than intervals. SPF [19] computes frequency normalized by the exhibition period of each item, providing comparable support across the same item. PPM [20] is a temporally correlated rule mining method that evaluates support for each interval partitioned at a fixed calendar granularity; while useful for capturing temporal changes in patterns, intervals are fixed to calendar granularity. Burst detection [21, 22] identifies intervals in which the occurrence frequency of a single event surges; although it shares with dense patterns the motivation of detecting frequency concentration within specific intervals, it differs from our work in that it does not involve combinatorial search over itemsets. In the field of periodic pattern mining, Periodic-Frequent Patterns (PFPs) [23–27] have been proposed. These methods output itemsets satisfying both Sup(X) ≥ minSup and Per (X) ≤ maxPer , where the maximum period Per (X) = maxi pi and p1 , p2 , . . . is the sequence of occurrence gaps of itemset X. Since maxPer acts as an upper bound on all occurrence gaps, smaller values require stricter periodicity; a single large gap causes the entire itemset to be rejected, making these methods susceptible to noise. Partial PeriodicFrequent Patterns (PPFPs) [28] relax this constraint and define qualifying itemsets as those with PR(X) = |{pi ≤ maxPer }|/(|Sup(X)| + 1) ≥ minPR. The parameter minPR controls the required fraction of occurrence gaps that lie within maxPer ; lowering it allows detection of patterns with irregular periodicity. However, both methods output only patterns and do not explicitly output dense intervals. Episode mining [29] handles sequential patterns that involve temporal relationships among multiple events, capturing periodicity based on event occurrence frequency, but differs from our problem setting of simultaneously outputting itemsets and their dense intervals. Emerging pattern mining [30] discovers patterns whose support changes substantially before and after a shift in data distribution, but does not produce dense interval 3
output.
2.3
Methods That Output Patterns and Their Dense Intervals
For dense pattern extraction, it is important to output not only the patterns but also the intervals in which they are dense. Existing methods that extract intervals can be broadly categorized into those that directly compute local frequency and those based on occurrence-gap constraints. As a direct local frequency approach, GLFMiner [31] automatically extracts locally frequent patterns and their intervals, but the intervals are fixed to integer multiples of a predefined temporal granularity, precluding data-driven flexible interval detection. SIM [32, 33] outputs the optimal single period for each itemset that satisfies a frequency condition. Although its motivation is similar to dense patterns, it differs from our problem setting of comprehensively enumerating dense intervals in that it outputs a single optimal period per itemset and imposes no minimum interval length constraint. As occurrence-gap-based approaches, LPFIM [34] extracts locally and periodically frequent itemsets with their intervals. For an itemset X, a new interval is started when the gap between occurrences reaches minthd1 ; intervals satisfying local support Sup [t1 ,t2 ] (X)/tc [t1 ,t2 ] ≥ σ and interval length ≥ minthd2 are output (where tc is the number of transactions in the interval). The parameter minthd1 determines the interval segmentation granularity, and minthd2 removes intervals that are too short. LPPM [35] achieves noise-robust interval detection by introducing cumulative spillover against the gap constraint. The spillover at occurrence timestamp tsi is surPer (tsi ) = interval (tsi ) − maxPer , accumulated as soPer (tsi ) = max(0, soPer (tsi−1 ) + surPer (tsi )); the interval is terminated when this exceeds maxSoPer . Intervals of length ≥ minDur are output together with patterns. The parameter maxPer controls the upper bound on acceptable occurrence gaps, maxSoPer controls the total permissible excess, and minDur controls the minimum interval length. RPM [36] partitions intervals where the occurrence gap is at most maxPer into periodic intervals, and outputs itemsets for which the number of periodic intervals containing at least minPS consecutive occurrences is at least minRec. The parameter maxPer controls the upper bound on gaps considered periodic, minPS controls the minimum number of consecutive occurrences within one interval, and minRec controls the minimum number of periodic intervals. These methods are the most closely related prior work to ours in that they output both patterns and their associated intervals. Table 1 compares the pattern definitions of each method with the dense pattern definition of this work. In contrast to Apriori-window, which directly evaluates the occurrence count within a window, existing methods indirectly estimate density through parameters such as gap constraints, cumulative spillover, and periodicity thresholds.
2.4
Evaluation of Local Frequency via Sliding Window
Sliding windows [37, 38] have been employed in stream mining [40] and change point detection in time series [39]. In stream mining, windows serve as a framework for limiting the temporal scope of data analysis as new data arrive online; in change point detection, they are used as a means of detecting local statistical changes in data.
4
Table 1: Comparison of pattern definitions across methods. Pattern Name
Pattern Condition
Dense Interval Detection
Output
• Sup(X) ≥ minSup: lower bound Does not output intervals on total occurrence count • Per (X) = maxi pi ≤ maxPer : upper bound on the maximum gap between consecutive occurrences Partial Periodic- • Sup(X) ≥ minSup: lower bound Does not output intervals Frequent Pattern on total occurrence count • PR(X) ≥ minPR: lower bound on the fraction of occurrence gaps that are at most maxPer
P only
Periodic-Frequent Pattern
P only
Locally and Periodi- • Sup [t1 ,t2 ] (X)/tc ≥ σℓ : lower Partitions an interval when P + interval cally Frequent Item- bound on local support rate within the occurrence gap reaches list set [t1 , t2 ] (tc : interval length) minthd1 • tc ≥ minthd2 : minimum interval length Local Periodic Pat- • spillover [t1 ,t2 ] ≤ maxSoPer : up- Terminates an interval when P + interval tern per bound on the cumulative sur- the cumulative surplus ex- list plus of occurrence gaps exceeding ceeds maxSoPer maxPer • tc ≥ minDur : minimum interval length Recurring Pattern
Dense (Ours)
• rec(X) ≥ minRec: lower bound Groups consecutive occur- P + interval on the number of detected recurring rences with gaps at most list maxPer into a single interval intervals • ps(X) ≥ minPS : lower bound on occurrence density within each recurring interval
Pattern • sup(P, l, W ) ≥ σ: lower bound on Determines whether the fre- P + interval direct occurrence count in window quency condition is satisfied list [l, l+W ] within a sliding window
The essence of dense patterns is that a given itemset occurs locally at high frequency within a specific consecutive interval. In this work, we introduce the evaluation of local frequency within consecutive intervals using a sliding window. By directly computing the occurrence frequency within the window as it moves, we can assess local density without relying on occurrence-gap constraints, thereby avoiding the parameter sensitivity problem in principle. This idea is similar in spirit to related work on change point detection. However, within our survey, we could not identify any prior work whose primary objective is the comprehensive extraction of itemsets and their dense intervals by combining direct local frequency evaluation via a sliding window with the anti-monotonicity of Apriori. This work is an attempt to formulate and implement this direction as an algorithm.
5
Table 2: Transaction database D used in running examples. Timestamp t 1 3 5 7 9 20 22 25
3
Problem Definition
3.1
Basic Definitions
Transaction Tt {a, b} {a, b, c} {b, c} {a, b, c} {a, b} {a, b, c} {b, c} {a, b, c}
Definition 1 (Timestamped Transaction Database). A timestamped transaction database over an item universe I is a finite set D = {(Tt , t) | t ∈ Z≥0 }, where each Tt ⊆ I is the transaction corresponding to timestamp t. Example. Throughout the following discussion, we use the database D shown in Table 2 (I = {a, b, c}, W = 10, σ = 3). Definition 2 (Occurrence Timestamp Sequence). The occurrence timestamp sequence of itemset P ⊆ I in D is defined as occ(P, D) = {t | P ⊆ Tt , (Tt , t) ∈ D}. When D is clear from context, we abbreviate this as occ(P ). Example. The occurrence timestamp sequences for each itemset in Table 2 are as follows: occ({a}) = {1, 3, 7, 9, 20, 25} occ({b}) = {1, 3, 5, 7, 9, 20, 22, 25} occ({c}) = {3, 5, 7, 20, 22, 25} occ({a, b}) = {1, 3, 7, 9, 20, 25} occ({a, c}) = {3, 7, 20, 25} occ({b, c}) = {3, 5, 7, 20, 22, 25} occ({a, b, c}) = {3, 7, 20, 25} Definition 3 (Interval Support). The interval support of itemset P in window [l, l + W ] (with window size W > 0) is defined as sup(P, l, W ) = |{t ∈ occ(P ) | l ≤ t ≤ l + W }|. For minimum support σ ∈ Z>0 , a window [l, l + W ] satisfying sup(P, l, W ) ≥ σ is called a dense window of P . Example. For P = {a, b}, l = 1, W = 10: sup({a, b}, 1, 10) = |{1, 3, 7, 9}| = 4 ≥ 3 = σ, so window [1, 11] is a dense window of {a, b}. At l = 15, however, sup({a, b}, 15, 10) = |{20, 25}| = 2 < 3, so [15, 25] is not a dense window. 6
Definition 4 (Dense Interval). An interval [s, e] (with 0 ≤ s, e ≤ Tmax , and e − s ≥ W ) is a dense interval of P if ∀ l ∈ t ∈ occ(P ) | s ≤ t ≤ e−W
: sup(P, l, W ) ≥ σ
and the interval cannot be further extended. Here Tmax is the maximum timestamp in dataset D. Example. For P = {a, b} with occ({a, b}) = {1, 3, 7, 9, 20, 25}, the condition sup({a, b}, l, 10) ≥ 3 holds only for l ∈ [−3, 3]. Indeed, at l = 4, sup({a, b}, 4, 10) = |{7, 9}| = 2 < 3. Hence the right endpoint of the dense interval is e = 3 + 10 = 13, and constraining the left endpoint to ≥ 0, the dense interval of {a, b} is [0, 13]. Definition 5 (Dense Pattern). An itemset P that has at least one dense interval is called a dense pattern. Definition 6 (Dense Pattern Mining Problem). Given a timestamped transaction database D, a window size W , and a minimum support σ, enumerate all pairs (P, DI(P )) of dense patterns P and their dense interval sets DI(P ). Example. For the database D in Table 2 with W = 10, σ = 3, and Tmax = 25, all dense patterns and their dense intervals are: {a} : [0, 13] {b} : [0, 15], [15, 25] {c} : [0, 13], [15, 25] {a, b} : [0, 13] {b, c} : [0, 13], [15, 25]
4
Proposed Method: Apriori-window
4.1
Method Overview
Apriori-window is an exact algorithm that applies the anti-monotonicity of Apriori [1] to sliding-window local frequency evaluation. The input is a timestamped transaction database D, a window size W , and a minimum support σ; the output is an enumeration of all dense patterns P together with their dense interval sets DI(P ). The algorithm begins at itemset size k = 1, repeatedly generating size-(k + 1) candidates from the size-k dense pattern set Lk and computing dense intervals for each candidate. Search space reduction employs two mechanisms: (1) candidate pattern pruning via anti-monotonicity of itemsets, and (2) candidate interval restriction via the intersection of dense intervals of individual items. Algorithm 1 presents the Apriori-window algorithm.
4.2
Anti-monotonicity
Proposition 1 (Anti-monotonicity of Interval Support). If P ′ ⊇ P , then sup(P ′ , l, W ) ≤ sup(P, l, W ) for any l and W .
7
Algorithm 1 Apriori-window Input: item ts: item-to-occ map; W : window size; σ: min support Output: F : map from pattern to dense intervals 1: F, L1 , S ← ∅, ∅, empty map 2: for x in sorted keys(item ts) do 3: DI(x) ← Scan(occ(x), W, σ, unr) 4: if DI(x) ̸= ∅ then 5: F [{x}] ← DI(x); L1 ← L1 ∪ {{x}}; S[x] ← DI(x) 6: end if 7: end for 8: k ← 2; Lp ← L1 9: while Lp ̸= ∅ do 10: Ck ← AprioriJoin(Lp ) on first k−2 items 11: Ck ← {X ∈ Ck | all (k−1)-subsets in Lp } 12: Lk ← ∅ 13: for X ∈ Ck do T 14: occ(X) ← x∈X occ(x) 15: if occ(X) = ∅ then 16: continue 17: end if 18: RX ← cand(X) using S[x] for x ∈ X 19: if RX = ∅ then 20: continue 21: end if 22: DI(X) ← Scan(occ(X), W, σ, RX ) 23: if DI(X) ̸= ∅ then 24: F [X] ← DI(X); Lk ← Lk ∪ {X} 25: end if 26: end for 27: Lp ← Lk ; k ← k + 1 28: end while 29: return F Proof. Since P ′ ⊇ P , any occurrence of P ′ must contain all items of P , so occ(P ′ , D) ⊆ occ(P, D). Consequently, the occurrence count within any window also satisfies sup(P ′ , l, W ) ≤ sup(P, l, W ). Proposition 1 establishes that the same candidate generation and pruning strategy as Apriori applies to the dense pattern mining problem. Proposition 2 (Containment of Dense Intervals). For any x ∈ P , every dense interval of P is contained within some dense interval of x. Proof. For a dense interval [s, e] of P , there exists l ∈ [s, e − W ] such that sup(P, l, W ) ≥ σ. By Proposition 1 (anti-monotonicity), for any x ∈ P , sup(x, l, W ) ≥ sup(P, l, W ) ≥ σ, so [l, l + W ] is a dense window of x. Hence l is contained within some dense interval of x. Since the left endpoint of [s, e] is determined by l, the interval [s, e] is contained within a dense interval of x.
8
From Proposition 2, the dense intervals of a pattern P of size k ≥ 2 cannot exist outside the intersection of the dense intervals of all individual items composing P (i.e., T x∈P DI(x)). Using this property, we restrict the search range for dense intervals to the candidate interval set ( ) \ cand (P ) = (s, e) ∈ DI(x) e − s ≥ W . x∈P
If cand (P ) is empty, then P cannot be a dense pattern, and the search is terminated.
4.3
Dense Interval Detection via Sliding Window
Algorithm 2 presents the dense interval detection procedure. In sliding-window interval detection, the number of scan operations affects computational efficiency. To reduce the number of scans, we introduce stride-skip. Stride-Skip: When the occurrence count within the window [l, l + W ] satisfies cnt ≥ σ, let tkeep be the position of the first of the last σ occurrences; the window starting position l is then advanced to tkeep + 1. Proposition 3 (Safety of Stride-Skip). Let cnt be the occurrence count within the window [l, l + W ], and suppose cnt ≥ σ. Let tkeep be the first of the last σ occurrences in this window. Then for any l′ satisfying l ≤ l′ ≤ tkeep , the window [l′ , l′ + W ] is also a dense window. Therefore, advancing l to tkeep + 1 does not miss any dense interval. Proof. Let the occurrences within the window [l, l + W ] be ordered as t1 ≤ t2 ≤ · · · ≤ tcnt (cnt ≥ σ). Consider the last σ occurrences tcnt−σ+1 , tcnt−σ+2 , . . . , tcnt . For any l′ satisfying l ≤ l′ ≤ tcnt−σ+1 , since l′ ≤ tcnt−σ+1 and tcnt ≤ l+W ≤ l′ +W (by l′ ≥ l), all σ occurrences are contained in [l′ , l′ + W ]. Hence [l′ , l′ + W ] is a dense window. Proposition 3 guarantees the safety of stride-skip. As the occurrence count cnt within the window increases, cnt − σ increases and the skip distance grows; therefore, greater computational efficiency is expected for patterns whose occurrences are more densely concentrated. Answer to RQ1: Exploiting the anti-monotonicity of the pattern space and the containment relationship of dense intervals, it is possible to realize an exact algorithm by extending the Apriori framework. Stride-skip further improves efficiency while preserving the exactness of the interval search.
5
Experiments
5.1
Experiment A: Analysis of Existing Methods
The purpose of this experiment is not to directly compare the proposed method against existing methods, but rather to investigate to what extent existing occurrence-gap-based methods can approximate the “window-based local frequency dense patterns and dense intervals” as defined in this work. To this end, we use the output of Apriori-window, which provides the exact solution under our definition, as the reference, and evaluate how well existing methods can approximate this definition. We use three benchmark datasets— Retail, OnlineRetail, and ChicagoCrime—publicly available through SPMF [40]. Dataset statistics are shown in Table 3. 9
Algorithm 2 Scan Input: occ: sorted occurrence positions; W : window size; σ: min support; R: scan ranges Output: DI: dense interval list 1: DI, recorded ← ∅ 2: for (cs , ce ) ∈ R do 3: j ← LB(occ, cs ); l ← max(cs , max(0, occ[j + σ − 1] − W )) 4: in dense, s, d ← false, ⊥, ⊥ 5: while l ≤ ce do 6: if l ∈ recorded block [a, b] then 7: l ← b + 1; continue 8: end if 9: cnt ← occurrence in window [l, l + W ] 10: if cnt < σ then 11: if in dense and d + W − s ≥ W then 12: Register(s, d + W, recorded) 13: end if 14: in dense, s, d ← false, ⊥, ⊥ 15: l ← max(l + 1, occ[UB(occ, l + W )] − W ) 16: else 17: keep ← occ[LB(occ, l) + cnt − σ] 18: if not in dense then 19: s ← l; d ← keep; in dense ← true 20: else 21: d ← max(d, keep) 22: end if 23: if keep +1 > ce then 24: d ← min(d, ce ); break 25: else 26: l ← keep +1 27: end if 28: end if 29: end while 30: if in dense and d + W − s ≥ W then 31: Register(s, d + W, recorded) 32: end if 33: end for 34: return DI We compare against the following methods: • FIM: Frequent Itemset Mining [1] • PFPM: Periodic-Frequent Pattern Mining [23] • PPFPM: Partial Periodic-Frequent Pattern Mining [28] • LPFIM: Locally and Periodically Frequent Itemset Mining [34] • LPPM: Local Periodic Pattern Mining [35] 10
Table 3: Experimental datasets. Dataset Retail OnlineRetail ChicagoCrime
#Trans
#Items
Avg. length
88,162 540,455 2,662,309
14,089 2,147 34
10.3 4.4 1.8
Table 4: Number of ground-truth dense patterns (length ≥ 2) in Experiment A. Header values denote W/σ. Dataset 250/25 500/50 750/75 1000/100 Retail Chicago
171 63
Dataset
110 42
89 28
81 23
100/10 250/25 500/50
OnlineRetail
355
64
11
• RPM: Recurring Pattern Mining [36] • Span: A reference method that outputs the interval from the first to the last occurrence timestamp of each pattern as a single interval. Its purpose is to verify the locality of the ground-truth dense periods in each dataset. The parameters (W, σ) of Apriori-window are set to {(250, 25), (500, 50), (750, 75), (1000, 100)} for Retail and ChicagoCrime, and to {(100, 10), (250, 25), (500, 50)} for OnlineRetail. Evaluation is restricted to patterns of length ≥ 2; the number of ground-truth dense patterns for each setting is shown in Table 4. The extraction accuracy of each method is evaluated using three metrics: F1 score, mean Jaccard, and mean Temporal Precision. Methods that do not output intervals (FIM, PFPM, PPFPM) are evaluated using F1 score only. Let P ∗ denote the set of ∗ patterns extracted S by Apriori-window and DI S (P ) their dense intervals. For each pattern P , let G(P ) = [s,e]∈DI∗ (P ) [s, e] and Ĝ(P ) = [s,e]∈DI(P c ) [s, e] denote the temporal coverage of the ground-truth and predicted intervals, respectively (where | · | denotes duration), and let P̂ denote the set of predicted patterns for each method. The F1 score is the harmonic mean based on the agreement between ground-truth and predicted pattern sets: 2 |P̂ ∩ P ∗ | F1 = |P̂| + |P ∗ | Mean Jaccard is the average over all ground-truth patterns of the Jaccard coefficient computed from the temporal overlap between ground-truth and predicted intervals: mean Jaccard =
1 X |G(P ) ∩ Ĝ(P )| |P ∗ | P ∈P ∗ |G(P ) ∪ Ĝ(P )|
Mean Temporal Precision is computed only for correctly identified patterns (P ∈ P̂ ∩ P ∗ ) and is the average fraction of the predicted intervals that overlap with the
11
Table 5: Parameter search space for each baseline method. σ: minimum support in the experimental setting (= W/10). N : upper bound for PFPM maximum period (Retail: 900, OnlineRetail: 3,500, Chicago: 10,000). N ′ : upper bound for PPFPM maximum period (Retail: 50, OnlineRetail: 500, Chicago: 900). MethodParameter
Value / Search Range
FIM
minSup
σ
PFPM
maxPer minSup
{5, 10, . . . , N } (step 5) σ
searched fixed
maxPer PPFPMminPR minSup
{5, 10, . . . , N ′ } (step 5) {0.05, 0.10, . . . , 0.95} σ
searched searched fixed
σℓ minthd1 LPFIM minthd2
{10, 15, 20, 25, 30}% {10, 15, . . . , 100} (step 5) {10, 20, . . . , 1000} (step 10)
searched searched searched
maxPer LPPM minDur maxSoPer
{5, 10, . . . , 50} (step 5) {5, 10, . . . , 1000} (step 5) {5, 10, . . . , 500} (step 5)
searched searched searched
{5, 10, . . . , 250} (step 5) σ 1
searched fixed fixed
RPM
maxPer minPS minRec
fixed
ground-truth intervals: mean TP =
1
X
|P̂ ∩ P ∗ |
P ∈P̂∩P ∗
|G(P ) ∩ Ĝ(P )| |Ĝ(P )|
The extraction accuracy of existing methods varies substantially depending on parameter settings. Therefore, for each method, parameters are selected by grid search to maximize the F1 score; ties are broken by prioritizing the setting with the higher Jaccard coefficient. The parameter search spaces for each method are shown in Table 5, and the best-F1 parameters for each method are listed in Appendix C. LPPM is implemented using the Java code publicly available in SPMF [40]; all other existing methods and Apriori-window are implemented in Rust. Table 6 presents the F1 score, mean Jaccard, and mean Temporal Precision at the best parameters for all methods across three datasets and all window sizes. The F1 score of FIM remained at most 0.035. Since FIM extracts patterns based on dataset-wide support, it retrieves a large number of non-dense patterns that occur at similar frequency to dense patterns but are spread throughout the dataset; consequently, recall is 1.0 while precision is extremely low. PFPM and PPFPM show improved F1 compared to FIM through the introduction of gap constraints (PPFPM Retail: 0.782–0.926, Chicago: 0.740–0.818), suggesting that occurrence-gap constraints can contribute to pattern identification accuracy. LPFIM, LPPM, and RPM, which output intervals, achieve high F1 (0.866–0.989) in certain settings for Retail and Chicago; however, Jaccard shows considerable variation across datasets and window sizes, and is particularly low for OnlineRetail. This is presumably because the ground-truth dense intervals include interval expansion based on the sliding window width W , which occurrence-gap-based methods cannot reproduce by 12
Table 6: Pattern identification accuracy and interval detection accuracy of baseline methods at best-F1 parameters. Best parameters for each method are listed in Appendix C. Since Apriori-window is an exact algorithm for dense patterns, it achieves F1 = Jaccard = TP = 1.000. F1 Score
Jaccard
Temporal Precision
Dataset
W
Retail
250 25 .009 500 50 .017 750 75 .025 1000 100 .035
.119 .120 .146 .159
.782 .861 .908 .926
.866 .830 .867 .868
.917 .967 .989 .981
.906 .941 .943 .929
.205 .218 .206 .201
.637 .715 .695 .649
.652 .710 .713 .652
.397 .526 .564 .540
.896 .949 .957 .962
.970 .988 .977 .954
.936 .933 .942 .945
.428 .609 .691 .704
Chicago
250 25 .007 500 50 .007 750 75 .006 1000 100 .007
.615 .627 .604 .622
.740 .743 .776 .818
.897 .886 .945 .957
.969 .952 .929 .936
.928 .963 .963 .920
.196 .337 .303 .156
.502 .514 .150 .182
.451 .424 .330 .346
.035 .042 .058 .069
.752 .817 .743 .673
.761 .853 .754 .730
.749 .716 .796 .591
.035 .042 .058 .069
.312 .230 .500
.770 .623 .909
.732 .814 1.000
.774 .938 .832 .699 .957 .909
.040 .027 .135
.065 .216 .012 .097 .311 .008 .239 .163 .013
.728 .432 .687
.762 .896 .012 .637 .741 .008 .358 .244 .013
100 OnlineRetail 250 500
σ FIM PFPM PPFPM LPFIM LPPM RPM LPFIM LPPM RPM Span LPFIM LPPM RPM Span
10 .013 25 .003 50 .001
definition. Based on mean Temporal Precision, we confirmed that interval mis-detection occurs even in settings where patterns are correctly identified. Across all methods and all datasets, mean Temporal Precision exceeds that of the Span reference method, suggesting that occurrence-gap-based interval extraction provides a certain degree of filtering effectiveness. However, in datasets where the Span score is low, cases were observed in which TP decreases even at settings with high F1 (e.g., RPM Chicago W = 1000: F1 = 0.920, TP = 0.591; LPPM OnlineRetail W = 500: F1 = 0.957, TP = 0.358). This suggests that relaxing parameter constraints to avoid missing dense patterns causes interval false positives, revealing a trade-off between pattern identification and accurate interval extraction. Answer to RQ2: Existing methods show a degree of effectiveness in dense pattern identification; however, simultaneously achieving high accuracy in both pattern identification and dense interval detection may be difficult.
5.2
Experiment B: Scalability
This experiment examines the growth trend of Apriori-window in execution time and memory usage with respect to data characteristics. Using synthetic data, we run 45 configurations with varying parameters T ∈ {1.0, 1.25, 1.5, 1.75, 2.0} × 106 transactions, I ∈ {10,000, 15,000, 20,000} items, and mean basket length B ∈ {5, 10, 15}, each repeated 10 times, and measure the mean execution time and peak memory usage. The synthetic data generation procedure is described in Appendix A. Experiments were conducted on an 11th Gen Intel Core i7-1185G7 @ 3.00 GHz with 32 GB RAM. Execution time and peak memory usage are shown in Fig. 2 and Fig. 3, respectively. Both metrics grow approximately linearly with the number of transactions, number of items, and basket length; even under the maximum setting (T = 2 × 106 , I = 20,000, B = 15), the mean execution time was 8.9 seconds and memory usage was 333 MiB. The number of extracted patterns ranged from 1,545 to 1,550 across all settings, confirming that the variation in dense pattern count due to parameter changes is small and that the main drivers of execution time and memory variation are data size and basket length. Both figures show increased execution time and memory usage as mean basket length increases (from 5 to 15), presumably because a larger basket length increases both the 13
Figure 1: Change in F1 score (red, solid) and mean Temporal Precision (green, dashed) with respect to the gap constraint parameter (LPFIM: minthd1 , LPPM: maxPer , RPM: recur per) for each method (W = 250, σ = 25; other parameters fixed at best-F1 settings). Vertical dotted lines indicate the gap value that maximizes F1. number of occurrence timestamps for each item and the number of candidate patterns. By contrast, the effect of increasing the number of items I (10k to 20k) is relatively small compared to basket length, presumably because while increasing items expands the length-1 candidate set, anti-monotonicity-based pruning restricts the search for longer patterns to those that include the embedded patterns. Answer to RQ3: Execution time grows approximately linearly with the number of transactions, items, and basket length; even under the maximum setting (T = 2 × 106 , I = 20k, B = 15), processing was completed within 8.9 seconds and 333 MiB of memory.
5.3
Experiment C: Ablation Study
We evaluate the effect of the two search space reduction techniques employed by the proposed method. The models used in the ablation study are defined as follows: • Baseline: A basic implementation with no optimizations applied. Candidate search 14
Figure 2: Scalability experiment: mean execution time (T ∈ [1×106 , 2×106 ], I ∈ {10k, 15k, 20k}, B ∈ {5, 10, 15}, averaged over 10 trials).
Figure 3: Scalability experiment: peak memory usage (same conditions, averaged over 10 trials). Line styles correspond to B settings; colors correspond to I settings.
is performed at all window positions. • Intersect: Applies candidate reduction via the intersection of dense intervals of length-1 patterns, but still performs window sliding at all positions. • Apriori-window: In addition to the intersection-based reduction, applies the stride-skip optimization. Windows are skipped based on the number of surplus occurrences, reducing unnecessary scan positions. Table 7 presents the ablation study results. First, the Intersect model reduces execution time compared to Baseline by an approximately equivalent margin for Retail, 40–50% for Chicago, and 10–60% for OnlineRetail. When the intersection computation substantially narrows the candidate interval space, the reduction in the candidate search space outweighs the overhead. Second, Apriori-window achieves reductions of 94–96% overall for Retail, 65–77% for Chicago, and 88–94% for OnlineRetail, demonstrating the pronounced effect of the stride-skip optimization. The relative contribution of stride-skip tends to improve as the window size increases, presumably because a larger window leads to greater surplus and consequently a wider skip distance.
5.4
Experiment D: Application to Real-World Data
This experiment applies the proposed method to real-world transactional data annotated with external events, and investigates whether dense patterns with different correspondences to external events can be extracted by varying the window size.
15
Table 7: Ablation study: comparison of execution times (ms, averaged over 10 trials) for different combinations of optimization components. Dataset
W
Retail
250 25 500 50 750 75 1000 100
3,313 3,181 3,744 3,190
3,111 3,241 3,145 3,106
164 324 184 140
Chicago
250 25 500 50 750 75 1000 100
6,587 5,202 4,626 4,269
3,575 3,023 2,953 2,806
2,036 1,303 1,116 1,077
14,620 7,320 6,475
6,020 5,631 5,642
813 488 357
100 OnlineRetail 250 500
σ Baseline Intersect Apriori-window
10 25 50
We use the Dunnhumby Complete Journey dataset.1 This dataset contains two years (711 days) of purchase histories from a U.S. retailer, consisting of 276,176 baskets and 308 product categories. The dataset also includes records of 30 promotional campaigns (Type A, Type B, and Type C, each lasting 32–161 days, with a mean duration of 46.6 days) and the products for which coupons were distributed in each campaign. Data preprocessing is described in Appendix B. We run Apriori-window under the following two conditions: • W = 47 days: W = 47,000 (47 days ≈ mean promotional duration), σ = 470, kmax = 5. Intended for detecting dense intervals corresponding to individual promotional periods. • W = 141 days: W = 141,000 (141 days ≈ 3×mean duration), σ = 1,410, kmax = 5. Intended for extracting long-term patterns spanning multiple promotional periods. As an indicator of the relationship between each dense pattern’s intervals and the promotional periods, we introduce the overlap ratio. For each pattern, we compute the overlap ratio Rpromo between its dense intervals and the promotional periods of the constituent products on a day-count basis: P overlap([ si , ei ], Ppromo ) P Rpromo = i i (ei − si ) where [si , ei ] is the i-th dense interval and Ppromo is the union of promotional periods for the constituent product group. Table 8 shows, for each dense interval [si , ei ], the number of promotional periods it overlaps. With W = 47 days, 83.0% of the intervals fell within a single promotional period (≤ 1 overlap), whereas with W = 141 days, 64.6% of the intervals spanned multiple promotional periods (≥ 2 overlaps); the mean number of overlapping periods was 1.06 and 1.93 for W = 47 and W = 141 days, respectively. Furthermore, the 149 patterns detected exclusively with W = 47 days had a mean Rpromo of 76.5%, exceeding the mean Rpromo of 58.4% for patterns commonly extracted under both window sizes. This indicates that patterns detected only with W = 47 days are those concentrated exclusively within specific campaign periods. 1
https://www.kaggle.com/datasets/frtgnn/dunnhumby-the-complete-journey
16
Table 8: Effect of window size: comparison between W = 47 days and W = 141 days. Number of extracted patterns Mean number of intervals per pattern Mean interval length Fraction of intervals overlapping ≤ 1 promotional period Fraction of intervals overlapping ≥ 2 promotional periods Mean number of overlapping promotional periods
W = 47 days
W = 141 days
513
364
23.3 222 days
9.2 385 days
83.0% 17.0% 1.06
35.4% 64.6% 1.93
Table 9: Examples of high-Rpromo dense patterns. Pattern BAKED BREAD & PNT BTR/ JELLY/JAMS
Setting
Dense terval
In- Campaigns overlapping with the dense inter- Rpromo val
[245, 332] W = 47 days [491, 574] [612, 711] W = 141 days [549, 711]
FROZEN PIZZA & SOUP
W = 47 days
[211, 329] [561, 711]
W = 141 days [542, 711]
CANNED JUICES & CHEESE & FLUID MILK
W = 47 days
[240, 330] [563, 711]
W = 141 days [550, 711]
C26 [224, 264], C28 [259, 320], C29 [281, 334], C30 [323, 369] C11 [477, 523], C12 [477, 509], C13 [504, 551], C14 [531, 596] C18 [587, 642], C21 [624, 656], C24 [659, 719] C13 [504, 551], C14 [531, 596], C18 [587, 642], C21 [624, 656], C24 [659, 719] C26 [224, 264], C27 [237, 300], C28 [259, 320], C29 [281, 334], C30 [323, 369] C16 [561, 593], C17 [575, 607], C18 [587, 642], C21 [624, 656], C22 [624, 656], C23 [646, 684], C25 [659, 691] C13 [504, 551], C16 [561, 593], C17 [575, 607], C18 [587, 642], C21 [624, 656], C22 [624, 656], C23 [646, 684], C25 [659, 691] C26 [224, 264], C28 [259, 320], C29 [281, 334], C30 [323, 369] C17 [575, 607], C18 [587, 642], C21 [624, 656], C22 [624, 656], C23 [646, 684], C25 [659, 691] C13 [504, 551], C17 [575, 607], C18 [587, 642], C21 [624, 656], C22 [624, 656], C23 [646, 684], C25 [659, 691]
100%
98%
94%
82%
98%
73%
Table 9 shows three examples of high-Rpromo dense patterns. A common trend across all three examples is that with W = 47 days, multiple dense intervals are extracted individually, each with Rpromo ≥ 94%, showing high temporal overlap with campaign periods. With W = 141 days, on the other hand, the dense intervals are merged into a single long-term interval around DAY [550, 711], collectively capturing multiple consecutive campaigns. Table 10 shows three examples of low-Rpromo dense patterns. A common characteristic across all three examples is that Rpromo is low, ranging from 21% to 39%, and remains at a low level regardless of the window size. The total coverage by dense intervals exceeds 550 days, indicating that dense intervals are formed throughout the entire data collection period. All three are combinations of food items centered around beef, and such product groups are expected to co-occur throughout the year regardless of specific promotional periods. In addition, although the number of intervals decreases substantially with W = 17
Table 10: Examples of low-Rpromo dense patterns. Pattern
Setting
No. of intervals
Total coverage by dense intervals (days)
Rpromo
BEEF & CHICKEN
W = 47 days W = 141 days
54 31
575 551
24% 11%
BEEF & POTATOES
W = 47 days W = 141 days
49 9
557 595
21% 33%
BEEF & LUNCHMEAT
W = 47 days W = 141 days
8 1
644 670
39% 29%
141 days, the total coverage is maintained and the variation in Rpromo is small. This suggests that while the granularity of the number and length of intervals varies with window size, patterns with a broad temporal distribution can be consistently extracted. In summary, we confirmed that setting the window size to match the promotional period duration enables individual detection of dense intervals corresponding to each promotional period, while a larger window captures long-term dense intervals spanning multiple promotional periods. Patterns distributed throughout the entire data collection period (711 days) tended to be detected under both window sizes. The parameter W determines the temporal resolution of the dense intervals; in practice, appropriate selection of W according to the analysis objective is required.
6
Conclusion
In this paper, we proposed Apriori-window, an exact algorithm for mining patterns together with their dense intervals from transactional data. The proposed method is based on direct evaluation of local frequency via a sliding window, and avoids the inherent trade-off between pattern identification accuracy and interval detection accuracy that characterizes occurrence-gap-based methods. Through candidate interval pruning using the anti-monotonicity of interval support and stride adjustment based on surplus occurrences, we achieved comprehensive and exact dense pattern mining at practical efficiency. Experiments on three real-world datasets demonstrated that existing methods struggle to simultaneously achieve high accuracy in both pattern identification and dense interval detection, and scalability experiments on synthetic data confirmed that the proposed method operates within 8.9 seconds and 333 MiB of memory even at a scale of one million transactions. Future directions include application to a wider range of real-world data, analysis of relationships among dense intervals, and online application to streaming data.
References [1] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” in Proc. VLDB, 1994, pp. 487–499. [2] M. J. Zaki, S. Parthasarathy, M. Ogihara, and W. Li, “New algorithms for fast discovery of association rules,” in Proc. KDD, 1997, pp. 283–296. [3] J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation,” ACM SIGMOD Record, vol. 29, no. 2, pp. 1–12, 2000. 18
[4] P. Fournier-Viger, J. C.-W. Lin, B. Vo, T. T. Chi, J. Zhang, and H. B. Le, “A survey of itemset mining,” WIREs Data Mining Knowl. Discov., vol. 7, no. 4, e1207, 2017. [5] P. Fournier-Viger, W. Gan, Y. Wu, M. Nouioua, W. Song, T. Truong, and H. Duong, “Pattern mining: Current challenges and opportunities,” in Proc. DASFAA Workshops, LNCS 13248, 2022, pp. 34–49. [6] J. M. Luna, P. Fournier-Viger, and S. Ventura, “Frequent itemset mining: A 25 years review,” WIREs Data Mining Knowl. Discov., vol. 9, no. 6, e1329, 2019. [7] B. Liu, W. Hsu, and Y. Ma, “Mining association rules with multiple minimum supports,” in Proc. KDD, 1999, pp. 337–341. [8] C. F. Ahmed, S. K. Tanbeer, B.-S. Jeong, and Y.-K. Lee, “Efficient tree structures for high utility pattern mining in incremental databases,” IEEE Trans. Knowl. Data Eng., vol. 21, no. 12, pp. 1708–1721, 2009. [9] P. Fournier-Viger, J. C.-W. Lin, T. Truong-Chi, and R. Nkambou, “A survey of high utility itemset mining,” in High-Utility Pattern Mining, Springer, 2019, pp. 1–45. [10] T. Berteloot, R. Khoury, and A. Durand, “Association rules mining with autoencoders,” in Proc. IDEAL, LNCS, Springer, 2025. [11] E. Karabulut, R. Pellicer-Valero, V. Degeler, and P. Fournier-Viger, “Learning semantic association rules from internet of things data,” arXiv:2412.03417, 2024. [12] J. Fischer and J. Vreeken, “Differentiable pattern set mining,” in Proc. KDD, 2021, pp. 383–392. [13] S. Ghosh, A. Chakraborty, and S. Dey, “Probabilistic and reinforced mining of association rules,” arXiv:2506.18155, 2025. [14] A. Jamshed, B. Mallick, and P. Kumar, “Deep learning-based sequential pattern mining for progressive database,” Soft Computing, vol. 24, no. 22, pp. 17233–17246, 2020. [15] M. K. Porwal and N. Porwal, “A novel deep learning model for high-utility item set mining in transactional data,” in Intelligent Systems (ICMIB 2025), LNNS vol. 1623, Springer, 2026, pp. 267–280. [16] Y. Djenouri, D. Djenouri, A. Belhadi, P. Fournier-Viger, and J. C.-W. Lin, “A new framework for metaheuristic-based frequent itemset mining,” Applied Intelligence, vol. 48, pp. 4775–4791, 2018. [17] A. Telikani, A. H. Gandomi, and A. Shahbahrami, “A survey of evolutionary computation for association rule mining,” Information Sciences, vol. 524, pp. 318–352, 2020. [18] Q. Wan and A. An, “Discovering transitional patterns and their significant milestones in transaction databases,” IEEE Trans. Knowl. Data Eng., vol. 21, no. 12, pp. 1692– 1707, 2009.
19
[19] C.-Y. Chang, M.-S. Chen, and C.-H. Lee, “Mining general temporal association rules for items with different exhibition periods,” in Proc. ICDM, 2002, pp. 59–66. [20] C.-H. Lee, M.-S. Chen, and C.-R. Lin, “Progressive partition miner: An efficient algorithm for mining general temporal association rules,” IEEE Trans. Knowl. Data Eng., vol. 15, no. 4, pp. 1004–1017, 2003. [21] J. Kleinberg, “Bursty and hierarchical structure in streams,” Data Mining and Knowledge Discovery, vol. 7, no. 4, pp. 373–397, 2003. [22] Z. Yang, Y. Gong, Q. He, Y. Zhang, and T. Yang, “BurstSketch: Finding bursts in data streams,” in Proc. ACM SIGMOD, 2021, pp. 2375–2383. [23] S. K. Tanbeer, C. F. Ahmed, B.-S. Jeong, and Y.-K. Lee, “Discovering periodicfrequent patterns in transactional databases,” in Proc. PAKDD, 2009, pp. 242–253. [24] R. U. Kiran, M. Kitsuregawa, and P. K. Reddy, “Efficient discovery of periodicfrequent patterns in very large databases,” J. Systems and Software, vol. 112, pp. 110–121, 2016. [25] P. Fournier-Viger et al., “Discovering periodic high utility itemsets in a discrete sequence,” in High-Utility Pattern Mining, Studies in Big Data vol. 51, Springer, 2021, pp. 157–181. [26] K. Amphawan, P. Lenca, and A. Surarerks, “Mining top-K periodic-frequent pattern from transactional databases without support threshold,” in Proc. IAIT, 2009, pp. 18–29. [27] J.-Y. Chen, Y.-C. Chen, and S.-Y. Lee, “An efficient bit-based approach for mining skyline periodic itemset patterns,” Electronics, vol. 12, no. 23, 4874, 2023. [28] R. U. Kiran, J. Venkatesh, M. Toyoda, M. Kitsuregawa, and P. K. Reddy, “Discovering partial periodic-frequent patterns in a transactional database,” J. Systems and Software, vol. 125, pp. 170–182, 2017. [29] V. Radhakrishna, P. Kumar, and V. Janaki, “A survey on temporal databases and data mining,” in Proc. ICEMIS, 2015, pp. 1–6. [30] G. Dong and J. Li, “Efficient mining of emerging patterns: Discovering trends and differences,” in Proc. KDD, 1999, pp. 43–52. [31] K.-C. Yin, Y.-L. Hsieh, D.-L. Yang, and M.-C. Hung, “Association rule mining considering local frequent patterns with temporal intervals,” Applied Mathematics & Information Sciences, vol. 8, no. 4, pp. 1879–1890, 2014. [32] B. Saleh and F. Masseglia, “Time aware mining of itemsets,” in Proc. TIME, 2008, pp. 93–97. [33] B. Saleh and F. Masseglia, “Discovering frequent behaviors: Time is an essential element of the context,” Knowledge and Information Systems, vol. 28, no. 2, pp. 311– 331, 2011.
20
[34] A. K. Mahanta, F. A. Mazarbhuiya, and H. K. Baruah, “Finding locally and periodically frequent sets and periodic association rules,” in Proc. PReMI, 2005, pp. 576– 582. [35] P. Fournier-Viger, P. Yang, R. U. Kiran, S. Ventura, and J. M. Luna, “Mining local periodic patterns in a discrete sequence,” Information Sciences, vol. 544, pp. 519– 548, 2021. [36] R. U. Kiran, H. Shang, M. Toyoda, and M. Kitsuregawa, “Discovering recurring patterns in time series,” in Proc. EDBT, 2015, pp. 97–108. [37] C.-H. Lee, C.-R. Lin, and M.-S. Chen, “Sliding-window filtering: An efficient algorithm for incremental mining,” in Proc. CIKM, 2001, pp. 263–270. [38] C. K.-S. Leung and Q. I. Khan, “DSTree: A tree structure for the mining of frequent sets from data streams,” in Proc. ICDM, 2006, pp. 928–932. [39] S. Aminikhanghahi and D. J. Cook, “A survey of methods for time series change point detection,” Knowledge and Information Systems, vol. 51, no. 2, pp. 339–367, 2017. [40] P. Fournier-Viger, J. C.-W. Lin, A. Gomariz, T. Gueniche, A. Soltani, Z. Deng, and H. T. Lam, “The SPMF open-source data mining library version 2,” in Proc. ECML-PKDD, 2016, pp. 36–40. [41] C.-H. Chee, J. Jaafar, I. A. Aziz, M. H. Hasan, and W. Yeoh, “Algorithms for frequent itemset mining: A literature review,” Artificial Intelligence Review, vol. 52, pp. 2603–2621, 2019.
A
Synthetic Data Generation for the Scalability Experiment
Synthetic data were generated to evaluate the scalability of the proposed method. For background transaction generation, the number of transactions T , item universe size I, and mean transaction length B were taken as inputs. Each transaction length was drawn from a normal distribution with mean B and standard deviation max(1, B/3), rounded to an integer, and clipped to the range [0, I], after which the corresponding number of items were sampled uniformly at random without replacement. To suppress the extraction of patterns of length ≥ 2 other than the embedded patterns, the expected item occurrence frequency in the background data was adjusted so that co-occurrences other than the embedded patterns were unlikely. Timestamps were assigned one per transaction; outside the embedding interval, intertransaction gaps followed a discrete uniform distribution over [5, 10], and inside the embedding interval, gaps were adjusted to satisfy the prescribed interval length. Dense patterns were embedded with the following parameters: • Pattern length: 5 • Number of patterns: 50 • Dense interval length: 10,000 21
• Number of dense intervals per pattern: 1 • Occurrences per pattern within the interval: 100 The total number of patterns of length ≥ 2 to be extracted was controlled to 1,300.
B
Data Preprocessing for Experiment D
Each basket in the Dunnhumby Complete Journey dataset is annotated with a day-level timestamp (DAY); however, Apriori-window assumes consecutive integer timestamps. We therefore sorted baskets in ascending order of (DAY, BASKET ID) and defined the timestamp of each basket as rank within day × 1000 timestamp = DAY × 1000 + nday (where nday is the total number of baskets on that day, at most 668 < 1000). This uniform placement distributes baskets evenly across slots 0–999 within each day, so that W = d × 1000 corresponds precisely to a d-day window. The original DAY value can be recovered directly as ⌊timestamp/1000⌋.
C
Best F1 Parameters for Each Method
We list below the F1-maximizing parameters for each method and setting reported in Table 6. FIM For all datasets, minSup is set to the experimental minimum support σexp . LPFIM • Retail: – W = 250, σ = 25: σℓ = 15%, minthd1 = 10, minthd2 = 20 – W = 500, σ = 50: σℓ = 15%, minthd1 = 10, minthd2 = 30 – W = 750, σ = 75: σℓ = 20%, minthd1 = 10, minthd2 = 20 – W = 1000, σ = 100: σℓ = 20%, minthd1 = 10, minthd2 = 30 • Chicago: – W = 250, σ = 25: σℓ = 10%, minthd1 = 20, minthd2 = 90 – W = 500, σ = 50: σℓ = 10%, minthd1 = 35, minthd2 = 200 – W = 750, σ = 75: σℓ = 10%, minthd1 = 45, minthd2 = 290 – W = 1000, σ = 100: σℓ = 10%, minthd1 = 25, minthd2 = 300 • OnlineRetail: – W = 100, σ = 10: σℓ = 15%, minthd1 = 10, minthd2 = 10 – W = 250, σ = 25: σℓ = 15%, minthd1 = 40, minthd2 = 10 – W = 500, σ = 50: σℓ = 10%, minthd1 = 55, minthd2 = 100 22
LPPM • Retail: – W = 250, σ = 25: maxPer = 10, minDur = 165, maxSoPer = 75 – W = 500, σ = 50: maxPer = 10, minDur = 425, maxSoPer = 105 – W = 750, σ = 75: maxPer = 10, minDur = 635, maxSoPer = 160 – W = 1000, σ = 100: maxPer = 10, minDur = 685, maxSoPer = 145 • Chicago: – W = 250, σ = 25: maxPer = 10, minDur = 145, maxSoPer = 125 – W = 500, σ = 50: maxPer = 10, minDur = 350, maxSoPer = 185 – W = 750, σ = 75: maxPer = 15, minDur = 335, maxSoPer = 10 – W = 1000, σ = 100: maxPer = 15, minDur = 460, maxSoPer = 15 • OnlineRetail: – W = 100, σ = 10: maxPer = 5, minDur = 25, maxSoPer = 90 – W = 250, σ = 25: maxPer = 5, minDur = 50, maxSoPer = 55 – W = 500, σ = 50: maxPer = 10, minDur = 205, maxSoPer = 120 PFPM • Retail: – W = 250, σ = 25: maxPer = 885, minSup = 25 – W = 500, σ = 50: maxPer = 255, minSup = 50 – W = 750, σ = 75: maxPer = 255, minSup = 75 – W = 1000, σ = 100: maxPer = 255, minSup = 100 • Chicago: – W = 250, σ = 25: maxPer = 6050, minSup = 25 – W = 500, σ = 50: maxPer = 3655, minSup = 50 – W = 750, σ = 75: maxPer = 3655, minSup = 75 – W = 1000, σ = 100: maxPer = 3560, minSup = 100 • OnlineRetail: – W = 100, σ = 10: maxPer = 3400, minSup = 10 – W = 250, σ = 25: maxPer = 1165, minSup = 25 – W = 500, σ = 50: maxPer = 785, minSup = 50
23
PPFPM • Retail: – W = 250, σ = 25: maxPer = 50, minPR = 0.90, minSup = 25 – W = 500, σ = 50: maxPer = 50, minPR = 0.95, minSup = 50 – W = 750, σ = 75: maxPer = 50, minPR = 0.95, minSup = 75 – W = 1000, σ = 100: maxPer = 50, minPR = 0.95, minSup = 100 • Chicago: – W = 250, σ = 25: maxPer = 15, minPR = 0.30, minSup = 25 – W = 500, σ = 50: maxPer = 185, minPR = 0.95, minSup = 50 – W = 750, σ = 75: maxPer = 45, minPR = 0.75, minSup = 75 – W = 1000, σ = 100: maxPer = 45, minPR = 0.75, minSup = 100 • OnlineRetail: – W = 100, σ = 10: maxPer = 105, minPR = 0.55, minSup = 10 – W = 250, σ = 25: maxPer = 70, minPR = 0.65, minSup = 25 – W = 500, σ = 50: maxPer = 80, minPR = 0.80, minSup = 50 RPM • Retail: – W = 250, σ = 25: maxPer = 30, minPS = 25, minRec = 1 – W = 500, σ = 50: maxPer = 40, minPS = 50, minRec = 1 – W = 750, σ = 75: maxPer = 45, minPS = 75, minRec = 1 – W = 1000, σ = 100: maxPer = 45, minPS = 100, minRec = 1 • Chicago: – W = 250, σ = 25: maxPer = 30, minPS = 25, minRec = 1 – W = 500, σ = 50: maxPer = 35, minPS = 50, minRec = 1 – W = 750, σ = 75: maxPer = 35, minPS = 75, minRec = 1 – W = 1000, σ = 100: maxPer = 45, minPS = 100, minRec = 1 • OnlineRetail: – W = 100, σ = 10: maxPer = 40, minPS = 10, minRec = 1 – W = 250, σ = 25: maxPer = 75, minPS = 25, minRec = 1 – W = 500, σ = 50: maxPer = 80, minPS = 50, minRec = 1
24