A support-ordered trie for fast frequent itemset discovery

• Main Authors: LIM, Ee Peng, WOON, Yew-Kwong, NG, Wee-Keong
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2004
• Subjects: Association rule mining; Data mining; Data structures; Databases and Information Systems; Numerical Analysis and Scientific Computing
• Online Access: https://ink.library.smu.edu.sg/sis_research/123; https://ink.library.smu.edu.sg/context/sis_research/article/1122/viewcontent/Support_ordered_trie_for_fast_frequent_itemset_discovery.pdf
• Institution: Singapore Management University

The importance of data mining is apparent with the advent of powerful data collection and storage tools; raw data is so abundant that manual analysis is no longer possible. Unfortunately, data mining problems are difficult to solve and this prompted the introduction of several novel data structures to improve mining efficiency. Here, we critically examine existing preprocessing data structures used in association rule mining for enhancing performance in an attempt to understand their strengths and weaknesses. Our analyses culminate in a practical structure called the SOTrielT (support-ordered trie itemset) and two synergistic algorithms to accompany it for the fast discovery of frequent itemsets. Experiments involving a wide range of synthetic data sets reveal that its algorithms outperform FP-growth, a recent association rule mining algorithm with excellent performance, by up to two orders of magnitude and, thus, verifying its' efficiency and viability.