Association rule mining: A graph based approach for mining frequent itemsets

Most of studies for mining frequent patterns are based on constructing tree for arranging the items to mine frequent patterns. Many algorithms proposed recently have been motivated by FP-Growth (Frequent Pattern Growth) process and uses an FP-Tree (Frequent Pattern Tree) to mine frequent patterns. This paper introduces an algorithm called FP-Growth-Graph which uses graph instead of tree to arrange the items for mining frequent itemsets. The algorithm contains three main parts. The first is to scan the database only once for generating graph for all item. The second is to prune the non-frequent items based on given minimum support threshold and readjust the frequency of edges, and then construct the FP_graph. The benefit of using graph structure comes in the form of space complexity because graph uses an item as node exactly once rather than two or more times as was done in tree.