Journal Article

Clustering data streams using grid-based synopsis

Bhatnagar, Vasudha, Kaur, Sharanjit, Chakravarthy, Sharma

2014

Overview

Continually advancing technology has made it feasible to capture data online for onward transmission as a steady flow of newly generated data points, termed as data stream. Continuity and unboundedness of data streams make storage of data and multiple scans of data an impractical proposition for the purpose of knowledge discovery. Need to learn structures from data in streaming environment has been a driving force for making clustering a popular technique for knowledge discovery from data streams. Continuous nature of streaming data makes it infeasible to look for point membership among the clusters discovered so far, necessitating employment of a synopsis structure to consolidate incoming data points. This synopsis is exploited for building clustering scheme to meet subsequent user demands. The proposed Exclusive and Complete Clustering (ExCC) algorithm captures non-overlapping clusters in data streams with mixed attributes, such that each point either belongs to some cluster or is an outlier/noise. The algorithm is robust, adaptive to changes in data distribution and detects succinct outliers on-the-fly. It deploys a fixed granularity grid structure as synopsis and performs clustering by coalescing dense regions in grid. Speed - based pruning is applied to synopsis prior to clustering to ensure currency of discovered clusters. Extensive experimentation demonstrates that the algorithm is robust, identifies succinct outliers on-the-fly and is adaptive to change in the data distribution. ExCC algorithm is further evaluated for performance and compared with other contemporary algorithms.

• Publisher: Springer London,Springer,Springer Nature B.V
• Subject: Adaptive algorithms / Algorithms / Applied sciences / Cluster analysis / Clustering / Clusters / Computer Science / Computer science; control theory; systems / Computer systems and distributed systems. User interface / Construction / Data compression / Data mining / Data Mining and Knowledge Discovery / Data points / Data processing. List processing. Character string processing / Data transmission / Database Management / Exact sciences and technology / Information Storage and Retrieval / Information Systems and Communication Service / Information Systems Applications (incl.Internet) / IT in Business / Knowledge discovery / Memory and file management (including protection and security) / Memory organisation. Data processing / Noise / Regular Paper / Software / Streaming media / Studies