A Scalable Algorithm for Constructing Frequent Pattern Tree

• Main Authors: Noraziah, Ahmad, Herawan, Tutut, Zailani, Abdullah, Mustafa, Mat Deris
• Format: Article
• Language: English
• Published: IGI Global 2014
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://umpir.ump.edu.my/id/eprint/6623/1/fskkp-2014-noraziah-Scalable_algorithm.pdf; http://umpir.ump.edu.my/id/eprint/6623/; http://dx.doi.org/10.4018/ijiit.2014010103

Frequent Pattern Tree (FP-Tree) is a compact data structure of representing frequent itemsets. The construction of FP-Tree is very important prior to frequent patterns mining. However, there have been too limited efforts specifically focused on constructing FP-Tree data structure beyond from its original database. In typical FP-Tree construction, besides the prior knowledge on support threshold, it also requires two database scans; first to build and sort the frequent patterns and second to build its prefix paths. Thus, twice database scanning is a key and major limitation in completing the construction of FP-Tree. Therefore, this paper suggests scalable Trie Transformation Technique Algorithm (T3A) to convert our predefined tree data structure, Disorder Support Trie Itemset (DOSTrieIT) into FP-Tree. Experiment results through two UCI benchmark datasets show that the proposed T3A generates FP-Tree up to 3 magnitudes faster than that the benchmarked FP-Growth.