Memory- and knowledge-conscious data mining
Srinivasan Parthasarathy, Amol Ghoting · 2007
Advances in data collection and storage technologies have allowed organizations to gather, collect, and distribute increasing amounts of data. Spurred by these advances, the field of knowledge discovery in databases has emerged, merging ideas from statistics, machine learning, databases, and high performance computing. The main challenge in the knowledge discovery process is to extract knowledge and insight from massive data sets in a fast and efficient manner. This process is iterative in nature and involves a human in the loop. Therefore, to facilitate effective data understanding and knowledge discovery, it is imperative that one minimizes response time to a user's query. To address this challenge, over the past decade, research efforts have largely focused on reducing the computation required to process a single data mining query. However, simply pursuing this direction is insufficient. In this dissertation, we will explore two new directions to improve the performance of data mining algorithms. The first direction attempts to improve performance by understanding and then improving the memory system performance of data mining algorithms. The second direction attempts to improve performance by redesigning a data mining algorithm such that it reuses computation. Specifically, we make the following contributions. In the context of memory aware data mining, first, we present results of our study that delves into the memory system performance of data mining algorithms that are designed to operate over static data sets. Second, using the knowledge gleaned in the above investigation, we look at improving the cache performance of frequent pattern mining algorithms, a popular class of data mining algorithms. We expect that the presented methodology will be useful in improving the performance of other data mining algorithms as well. Third, a scheduling scheme that is cognizant of the trade-off between response time and memory usage, when processing and mining distributed and dynamic data sets, is presented. This scheme allows us to better use the memory system when mining distributed and dynamic data sets. In the context of knowledge-conscious data mining, first, we show how one can redesign exploratory kMeans clustering such that it can expose and reuse repeated computation across iterations of a single kMeans query and multiple kMeans queries. Second, we present the design of a knowledge caching service for data mining algorithms. This service is easy to use (in terms of programming effort), scalable, and allows for the reuse of computation across multiple users of a data mining system.