Efficient clustering of uncertain data streams

• Published in: Knowledge and information systems 2014-09, Vol.40 (3), p.509-539
• Main Authors: Jin, Cheqing, Yu, Jeffrey Xu, Zhou, Aoying, Cao, Feng
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Cluster analysis; Clustering; Computer Science; Computer science; control theory; systems; Computer systems and distributed systems. User interface; Data analysis; Data Mining and Knowledge Discovery; Data processing. List processing. Character string processing; Data structures; Data transmission; Database Management; Datasets; Exact sciences and technology; Handles; High speed; Information Storage and Retrieval; Information systems; Information Systems and Communication Service; Information Systems Applications (incl.Internet); IT in Business; Location based services; Memory organisation. Data processing; Regular Paper; Software; Statistics; Studies; Uncertainty
• ISSN: 0219-1377; 0219-3116
• DOI: 10.1007/s10115-013-0657-3

Clustering uncertain data streams has recently become one of the most challenging tasks in data management because of the strict space and time requirements of processing tuples arriving at high speed and the difficulty that arises from handling uncertain data. The prior work on clustering data streams focuses on devising complicated synopsis data structures to summarize data streams into a small number of micro-clusters so that important statistics can be computed conveniently, such as Clustering Feature ( C F) (Zhang et al. in Proceedings of ACM SIGMOD, pp 103–114, 1996 ) for deterministic data and Error-based Clustering Feature ( E CF) (Aggarwal and Yu in Proceedings of ICDE, 2008 ) for uncertain data. However, E CF can only handle attribute-level uncertainty , while existential uncertainty , the other kind of uncertainty, has not been addressed yet. In this paper, we propose a novel data structure, Uncertain Feature ( U F), to summarize data streams with both kinds of uncertainties: U F is space-efficient, has additive and subtractive properties, and can compute complicated statistics easily. Our first attempt aims at enhancing the previous streaming approaches to handle the sliding-window model by using U F instead of old synopses, inclusive of C luStream (Aggarwal et al. in Proceedings of VLDB, 2003 ) and U Micro (Aggarwal and Yu in Proceedings of ICDE, 2008 ). We show that such methods cannot achieve high efficiency. Our second attempt aims at devising a novel algorithm, c luUS , to handle the sliding-window model by using U F structure. Detailed analysis and thorough experimental reports on synthetic and real data sets confirm the advantages of our proposed method.