CDS-Tree: an effective index for clustering arbitrary shapes in data streams

Finding clusters of arbitrary shapes in data streams is a challenging work for advanced applications. An effective approach to clustering arbitrary shapes is the clustering algorithm based on space partition. However, it cannot be applied directly into data stream clustering since it costs large memory spaces while data stream processing has strict memory space limitation. In addition, it has low efficiency for high dimensional data and fine granularity. Moreover, its fixed granularity partition isn´t suitable for the changes on data distribution of data streams. Therefore, we propose a novel index structure CDS-Tree and design an improved space partition based clustering algorithm, which aims to cluster arbitrary shapes on high dimension streams data with high accuracy. CDS-Tree stores only non-empty cells and keeps the position relationship among cells, so its compact structure costs small memory spaces and gets high efficiency. Moreover, we propose a novel measure for data skew - DSF (Data Skew Factor) to be used to adjust automatically the partition granularity according to the change of data streams, thus the algorithm can gain high analysis accuracy within limited memory. The experimental results on real datasets and synthetic datasets show that this algorithm has higher clustering accuracy, and better scalability with the size of windows and data dimensionality than other typical algorithms applied in trivial style.