Frequent Pattern Mining from Data Streams.
1. Search Space in Data Stream Frequent Pattern Mining
In frequent pattern mining, the search space is the set of all possible patterns
(items/itemsets/sequences) that can be discovered from the stream.
For data streams, the search space is dynamic, unbounded, and time-sensitive because:
• New items appear over time
• Item frequencies change
• Only a portion of the stream is stored
• Patterns may become frequent or infrequent as the window slides
➢ Types of Search Spaces
(A) Search Space for Frequent Itemsets
Patterns are sets of items, example:
{A}, {B}, {A,B}, {A,C}, {A,B,C}, ...
Search space size = (2^m) where m = number of items seen so far.
Because m increases over time in a stream, search space is unbounded.
Streaming challenges:
• Cannot generate all subsets for each transaction
• Memory is not enough to store full candidate sets
• Counts must be approximate (Count-Min Sketch, Lossy Counting)
• Must prune aggressively
(B) Search Space for Sequential Patterns
Patterns are ordered lists of items, example:
<A>, <A→B>, <A→C→D>, <A→(B,C)→D>
Search space size = exponential × factorial = extremely large.
Thus, stream algorithms use:
• Pattern-growth (PrefixSpan-like)
• Occurrence-pattern compression
• Sliding-window counts
• Approximation counters
(C) Search Space Restriction Techniques
Prefix-based search space
Use pattern-growth like PrefixSpan, FP-Stream, CPS-Tree.
Candidate-based search space
Use Apriori-like structure (e.g., estDec, Lossy Counting, Manku-Motwani).
Approximate search space
Using synopsis structures:
• Count-Min Sketch
• Lossy Counting
• Sticky Sampling
• Reservoir Sampling
• Sampling + window-based mining
Time-based restricted search space
Items expire based on window length → reduces search space by deleting outdated counts.
2. Landmark Windows in Data Stream Mining
A window model defines how much of the stream is considered during mining.
A Landmark Window is a cumulative window starting from a fixed landmark time.
➢ Definition: Landmark Window
A landmark L is a specific starting point in the stream.
The window includes all transactions from L to now:
[
W(t) = {T_i \mid i \ge L}
]
Typical usage:
• Detecting long-term trends
• Mining over complete session / entire stream seen so far
• Constructing models for entire history
➢ Example
Stream:
T1, T2, T3, T4, T5, T6, …
Landmark = T1
At time t = 5:
Window = {T1, T2, T3, T4, T5}
At time t = 10:
Window = {T1, T2, …, T10}
• Window never shrinks
• Patterns accumulate frequencies forever
• Trending patterns become stable
➢ Why Use Landmark Windows?
Feature Benefit
Accumulates all data Detects global patterns
Easy to compute No deletions, no expiration
Stable supports Patterns vary smoothly
More accurate Better accuracy than sliding windows
Useful for logs, sessions, clickstreams Long-term behaviour
➢ Weaknesses of Landmark Windows
Problem Description
No forgetting old data Past dominates future
Search space grows unbounded Memory explosion
Cannot adapt to concept drift Model becomes outdated
Large aggregation structures needed Need sketches or summaries
➢ How Frequent Pattern Mining Works on Landmark Windows
Most algorithms follow the structure:
Initialize counts = 0
For each incoming transaction:
Update counts of items in transaction
Generate and update counts of candidate itemsets
Report all itemsets with count >= min_sup × window_size
Because window grows continuously:
• Support threshold must be absolute (not relative)
• Need pruning based on error bounds (Lossy Counting)
➢ Algorithms That Use Landmark Windows
1. Lossy Counting (Manku & Motwani)
• Maintains counters with error bounds
• Prunes low-frequency items
• Guarantees ( \epsilon )-approximate frequent itemsets
• Perfect for landmark windows because it never deletes data, only compresses.
2. Sticky Sampling
• Probability-based updating
• Maintains only items likely to become frequent
• Uses fixed probability that depends on landmark window size
3. Count-Min Sketch (CMS)
• A small 2D array of counters
• Updates per transaction
• Provides approximate frequency estimation
• Works perfectly with landmark model since summarization accumulates over time
4. FP-Stream (Landmark version)
• Builds a prefix-tree with timestamped counters
• Patterns accumulate counts as stream grows
• Old patterns may be pruned based on decay factor
5. Reservoir Sampling → Offline mining periodically
• Keeps sample of landmark window
• Mine FP-Growth or other static algorithm on the sample
➢ Comparing Search Space vs. Landmark Window
Aspect Search Space Landmark Window
All possible patterns (items, All stream data from baseline to current
Definition
itemsets, sequences) time
Exponential, grows as items
Size Increases indefinitely
increase
Memory
Too many patterns Too many transactions
Challenge
Approach to Pruning, sketches, sampling, Approximation (LC, CMS), memory-
Manage prefix trees compressed structures
Nature Structural concept Window model concept
➢ Combined View:
Frequent Pattern Mining from Data Streams
= Search Space Control + Window Model + Approximate Counting
To mine frequent itemsets from streams, an algorithm must decide:
1. What part of stream to mine?
o Landmark window
o Sliding window
o Damped window
2. How to manage search space?
o Prune candidates (Apriori-based)
o Compressed structure (FP-tree variants)
o Count-Min Sketch / Lossy Counting
o Sampling
3. How to estimate support?
o Exact (if window fits memory)
o Approximate with error guarantees
Below is a clear, detailed, academically complete explanation of Frequent Pattern
Mining from Data Streams, focused on two major topics you asked for:
1. Search Space in Streaming Frequent Mining
2. Landmark Window Model
I also include diagrams, definitions, examples, and algorithm connections.
➢ Search Space in Data Stream Frequent Pattern Mining
In frequent pattern mining, the search space is the set of all possible patterns
(items/itemsets/sequences) that can be discovered from the stream.
For data streams, the search space is dynamic, unbounded, and time-sensitive because:
• New items appear over time
• Item frequencies change
• Only a portion of the stream is stored
• Patterns may become frequent or infrequent as the window slides
➢ Types of Search Spaces
(A) Search Space for Frequent Itemsets
Patterns are sets of items, example:
{A}, {B}, {A,B}, {A,C}, {A,B,C}, ...
Search space size = (2^m) where m = number of items seen so far.
Because m increases over time in a stream, search space is unbounded.
Streaming challenges:
• Cannot generate all subsets for each transaction
• Memory is not enough to store full candidate sets
• Counts must be approximate (Count-Min Sketch, Lossy Counting)
• Must prune aggressively
(B) Search Space for Sequential Patterns
Patterns are ordered lists of items, example:
<A>, <A→B>, <A→C→D>, <A→(B,C)→D>
Search space size = exponential × factorial = extremely large.
Thus, stream algorithms use:
• Pattern-growth (PrefixSpan-like)
• Occurrence-pattern compression
• Sliding-window counts
• Approximation counters
(C) Search Space Restriction Techniques
Prefix-based search space
Use pattern-growth like PrefixSpan, FP-Stream, CPS-Tree.
Candidate-based search space
Use Apriori-like structure (e.g., estDec, Lossy Counting, Manku-Motwani).
Approximate search space
Using synopsis structures:
• Count-Min Sketch
• Lossy Counting
• Sticky Sampling
• Reservoir Sampling
• Sampling + window-based mining
Time-based restricted search space
Items expire based on window length → reduces search space by deleting outdated counts.
➢ 2. Landmark Windows in Data Stream Mining
A window model defines how much of the stream is considered during mining.
A Landmark Window is a cumulative window starting from a fixed landmark time.
Definition: Landmark Window
A landmark L is a specific starting point in the stream.
The window includes all transactions from L to now:
[
W(t) = {T_i \mid i \ge L}
]
Typical usage:
• Detecting long-term trends
• Mining over complete session / entire stream seen so far
• Constructing models for entire history
Example
Stream:
T1, T2, T3, T4, T5, T6, …
Landmark = T1
At time t = 5:
Window = {T1, T2, T3, T4, T5}
At time t = 10:
Window = {T1, T2, …, T10}
• Window never shrinks
• Patterns accumulate frequencies forever
• Trending patterns become stable
➢ Why Use Landmark Windows?
Feature Benefit
Accumulates all data Detects global patterns
Easy to compute No deletions, no expiration
Stable supports Patterns vary smoothly
More accurate Better accuracy than sliding windows
Useful for logs, sessions, clickstreams Long-term behaviour
➢ Weaknesses of Landmark Windows
Problem Description
No forgetting old data Past dominates future
Search space grows unbounded Memory explosion
Cannot adapt to concept drift Model becomes outdated
Large aggregation structures needed Need sketches or summaries
➢ How Frequent Pattern Mining Works on Landmark Windows
Most algorithms follow the structure:
Initialize counts = 0
For each incoming transaction:
Update counts of items in transaction
Generate and update counts of candidate itemsets
Report all itemsets with count >= min_sup × window_size
Because window grows continuously:
• Support threshold must be absolute (not relative)
• Need pruning based on error bounds (Lossy Counting)
➢ Algorithms That Use Landmark Windows
1. Lossy Counting (Manku & Motwani)
• Maintains counters with error bounds
• Prunes low-frequency items
• Guarantees ( \epsilon )-approximate frequent itemsets
• Perfect for landmark windows because it never deletes data, only compresses.
2. Sticky Sampling
• Probability-based updating
• Maintains only items likely to become frequent
• Uses fixed probability that depends on landmark window size
3. Count-Min Sketch (CMS)
• A small 2D array of counters
• Updates per transaction
• Provides approximate frequency estimation
• Works perfectly with landmark model since summarization accumulates over time
4. FP-Stream (Landmark version)
• Builds a prefix-tree with timestamped counters
• Patterns accumulate counts as stream grows
• Old patterns may be pruned based on decay factor
5. Reservoir Sampling → Offline mining periodically
• Keeps sample of landmark window
• Mine FP-Growth or other static algorithm on the sample
➢ Comparing Search Space vs. Landmark Window
Aspect Search Space Landmark Window
All possible patterns (items, All stream data from baseline to current
Definition
itemsets, sequences) time
Aspect Search Space Landmark Window
Exponential, grows as items
Size Increases indefinitely
increase
Memory
Too many patterns Too many transactions
Challenge
Approach to Pruning, sketches, sampling, Approximation (LC, CMS), memory-
Manage prefix trees compressed structures
Nature Structural concept Window model concept
➢ Combined View:
Frequent Pattern Mining from Data Streams = Search Space Control + Window Model + Approximate Counting
To mine frequent itemsets from streams, an algorithm must decide:
1. What part of stream to mine?
o Landmark window
o Sliding window
o Damped window
2. How to manage search space?
o Prune candidates (Apriori-based)
o Compressed structure (FP-tree variants)
o Count-Min Sketch / Lossy Counting
o Sampling
3. How to estimate support?
o Exact (if window fits memory)
o Approximate with error guarantees
Landmark Window Problems (window = from a fixed landmark time to now)
Note: landmark windows accumulate everything from the landmark onward;
nothing ever expires.
Problem L1 (easy — single item frequency)
Stream of items (arriving from the landmark):
S = [A, B, A, C, A, B, A]
Question: What is the frequency (count) and relative support of item A in the
landmark window? (Support = count / total items.)
Solution
• Total items = 7.
• Count(A) = number of A’s = positions 1, 3, 5, 7 → 4.
• Support(A) = 4 / 7 ≈ 0.5714 (57.14%).
Answer: Count = 4; Support ≈ 57.14%.
Problem L2 (medium — 2-itemsets with absolute min_sup)
Stream: S = [ {A,B}, {A}, {B}, {A,B}, {C}, {A,B}, {A} ] — here each
element is a transaction (a set).
Question: With absolute minimum support threshold min_sup = 3 (an itemset
must appear in ≥3 transactions), list all frequent 1-itemsets and 2-itemsets in
the landmark window.
Solution
• Total transactions = 7.
• Count single items:
o A appears in transactions 1,2,4,6,7 → count(A)=5.
o B appears in transactions 1,3,4,6 → count(B)=4.
o C appears in transaction 5 → count(C)=1.
• Frequent 1-itemsets (count ≥ 3): {A}, {B}.
• Count 2-itemsets:
o {A,B} appears in transactions 1,4,6 → count({A,B})=3.
o {A,C}: never (C only in tx 5 which has no A) → 0.
o {B,C}: 0.
• Frequent 2-itemsets (count ≥ 3): {A,B}.
Answer: Frequent 1-itemsets: {A} (5), {B} (4). Frequent 2-itemset: {A,B}
(3).
Problem L3 (harder — sequential counts across landmark)
Stream of ordered events (single user): ⟨A, B, A, C, B, A, B⟩ (landmark at
start).
Question: Find support (count) of sequence ⟨A → B⟩ (i.e., an A followed later
by a B) assuming non-overlapping occurrences are counted as distinct
occurrences when they appear in order (count every pair of positions i<j with
event i = A and event j = B).
Solution
We must count every ordered pair (i,j) with i < j, S[i]=A, S[j]=B.
List indices: 1:A, 2:B, 3:A, 4:C, 5:B, 6:A, 7:B.
For each A at index i, count B’s at later indices:
• A at i=1 → B at j=2,5,7 → 3 occurrences.
• A at i=3 → B at j=5,7 → 2 occurrences.
• A at i=6 → B at j=7 → 1 occurrence.
Total = 3 + 2 + 1 = 6.
Answer: Count(⟨A→B⟩) = 6 (support = 6 / number_of_possible_pairs — but
usually raw count = 6).
Sliding Window Problems (window = last W transactions/items; older items expire)
We use count-based sliding windows unless specified.
Problem S1 (easy — window of size 5)
Stream (arrival order): A, B, A, C, A, D, A, B
Window size W = 5 (most recent 5 items). After processing the entire stream,
what are the frequencies of A, B, C, D inside the current window?
Solution
We look at the last 5 items of the stream. Stream length = 8. Last 5 items =
positions 4..8 = [C, A, D, A, B].
Count:
• A: appears at positions 5 and 7 → 2.
• B: at position 8 → 1.
• C: at position 4 → 1.
• D: at position 6 → 1.
Answer: In window = [C,A,D,A,B]: A=2, B=1, C=1, D=1.
Problem S2 (medium — sliding window with transactions)
Transactions arriving:
T1={A,B}, T2={B}, T3={A,C}, T4={A,B}, T5={C}, T6={A,B}
Window = last 4 transactions (W=4). After T6 arrives, find frequent items with
min_sup (relative) = 0.5 (i.e., item must occur in ≥50% of window
transactions).
Solution
• After T6 arrived, window contains last 4 transactions: T3, T4, T5, T6 (transactions
3..6).
o T3={A,C}
o T4={A,B}
o T5={C}
o T6={A,B}
• Window size = 4 → min absolute support = 0.5 × 4 = 2 transactions.
• Count per item in window:
o A appears in T3, T4, T6 → 3.
o B appears in T4, T6 → 2.
o C appears in T3, T5 → 2.
• Items with count ≥ 2: A (3), B (2), C (2).
Answer: Frequent items: A (3), B (2), C (2).
Problem S3 (harder — sliding window sequential pattern)
Stream of events (single sequence) arriving over time: ⟨A, B, A, C, A, B, C,
A⟩. Window size W = 6 (most recent 6 events). After the final event arrives,
find occurrences and support (count) of sequence ⟨A → C⟩ inside the window.
Count each ordered pair of an A followed later by a C within the window.
Solution
• Final stream length = 8. Current window = last 6 events = positions 3..8: [A, C, A, B,
C, A] (indices 3 to 8).
Label positions inside window (global index): 3:A, 4:C, 5:A, 6:B, 7:C, 8:A.
We count every ordered pair (i,j) with i<j, S[i]=A, S[j]=C, both within the window.
Find A positions: i = 3, 5, 8.
For each:
• i=3 (A at pos3): C’s after pos3 within window at pos4 and pos7 → 2 occurrences.
• i=5 (A at pos5): C’s after pos5 within window at pos7 → 1 occurrence.
• i=8 (A at pos8): no later C in window → 0.
Total occurrences = 2 + 1 + 0 = 3.
Answer: Count(⟨A→C⟩) in sliding window = 3.
Damped (Time-Decay) Window Problems (recent items weighted higher)
We use exponential decay weights: each item at time t_i has weight ( w_i =
2^{-\lambda (T - t_i)} ) where T is current time, λ > 0 is the decay rate.
Weighted support = sum of weights for that item (often normalized by sum of
all weights or compared to a weighted threshold).
Problem D1 (easy — single item, compute weighted count)
Items with arrival times (time units):
Time 1: A
Time 2: B
Time 3: A
Current time T = 4. Use λ = 1. Compute weighted count of A at time T
(weights = (2^{-\lambda (T-t)})).
Solution
Compute weights for each A occurrence:
• A at t=1 → weight = (2^{-1*(4-1)} = 2^{-3} = 1/8 = 0.125).
• A at t=3 → weight = (2^{-1*(4-3)} = 2^{-1} = 1/2 = 0.5).
Weighted count(A) = 0.125 + 0.5 = 0.625.
(If you want normalized support, compute total weight of all items: B at t=2
weight = (2^{-(4-2)} = 2^{-2} = 0.25). Total weight = 0.625 + 0.25 = 0.875.
Normalized support(A) = 0.625 / 0.875 ≈ 0.7143.)
Answer: Weighted count(A)=0.625. Normalized weighted support ≈ 71.43%.
Problem D2 (medium — compare two items)
Events with times:
t=1: A
t=2: A
t=3: B
t=5: B
Current time T = 6. Use λ = 0.5 (slower decay). Compute weighted counts of
A and B at T and determine which is heavier.
Solution
Weight formula: (w = 2^{-\lambda (T - t)}) with λ=0.5.
Compute weights:
For A:
• t=1 → w = (2^{-0.5*(6-1)} = 2^{-0.5*5} = 2^{-2.5}).
o (2^{2.5} = 2^{2} * 2^{0.5} = 4 * 1.41421356 ≈ 5.656854).
o So (2^{-2.5} ≈ 1 / 5.656854 ≈ 0.1767767).
• t=2 → w = (2^{-0.5*(6-2)} = 2^{-0.5*4} = 2^{-2} = 0.25).
Weighted count(A) = 0.1767767 + 0.25 = 0.4267767 ≈ 0.42678.
For B:
• t=3 → w = (2^{-0.5*(6-3)} = 2^{-0.5*3} = 2^{-1.5}).
o (2^{1.5} = 2 * sqrt(2) ≈ 2 * 1.41421356 = 2.8284271).
o So (2^{-1.5} ≈ 1 / 2.8284271 ≈ 0.3535534).
• t=5 → w = (2^{-0.5*(6-5)} = 2^{-0.5*1} = 2^{-0.5} ≈ 0.70710678).
Weighted count(B) = 0.3535534 + 0.70710678 = 1.06066018 ≈ 1.06066.
Comparison: B (≈1.06066) > A (≈0.42678).
Answer: Weighted counts ≈ A:0.42678, B:1.06066 → B is heavier.
Problem D3 (harder — weighted frequent itemset decision)
Transactions with timestamps (each transaction is a set):
• t=1: {A,B}
• t=2: {A}
• t=4: {B}
• t=5: {A,B,C}
Current time T = 7. Use λ = 0.7. Compute weighted support for itemset {A,B} where
we define the weight of a transaction as (w_t = 2^{-\lambda (T - t)}); the weighted
support of an itemset is the sum of weights of transactions that contain the itemset.
Determine if {A,B} is frequent under weighted threshold θ = 0.3 where normalized
weighted support = (sum weights of transactions containing {A,B}) / (sum weights of
all transactions) and must be ≥ θ.
Solution
First compute transaction weights w_t:
Compute for each t:
• t=1 → w1 = (2^{-0.7*(7-1)} = 2^{-0.7*6} = 2^{-4.2}).
o (2^{4.2} = 2^{4} * 2^{0.2} = 16 * 2^{0.2}.)
(2^{0.2} ≈ e^{0.2 * ln2} ≈ e^{0.138629} ≈ 1.1487.)
So (2^{4.2} ≈ 16 * 1.1487 ≈ 18.3792.)
Thus w1 ≈ 1 / 18.3792 ≈ 0.054372.
• t=2 → w2 = (2^{-0.7*(7-2)} = 2^{-0.7*5} = 2^{-3.5}).
o (2^{3.5} = 2^{3} * 2^{0.5} = 8 * 1.41421356 = 11.3137085.)
w2 ≈ 1 / 11.3137085 ≈ 0.08838835.
• t=4 → w4 = (2^{-0.7*(7-4)} = 2^{-0.7*3} = 2^{-2.1}).
o (2^{2.1} = 2^{2} * 2^{0.1} = 4 * 2^{0.1}.)
(2^{0.1} ≈ e^{0.1 ln2} ≈ e^{0.0693147} ≈ 1.07177.)
So (2^{2.1} ≈ 4 * 1.07177 ≈ 4.28708.)
w4 ≈ 1 / 4.28708 ≈ 0.233232.
• t=5 → w5 = (2^{-0.7*(7-5)} = 2^{-0.7*2} = 2^{-1.4}).
o (2^{1.4} = 2^{1} * 2^{0.4} = 2 * 2^{0.4}.)
(2^{0.4} ≈ e^{0.4 ln2} ≈ e^{0.277259} ≈ 1.31951.)
So (2^{1.4} ≈ 2 * 1.31951 ≈ 2.63902.)
w5 ≈ 1 / 2.63902 ≈ 0.378924.
Now total weight = w1 + w2 + w4 + w5.
Compute sums (keep accuracy):
• w1 ≈ 0.054372
• w2 ≈ 0.08838835
Sum after two = 0.054372 + 0.08838835 = 0.14276035
• w4 ≈ 0.233232
Sum = 0.14276035 + 0.233232 = 0.37599235
• w5 ≈ 0.378924
Total weight W_total ≈ 0.37599235 + 0.378924 = 0.75491635
Now transactions containing {A,B} are t=1 ({A,B}) and t=5 ({A,B,C}) and
t=4 has {B} only (no A), t=2 has {A} only. So relevant transactions: t1 and t5.
Sum weights for {A,B} = w1 + w5 = 0.054372 + 0.378924 = 0.433296.
Normalized weighted support = 0.433296 / 0.75491635 ≈ compute:
Divide: 0.433296 ÷ 0.75491635.
Let's compute carefully:
0.75491635 * 0.57 = 0.430302. Difference to 0.433296 ≈ 0.002994 -> add
~0.004. Try 0.574: 0.75491635*0.574 = 0.433318... that's slightly above. So
ratio ≈ 0.57398 ≈ 57.40%.
More precisely: 0.433296 / 0.75491635 ≈ 0.57398.
Compare with θ = 0.3 → 0.574 ≥ 0.3 → frequent.
Answer: Normalized weighted support ≈ 0.574 (57.4%) → {A,B} is frequent
under θ = 0.3.