1. A Scalable Algorithm for Constructing Frequent Pattern Tree
- Author
-
Zailani Abdullah, Mustafa Mat Deris, Tutut Herawan, and Ahmad Noraziah
- Subjects
Theoretical computer science ,Association rule learning ,Computer science ,Segment tree ,computer.software_genre ,Data structure ,Search tree ,Tree (data structure) ,Trie ,Scalability ,sort ,Decision Sciences (miscellaneous) ,Data mining ,computer ,Information Systems - Abstract
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.
- Published
- 2014