Abstract
In recent times, data in many applications are generated as a form of continuous data streams. Since handling data streams is necessary and discovering knowledge behind data streams can often yield substantial benefits, mining over data streams has become one of the most important issues. Many approaches for mining frequent itemsets over a single data stream have been proposed. However, in many applications, multiple data streams generated at distributed remote sites may exist. In this dissertation, we concentrate on the problem of mining global frequent itemsets over a collection of data streams distributed at distinct remote sites. Instead of collecting and processing all the data in a central server, wasting computation resources of the remote sites, distributed computations over the data streams are performed. Moreover, to further speed up the mining process and provide more flexibility for the mining requests, we make the first attempt to address a new problem on continuously maintaining the global synopsis at the central server (named coordinator) for the union of all the distributed data streams under the condition that each remote site maintains its own local synopsis for the local stream it monitors. The global frequent itemsets therefore can be yielded on demand by directly processing the global synopsis. We propose a distributed computation framework to deal with the problem of continuously maintaining the global synopsis in this dissertation, which composes of two main works: 1) designing a local synopsis to summarize the local stream (equal to solving the problem of mining frequent itemsets over a single data stream) and 2) devising communication strategies and a merging operation rooted in the newly designed synopsis to achieve the goal of continuous maintenance. Since most of the existing approaches on mining frequent itemsets over a single data stream assume that the synopses of data streams can be saved in memory and ignore the fact that information of non-frequent itemsets kept in the synopses may cause memory utilization to be significantly degraded, we therefore consider compressing the information of all itemsets into a structure with a fixed size using a hashing technique and then propose a hash-based approach operating in an online-processing mode that processes the current transaction immediately for mining frequent itemsets over a single data stream. This hash-based approach skillfully summarizes the information of the whole data stream by using a hash table, provides a novel technique to estimate support counts of non-frequent itemsets, and keeps only the frequent itemsets for speeding up the mining process. Thereafter, based on the newly designed synopsis used in our hash-based approach over a single data stream, two communication strategies are designed for the distributed computation framework according to an accuracy guarantee of mining results, which decide when and what the remote sites should transmit to the coordinator. Moreover, a suitable merging operation is also proposed for merging the information received from the remote sites into the global synopsis maintained at the coordinator. By the strategies and merging operation, the goal of continuously maintaining the global synopsis for efficient global frequent itemset mining can therefore be achieved. The correctness guarantees of all the proposed algorithms and the accuracy guarantee analysis of the distributed computation framework are presented. A series of experiments on synthetic datasets and a real dataset are also performed to show the effectiveness and efficiency of the hash-based approach over a single data stream and those of the distributed computation framework over distributed data streams.