Approximation and learning techniques in database systems
Min Wang, Jeffrey Scott Vitter · 1999
In this thesis, we study two important techniques that are widely used in database systems: approximation and learning. Approximation has been an area of great interest and importance in database community. A classic example of using approximation in database systems is selectivity estimation. Another example is using approximation techniques to answer OLAP (On-Line Analytical Processing) queries, which is quite new and is initiated by our work. In this thesis, we propose novel approximation techniques used in both selectivity estimation and approximate computation of OLAP aggregates. Our techniques are based on the powerful mathematical tool of wavelets and multiresolution analysis and are fundamentally different from traditional approaches. We present several methods that first attempt to use wavelets in the domain of database approximation. Our methods offer substantial improvements in accuracy and efficiency over existing methods. We also develop efficient and scalable learning techniques for DBMSs to extract patterns from large databases in the context of data mining. Classification is an important and fundamental data mining problem. Almost all of the current classification algorithms have the restriction that the entire training set should fit in the internal memory to achieve efficiency. We present a novel classification algorithm (classifier) called MIND (MINing in Databases). MIND is scalable with respect to I/O efficiency, which is important since scalability is a key requirement for any data mining algorithm.