Dr. Sumeet Dua

Max P. and Robbie L. Watson Eminent Scholar Chair

  • Full Screen
  • Wide Screen
  • Narrow Screen
  • Increase font size
  • Default font size
  • Decrease font size

Yifei Long (2004)

E-mail Print PDF

Efficient and Flexible Update of Association Rules in Growing Databases; MS-CS Thesis; Student: Yifei Long (2004)

Efficient association rule discovery in large databases has attracted a great deal of interest, especially in recent years. Although a significant amount of research effort has been evidenced in the development of novel methodologies for the discovery of association rules from large databases, the importance of updating these rules in growing databases has not been sufficiently discussed in the literature. The problem is complex because database growth can introduce new rules and invalidate some that have been previously discovered. It is not computationally efficient to run the rule discovery algorithm from scratch on the new database for even some minuscule changes in the old database, but a strategy to dynamically update the rule set with database growth is useful in real-time and high-dimensional data mining applications.
In this thesis, we have proposed a novel and efficient algorithm called Dynamic-Update for the incremental update of association rules when new transactions are added to a large database. The proposed algorithm scans the old database exactly once in contrast to some of the previous results in this area. Additionally, the minimum support required for association rule discovery can be flexible. We also propose a new methodology called ExtremePrune to prune the candidate itemsets as early as possible during the course of the incremental rule discovery process. The algorithm is also demonstrated to have significantly improved time performance relative to the previously reported results in this area.

You are here: Research Student Thesis