文献类型：期刊文献

英文题名：Tracking clusters in evolving data streams over sliding windows

作者：Zhou, Aoying[1];Cao, Feng[1,2];Qian, Weining[1];Jin, Cheqing[1,3]

机构：[1]Fudan Univ, Dept Comp Sci & Engn, Shanghai 200433, Peoples R China;[2]IBM China Res Lab, Beijing 100094, Peoples R China;[3]E China Univ Sci & Technol, Dept Comp Sci, Shanghai 200237, Peoples R China

年份：2008

卷号：15

期号：2

起止页码：181

外文期刊名：KNOWLEDGE AND INFORMATION SYSTEMS

收录：;EI(收录号：20211810283505);WOS:【SCI-EXPANDED(收录号:WOS:000255680300003)】；

语种：英文

外文关键词：cluster tracking; evolving; data streams; sliding windows

摘要：Mining data streams poses great challenges due to the limited memory availability and real-time query response requirement. Clustering an evolving data stream is especially interesting because it captures not only the changing distribution of clusters but also the evolving behaviors of individual clusters. In this paper, we present a novel method for tracking the evolution of clusters over sliding windows. In our SWClustering algorithm, we combine the exponential histogram with the temporal cluster features, propose a novel data structure, the Exponential Histogram of Cluster Features (EHCF). The exponential histogram is used to handle the in-cluster evolution, and the temporal cluster features represent the change of the cluster distribution. Our approach has several advantages over existing methods: (1) the quality of the clusters is improved because the EHCF captures the distribution of recent records precisely; (2) compared with previous methods, the mechanism employed to adaptively maintain the in-cluster synopsis can track the cluster evolution better, while consuming much less memory; (3) the EHCF provides a flexible framework for analyzing the cluster evolution and tracking a specific cluster efficiently without interfering with other clusters, thus reducing the consumption of computing resources for data stream clustering. Both the theoretical analysis and extensive experiments show the effectiveness and efficiency of the proposed method.