Title

A Support-Ordered Trie for Fast Frequent Itemset Discovery

Publication Type

Journal Article

Publication Date

2004

Abstract

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.

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Research Areas

Data Management and Analytics

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

16

Issue

7

First Page

875

Last Page

879

ISSN

1041-4347

Identifier

10.1109/TKDE.2004.1318569

Publisher

IEEE

Additional URL

http://dx.doi.org/10.1109/TKDE.2004.1318569