On High Dimensional Projected Clustering of Uncertain Data Streams

In this paper, we will study the problem of projected clustering of uncertain data streams. The use of uncertainty is especially important in the high dimensional scenario, because the sparsity property of high dimensional data is aggravated by the uncertainty. The uncertainty information is important for not only the determination of the assignment of data points to clusters, but also that of the valid projections across which the data is naturally clustered. The problem is especially challenging in the case where the data is not available on disk and arrives in the form of a fast stream. In such cases, the one-pass constraint in data stream computation poses special challenges to the algorithmic sophistication required for incorporating uncertainty information into the high dimensional computations. We will show that the projected clustering problem can be effectively solved in the context of uncertain data streams.