Data Stream Processing Research at IMC of East China Normal University

摘要

Data stream processing has been attracting more and more attention in research and industry communities due to its broad potential applications. In this talk, we would like to introduce briefly the research work which have been done in our group. Our research interests on data streams are frequent item(set)s mining, clustering, and burst detection over data streams. Some work on practical application and some consideration on future work will be introduced as well.For the basic problem of mining frequent items over data streams, an algorithm, called hCount is proposed. It is of low space complexity, low per-tuple processing cost, and high recall and precision. Then, for mining of the frequent itemsets, we develop a new false-negative frequent itemset mining algorithm which can get a condensed representation of frequent itemsets in transactional data streams by discovering a false negative collection of some special itemsets that covers frequent itemsets with high probability with respect to set inclusion relationship among itemsets.Our research on data stream mining was focusing on clustering of data streams. SWClustering is the algorithm we proposed to cluster data streams over sliding windows, and EHCF (Exponential Histogram of Cluster Features) is the synopsis to maintain the statistic information of clusters in sliding windows. With SWClustering, not only the changing distribution of clusters but also the evolving behaviors of individual clusters could be captured. CluDistream is for clustering distributed data streams, which can effectively handle a huge volume of data with noisy, corrupted or incomplete data records generated in distributed enviornment. In CluDistream, the EM-based (Expectation Maximization) algorithms, each data record is assigned to a cluster with certain degree of membership.The other important piece of work is on burst detection or monitoring over data streams. The fractal analysis method is adapted to enable the monitoring of both monotonic and non-monotonic aggregates on time changing data stream. The monotony property of aggregate monitoring is revealed and monotonic search space is built to decrease the time overhead for detecting bursts from O(m) to O(log m), where m is the number of windows to be monitored. With the help of a novel piecewise fractal model, the statistical summary is compressed to be fit in limited main memory, so that high aggregates on windows of any length can be detected accurately and efficiently on-line.A practical data stream processing system for telecommunication network flow data analysis will be also introduced in this talk.