@inproceedings{ han00mining,Motivation:
author = "Jiawei Han and Jian Pei and Yiwen Yin",
title = "Mining frequent patterns without candidate generation",
booktitle = "2000 ACM SIGMOD Intl. Conference on Management of Data",
month = "05",
publisher = "ACM Press",
editor = "Weidong Chen and Jeffrey Naughton and Philip A. Bernstein",
isbn = "1-58113-218-2",
pages = "1--12",
year = "2000",
url = "citeseer.ist.psu.edu/han99mining.html",
url = "citeseer.nj.nec.com/han99mining.html" }
To address apriori-like algorithms' combinational limitation.
Contributions:
Proposed data structure FP-tree, which is a compact representation of the database, without loss of frequent pattern information; also proposed FP-Growth algorithm to mine frequent patterns on FP-tree.
Methods:
FP-tree make database compact by prefix sharing.
FP-grows use a divide-and-conquer technique to divide fp-mining at each stage k into 1-item mining and k-1 item mining.
Discussions:
Though experiment result in paper showed that FP-tree and FP-growth greatly improved storage and computation efficient. There was no in-depth complexity analysis in the paper.