Aravind Kalavagattu's Defense

Mining Approximate Functional Dependencies as Condensed Representations of Association Rules
Student Defense
Date: July 30, 2008
Time: 10:00 AM - 12:00 PM

Contact Person: Aravind Krishna Kalavagattu
Contact Email: aravindk@asu.edu
Location: BYENG 420
Defense Type: Master's Thesis Defense
Committee Members: Prof. Subbarao Kambhampati

Approximate Functional Dependencies (AFD) mined from database relations represent potentially interesting patterns and have proven to be useful for various tasks like feature selection for classification, query optimization and query rewriting. Though the discovery of Functional Dependencies (FDs) from a relational database is a well studied problem, the discovery of AFDs still remains under explored, posing a special set of challenges. Such challenges include defining right interestingness measures for AFDs, employing effective pruning strategies and performing an efficient traversal in the search space of the attribute lattice. This thesis presents a novel perspective for AFDs as condensed representations of association rules; for example, an AFD (Model=>Make) is a condensation of various association rules like, (Model:Accord=>Make:Honda), (Model:Camry=>Make:Toyota). In this regard, this thesis describes two metrics, namely Confidence and InfoSupport analogous to the standard metrics confidence and support used in association rules respectively. This thesis presents an algorithm called AFDMiner for efficiently mining high quality AFDs by employing effective pruning strategies. AFDMiner performs a bottom-up search in the attribute lattice to find all AFDs and FDs that fall within the given Confidence and InfoSupport thresholds. Experiments on real data sets show the effectiveness of the approach both in terms of performance as well as the quality of AFDs generated.