Skip to content
Back to search results

FP-Growth (Frequent Pattern Growth)

Introduced by
Jiawei Han, Jian Pei & Yiwen Yin
Year
2000
Type
Frequent-itemset mining algorithm
Family
Pattern mining
Font size

What does it do?

FP-Growth, introduced by Jiawei Han, Jian Pei, and Yiwen Yin in 2000, mines frequent itemsets from transaction data without generating candidate sets, the costly step that slows the classic Apriori algorithm.

It compresses the database into a frequent-pattern tree (FP-tree) in two scans, then grows frequent patterns recursively from that structure, making it dramatically faster than Apriori on large, dense datasets.

The intuition behind the method

Apriori finds frequent itemsets by repeatedly generating and testing candidate combinations — an expensive, scan-heavy process that explodes on dense data. FP-Growth takes a different route: it squeezes the whole transaction database into a compact tree where shared prefixes are stored once, so common patterns overlap and compress. Then, instead of generating candidates, it reads frequent patterns directly out of the tree by following the paths that lead to each item and recursively mining smaller 'conditional' trees. Two passes over the data and a clever data structure replace Apriori's many passes and combinatorial candidate blow-up.

History

Han, Pei, and Yin presented FP-Growth at SIGMOD 2000 as a candidate-generation-free alternative to Apriori, with an expanded treatment in their 2004 Data Mining and Knowledge Discovery article. The frequent-pattern tree idea — compressing transactions into a shared prefix structure and mining it recursively — became a foundational technique in pattern mining, alongside Apriori (candidate-based) and ECLAT (vertical-format). It remains a standard, high-performance itemset miner in data-mining libraries.

When to use it

Use FP-Growth to mine frequent itemsets (and, downstream, association rules) from transactional data — market-basket analysis, web-usage and clickstream mining, recommendation, and bioinformatics co-occurrence — especially on large or dense datasets where Apriori's candidate generation is too slow. It needs only two database scans and typically far outperforms Apriori. Its costs: the FP-tree must fit in memory (a limitation for very large or extremely sparse data, where the tree compresses poorly), the recursion can be intricate to implement, and like all support-based mining it is sensitive to the minimum-support threshold (too low explodes the output, too high misses patterns). ECLAT (vertical tidset intersection) is an alternative; for the rules themselves, pair with association-rule generation.

Limitations and considerations

  • The FP-tree must fit in memory; very large datasets may not.
  • On sparse data the tree compresses poorly, eroding the advantage.
  • Recursive conditional-tree construction is comparatively complex to implement.
  • Sensitive to the minimum-support threshold, like all frequent-itemset mining.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • No candidate generation — far faster than Apriori on large/dense data.
  • Only two database scans, regardless of pattern length.
  • The FP-tree compresses shared structure, saving memory and time on dense data.
  • Scales to long frequent patterns that overwhelm candidate-based methods.

Applications

  • Market-basket analysis and retail association mining.
  • Web-usage and clickstream pattern mining.
  • Recommendation via frequently co-occurring items.
  • Bioinformatics co-occurrence and motif discovery.
  • Any large-scale frequent-itemset task where Apriori is too slow.

How it works

How it works

1

A first database scan counts the support of each item and discards those below the minimum support threshold. The surviving frequent items are sorted by descending frequency — this ordering lets transactions share tree prefixes and keeps the FP-tree compact.

Formula
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}
2

A second scan inserts each transaction (its frequent items, in the sorted order) into the FP-tree, incrementing counts along shared prefix paths and adding new branches as needed. A header table links all occurrences of each item, so the tree compactly represents the whole dataset's frequent structure.

Formula
\text{second scan: insert each transaction's frequent items into the FP-tree}
3

For each frequent item (processed least-frequent first), the algorithm gathers its conditional pattern base — the set of prefix paths in the tree that co-occur with that item, each weighted by its count. This captures the context in which the item appears frequently.

Formula
\text{for each item: collect its conditional pattern base (prefix paths)}
4

From each conditional pattern base a smaller conditional FP-tree is built and mined recursively, growing longer frequent itemsets by appending the item to patterns found in its conditional tree. Recursion bottoms out at single-path trees, whose itemset combinations are enumerated directly — yielding all frequent itemsets with no candidate generation.

Formula
\text{build conditional FP-trees recursively to grow frequent patterns}

Common pitfalls

  • Setting minimum support too low, producing an explosion of itemsets.
  • Assuming it always beats Apriori — on small or sparse data the gain is modest.
  • Forgetting that frequent itemsets are not rules; rule generation is a separate step.
  • Overlooking memory limits when the FP-tree cannot be held in RAM.

Frequently asked questions

How is FP-Growth faster than Apriori?

Apriori repeatedly generates and tests candidate itemsets, scanning the database many times. FP-Growth avoids candidate generation entirely: it compresses the data into an FP-tree in two scans and mines patterns recursively from it. This removes the combinatorial candidate blow-up, giving large speedups on dense data.

What is the FP-tree?

A compressed prefix tree of the database's frequent items. Transactions sharing a prefix share a path, with node counts recording support, and a header table links each item's occurrences. It stores the dataset's frequent structure compactly so patterns can be read off without rescanning the data.

How does FP-Growth relate to ECLAT and association rules?

FP-Growth, ECLAT, and Apriori all find frequent itemsets; ECLAT uses a vertical tidset-intersection approach instead of a tree. Finding frequent itemsets is only the first stage — association rules (with confidence/lift) are generated from those itemsets in a separate step.

Related methods

Sources

  1. Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.

    Open DOI reference
    Copied.
  2. Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.

    Open DOI reference
    Copied.