Significance of Shared Density Graph Using DBSTREAM Algorithm

Nowadays streaming data is delivered by more and more applications, due to this crucial method for data and knowledge engineering is considered to be clustering data streams. It is a two step process. A normal approach is to summarize the data stream in real-time with an online process into so called micro-clusters. Local density estimates are represented by micro-clusters by assembling the information of many data points which is defined in an area. A traditional clustering algorithm is used in a second offline step, in which larger final clusters are formed by reclustering the micro-clusters. For reclustering, the pseudo points which are used are actually coordinator of the micro-clusters with the weights which are density estimates. However, in the online process, information about density in the area between micro-clusters is not preserved and reclustering is based on possibly inaccurate assumptions about the distribution of data within and between micro-clusters (e.g., uniform or Gaussian). This paper depicts DBSTREAM, the first micro-cluster-based online clustering component that explicitly captures the density between micro-clusters via a shared density graph. The density information in this graph is then exploited for reclustering based on actual density between modified micro-clusters. We discuss the space and time complexity of maintaining the shared density graph. Experiments on a wide range of artificial and real data sets highlight that using shared density improves clustering quality over other popular data stream clustering methods which require the creation of a larger number of smaller microclusters to achieve comparable results.