On performance of data mining: from algorithms to management systems for data exploration
Paolo Palmerini · 2004
Data Mining (DM) is the science of extracting useful and non-trivial information from the huge amounts of data that is possible to collect in many and diverse fields of science, business and engineering. Due to its relatively recent development, Data Mining still poses many challenges to the research community. New methodologies are needed in order to mine more interesting and specific information from the data, new frameworks are needed to harmonize more effectively all the steps of the mining process, new solutions will have to manage the complex and heterogeneous source of information that is today available for the analysts. A problem that has always been claimed as one of the most important to address, but has never been solved in general terms, is about the performance of DM systems. Reasons for this concern are: (i) size and distributed nature of input data; (ii) spatio temporal complexity of DM algorithms; (iii) quasi real-time constraints imposed by many applications. When it is not possible to control the performance of DM systems, the actual applicability of DM techniques is compromised. In this Thesis we focused on the performance of DM algorithms, applications and systems. We faced this problem at different levels. First we considered the algorithmic level. Taking a common DM task, namely Frequent Set Counting (FSC), as a case study, we performed an in depth analysis of performance issues in FSC algorithms. This led us to devise a new algorithm for solving the FSC problem, that we called Direct Count and Intersect (DCI). We also proposed a more general characterization of transactional datasets that allow to forecast, within a reasonable range of confidence, important properties in the FSC process. From preliminary studies, it seems that measuring the entropy of a dataset can provide useful hints on the actual complexity of the mining process on such data. Performance of DM systems is particularly important for those system that have strong requirements in terms of response time. Web servers are a notable example of such systems: they produce huge amounts of data at different levels (access log, structure, content). If mined effectively and efficiently, the knowledge extracted from these data can be used for service personalization, system improvement or site modification. We illustrate the application of DM techniques to the web domain and propose a DM system for mining web access log data. The system is designed to be tightly coupled with the web server and process the input stream of http requests in an on-line and incremental fashion. Due to the intrinsically distributed nature of the data being mined and by the commonly claimed need for high performance, parallel and distributed architectures often constitute the natural platform for data mining applications. We parallelized some DM algorithms, most notably the DCI algorithm. We designed a multilevel parallel implementation of DCI, explicitly targeted at the execution on cluster of SMP nodes, that adopts multithreading for intra node and message passing for the inter node communications. To face the problems of resource management, we also study the architecture of a scheduler that maps DM applications onto large scale distributed environments, like Girds. We devised a strategy to predict the execution time of a generic DM algorithm and a scheduling policy that effectively takes into account the cost of transferring data across distributed sites. The specific results obtained in studying single DM kernels or applications can be generalized to wider classes of problems that allows the data miner to abstract from the architectural details of the application (physical interaction with the data source, base algorithm implementation) and concentrate only on the mining process. Following this generic thinking, a Data Mining Template Library (DMTL) for frequent pattern mining was designed at the Rensselaer Polytechnic Institute, Troy (NY) USA, under the supervision of prof. M. J. Zaki. We joined the DMTL project during 2002 fall. We present the main features of DMTL and a preliminary experimental evaluation.