---
title: "FP-Growth and Apriori disadvantage"
subject: "Data Mining"
chapter: 4
key: "semester_7/data_mining:fp-growth-vs-apriori"
source: https://www.bctengineer.com/q/semester_7/data_mining/fp-growth-vs-apriori
site: BCT Engineering
---

# FP-Growth and Apriori disadvantage

Data Mining · Chapter 4: Association Analysis

- Asked in: year not given
- Video: [FP growth Vs Apriori Algorithm|FP growth tree vs Apriori algorithm in frequent pattern mining](https://www.youtube.com/watch?v=qaTC0Y_evbk) — Unfold Data Science
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_7/data_mining/fp-growth-vs-apriori
- Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4

## Question

Define FP-Growth algorithm for frequent item set generation. Explain how FP growth approach overcomes the disadvantage of Apriori algorithm.

## Short answer

FP-growth builds an FP-tree from two database scans, then recursively mines conditional FP-trees without candidate generation. Overcomes Apriori by: no candidate generation, only two scans, counts stored in tree, compresses data via shared prefixes, divide-and-conquer for long patterns. Much faster, especially at low support.

## Answer

**FP-growth** (Frequent Pattern growth, Han, Pei and Yin) finds frequent itemsets **without candidate generation**. It compresses the database into a compact prefix tree, the **FP-tree**, and then mines the tree recursively by a divide-and-conquer pattern-growth method.

#### Algorithm
1. **Scan 1**: find the support count of each item; delete infrequent items; sort the frequent items in descending order of count (the *F-list*).
2. **Build the FP-tree**: scan 2: for each transaction, sort its frequent items by the F-list order and insert it as a path from the root. Shared prefixes share nodes (count is increased); a **header table** links all nodes of the same item (node-links).
3. **Mine** the tree, for each item from the least frequent upward:
   - take its **conditional pattern base** (prefix paths leading to the item, with the item's counts);
   - build a **conditional FP-tree** from it (drop items below min_sup);
   - recursively mine it, appending the item as the suffix.
4. Union of all patterns is the set of frequent itemsets.

#### How it overcomes the disadvantages of Apriori
| Apriori problem | FP-growth solution |
| --- | --- |
| Generates huge numbers of candidate itemsets | **No candidate generation**; patterns grow from frequent items in the tree |
| Scans the database many times (k scans) | Only **two scans** of the database |
| Counts candidates against every transaction | Counts are kept in the tree; mining works on the compact tree in memory |
| Large memory/time with dense data or low support | The tree **compresses** the data (shared prefixes), so mining is much faster |
| Level-wise search for long patterns is costly | Divide-and-conquer decomposes the problem into smaller conditional databases |

Experiments show FP-growth is about an order of magnitude faster than Apriori for low min_sup.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the key feature of FP-growth?
   A. It finds frequent itemsets without candidate generation using a compact FP-tree
   B. It generates candidates level by level
   C. It uses clustering to group items
   D. It needs one scan per level
   Answer: A. It compresses the database into a prefix tree and mines it recursively. (Key point: Definition)

2. How many database scans does FP-growth need?
   A. One per itemset size
   B. Two
   C. One
   D. As many as there are items
   Answer: B. Scan 1 counts items; scan 2 builds the tree. (Key point: Database scans)

3. How are the items of each transaction ordered before inserting into the tree?
   A. Alphabetically, keeping all items
   B. In ascending order of support
   C. In descending order of support count (F-list), after dropping infrequent items
   D. In order of arrival
   Answer: C. Descending order maximises prefix sharing so the tree is compact. (Key point: F-list)

4. How is the FP-tree mined?
   A. From the root downward with candidate counting
   B. By joining L_k with itself
   C. By randomly sampling the tree
   D. From the least frequent item upward, using conditional pattern bases and conditional FP-trees
   Answer: D. For each item, prefix paths form its conditional pattern base, from which a conditional FP-tree is built and mined recursively. (Key point: Mining order)

## Related in Data Mining

- [FP-Growth advantages and disadvantages](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-growth-pros-cons) — Data Mining, chapter 4
- [FP-tree on HotDogs data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-hotdogs) — Data Mining, chapter 4
- [FP-tree on t1-t5 data](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Afp-tree-t1-t5) — Data Mining, chapter 4
- [Apriori on 8 transactions, 25% support](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-b65-transactions) — Data Mining, chapter 4
- [Apriori on HotDogs data with rules](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aapriori-hotdogs-rules) — Data Mining, chapter 4
- [Association analysis and Apriori pruning](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aassociation-apriori-pruning) — Data Mining, chapter 4, asked 2×

## Related in other subjects

- [Advantages and disadvantages of DTMF set](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Adtmf-advantages-disadvantages) — Telecommunications, chapter 1
- [Variational approach for one-dimensional heat conduction](https://www.bctengineer.com/question.md?key=semester_8%2Ffinite_element_method%3Avariational-approach-heat-conduction) — Finite Element Method, chapter 5
- [Importance of growth function; Theta, O, Omega](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Agrowth-function-importance) — Data Structure and Algorithm, chapter 9
- [Fit y = a b^x (growth data)](https://www.bctengineer.com/question.md?key=semester_4%2Fnumerical_method%3Afit-y-abx-d2) — Numerical Method, chapter 4