Dynamic Itemset Counting

(DIC) algorithm
Dr. Somrita Saha
Origin of the Idea
• The Dynamic Itemset Counting (DIC) algorithm is a clever middle ground
between the "rigid levels" of Apriori and the "all-at-once" approach of FP-
Growth.

• It was designed to reduce the number of database scans by adding new

candidates on the fly as soon as enough evidence is gathered.

• If Apriori is like a train that only lets people board at specific stations (levels), DIC
is like a bus that lets people hop on at any stop along the route.
The Core Innovation: "Start Early"
• In Apriori, counting all 1-itemsets must be finished before we can even propose 2-
itemsets. DIC breaks this rule.

• It divides the database into intervals (blocks). Once an itemset has been seen
"enough" times within a few blocks, DIC doesn't wait for the end of the full
database scan; it immediately starts counting its supersets (larger combinations)
in the remaining blocks.
The Four States of an Itemset
• DIC tracks every itemset using a "state machine." Understanding
these four states is the key to the algorithm:
State Description

Solid Square Confirmed Frequent: We have finished a full scan, and it passed the threshold.

Solid Circle Confirmed Infrequent: We have finished a full scan, and it failed the threshold.

Dashed Square Suspected Frequent: We are still counting, but it already looks like it will pass.

Dashed Circle Suspected Infrequent: We are still counting, and it currently looks like it will fail.
How the Algorithm "Flows"
1. Initialization: Start with all 1-itemsets as Dashed Circles (suspected infrequent)
and the rest of the world as nothing.
2. The Scan: Start reading the database in blocks (e.g., every 100 transactions).
3. The "Promotion": * As you count, if a Dashed Circle hits the support threshold,
it is promoted to a Dashed Square.
• The Magic Step: The moment an itemset becomes a Dashed Square, DIC immediately
generates all its possible supersets (e.g., if {A} and {B} are now squares, it creates {A, B}) and
starts counting them as Dashed Circles in the very next block.
4. The Finish Line: An itemset becomes Solid once it has been counted across the
entire database (one full lap).
Comparative Study: DIC vs. Apriori
Feature Apriori Algorithm DIC Algorithm

As soon as support is reached

Candidate Generation Only at the end of a full pass.
(dynamic).

Much fewer (often just 1.5 to 2

Database Scans Usually many (k scans).
scans).

Flexibility Static and rigid. Adaptive to the data.

Complexity Simple but slow. Complex state-tracking but fast.

An Illustrative Example
• Imagine a database of 1,000 transactions and a threshold of 100.
• At Transaction 0: We start counting {Bread} and {Milk}.
• At Transaction 300: We notice {Bread} and {Milk} both already have a count of
120. They are promoted to Dashed Squares.
• At Transaction 301: We don't wait for Transaction 1,000! We immediately add
{Bread, Milk} to our "to-count" list.
• By the time we finish the first pass, we already have a partial count for the pair.
We might only need a short partial second scan to confirm it, whereas Apriori
would require two full, separate scans.
Philosophy Behind DIC
• DIC basically "cheats" the clock. It uses the information it gains during a scan to
predict what it should look for later in that same scan.
Visualization of the Dynamic Itemset Counting
(DIC) process
• Let's follow a single itemset combination—{Bread, Milk}—as it moves
through the "State Machine" across a database divided into four
blocks (Intervals).
The State Transition Table:
Goal: Reach a support threshold of 100.
Interval (Block) Action Taken State of {Bread, Milk} Logic / Reasoning
The pair doesn't exist yet
because its parents
Start Initialize 1-itemsets. None
({Bread}, {Milk}) aren't
frequent yet.
Parents are still "Dashed
Block 1 (0-250) Count {Bread} and {Milk}. None
Circles."
Parents become "Dashed
Squares." DIC
Block 2 (251-500) Parents hit count 100. Dashed Circle (◯) immediately creates the
candidate {Bread, Milk}
and starts counting.
The State Transition Table: (Contd..)
Goal: Reach a support threshold of 100.
Interval (Block) Action Taken State of {Bread, Milk} Logic / Reasoning
We are collecting data for
Block 3 (501-750) Counting continues. Dashed Circle (◯) the pair in this specific
block.
The pair crossed the
threshold before the scan
Block 4 (751-1000) Count hits 110. Dashed Square (☐) finished! It's now a
"Suspected Frequent"
itemset.
We finish counting the
"missing" part of the
circle (the first 250 rows).
Wrap-around Second scan (0-250). Solid Square (■)
Now that it has been seen
by the whole DB, it's
"Solid."
The State Machine: A Visual "Cheat Sheet"
Lifecycle of a Candidate
1. Dashed Circle (◯): "I'm a new candidate. I'm currently being counted, but I'm
not a winner yet.“
2. Dashed Square (☐): "I've hit the threshold! I'm popular! Tell the algorithm to
start making my 'children' (supersets) right now.“
3. Solid Square (■): "I've been checked against every single row in the database. I
am officially a Frequent Itemset.“
4. Solid Circle (●): "I've been checked against the whole database, and I didn't
make the cut. I'm officially Infrequent."
Why this saves time
• In a traditional Apriori approach, the pair {Bread, Milk} would have to wait until
the second full scan to even begin being counted.

• In DIC, because we noticed the parents were popular halfway through the first
scan, we started counting the pair early. By the time the first scan ended, we
were already 75% done with the count for the pair. We only needed to look at the
first block one more time to "seal the deal."
Think and Answer
• "If we have 10 blocks, and an itemset becomes a Dashed Square at Block 2, how
many blocks of 'extra' counting did we save compared to Apriori?"
Frequent Itemset Mining: The Big Four Comparison
Feature Apriori Partitioning FP-Growth DIC (Dynamic)

Level-by-level Build a compressed

Divide database into Add candidates on-
Primary Strategy candidate tree; mine
chunks; mine locally. the-fly during a scan.
generation. recursively.

Multiple (k scans for Often 1.5 to 2 scans

Database Scans Exactly 2 scans. Exactly 2 scans.
k-itemsets). (flexible).

Local Memory FP-Tree (Trie- State Machine

Data Structure Hash Trees / Lists.
Buffers. based). (Shapes).

Small, simple Massive, dense Reducing I/O

Large datasets that
Best Used For... datasets (Learning datasets (Industry overhead on large
don't fit in RAM.
basics). standard). datasets.

Heavy I/O; massive Can produce too High memory cost if Complex to
Weakness candidate many "False the tree is very implement and track
generation. Positive" candidates. sparse. states.
Key Takeaways
1. The "Candidate" Evolution:
• Apriori generates all candidates (Slow).
• DIC generates candidates sooner (Faster).
• FP-Growth generates no candidates (Fastest).
2. The "Memory" Evolution:
• Apriori fills memory with candidate lists.
• Partitioning solves this by only looking at one "slice" of data at a time.
• FP-Growth solves this by compressing the entire database into a single tree.
3. The "Scan" Evolution:
• If you have a 10-item pattern, Apriori scans the disk 11 times.
• Partitioning, FP-Growth, and DIC will usually do it in just 2.
Think and Answer
"If you were designing a recommendation engine for a massive streaming service
like Netflix (where data is distributed across many global servers), which algorithm
would you choose and why?"
Thank You!