An efficient approach to discovering knowledge from large databases

Graph based algorithms construct an association graph to indicate the associations between items and then traverse the graph to generate large itemsets and large sequences, respectively are presented.

Abstract

We study two problems: mining association rules and mining sequential patterns in a large database of customer transactions. The problem of mining association rules focuses on discovering large itemsets where a large itemset is a group of items which appear together in a sufficient number of transactions; while the problem of mining sequential patterns focuses on discovering large sequences where a large sequence is an ordered list of sets of items which appear in a sufficient number of transactions. We present efficient graph based algorithms to solve these problems. The algorithms construct an association graph to indicate the associations between items and then traverse the graph to generate large itemsets and large sequences, respectively. Our algorithms need to scan the database only once. Empirical evaluations show that our algorithms outperform other algorithms which need to make multiple passes over the database.