Scaling clustering algorithms for massive data sets using data streams

Computing clustering techniques on massive data sets is still not feasible nor efficient today. For instance, raw satellite imagery data can be replaced with compressed counterparts for many scientific applications. However, to facilitate scientific data analysis the high order correlation between the attributes in the data set as well as their nonparametric distribution must be preserved in the reduced data set. Therefore, practical data reduction can be achieved by partitioning the overall data set via a coarse regular spatial grid, and compressing each grid cell individually by computing multivariate histograms or k-means clustering. Clustering spatial data in high dimensional spaces using k-means is expensive both with regard to computational costs and memory requirements. In a traditional k-means implementation all N data points belonging to a grid cell must be kept in memory to be clustered at a time, which often establishes a bottleneck for scientific data sets. Our objective is to define a clustering algorithm that scales automatically to any number of data points in a single grid cell, and provides high quality clustering results.