Summarization and matching of density-based clusters in steaming environments

Density-based cluster mining is known to serve a broad range of applications ranging from stock trade analysis to moving object monitoring. Although methods for efficient extrac-tion of density-based clusters have been studied in the lit-erature, the problem of summarizing and matching of such clusters with arbitrary shapes and complex cluster struc-tures remains unsolved. Therefore, the goal of our work is to extend the state-of-art of density-based cluster mining in streams from cluster extraction only to now also support analysis and management of the extracted clusters. Our work solves three major technical challenges. First, we pro-pose a novel multi-resolution cluster summarization method, called Skeletal Grid Summarization (SGS), which captures the key features of density-based clusters, covering both their external shape and internal cluster structures. Second, in order to summarize the extracted clusters in real-time, we present an integrated computation strategy C-SGS, which piggybacks the generation of cluster summarizations within the online clustering process. Lastly, we design a mecha-nism to efficiently execute cluster matching queries, which identify similar clusters for given cluster of analyst’s interest from clusters extracted earlier in the stream history. Our ex-perimental study using real streaming data shows the clear superiority of our proposed methods in both efficiency and effectiveness for cluster summarization and cluster matching queries to other potential alternatives. 1