Clustering is a common problem in the analysis of large data sets.  Streaming algorithms, which make a single pass over the data set using small working memory and produce a clustering comparable in cost to the optimal offline solution, are especially useful. We develop the first streaming algorithms achieving a constant-factor approximation to the cluster radius for two variations of the  k -center clustering problem. We give a streaming (4 +  i¾? )-approximation algorithm using  O ( i¾? i¾? 1 kz ) memory for the problem with  outliers , in which the clustering is allowed to drop up to  z of the input points; previous work used a random sampling approach which yields only a bicriteria approximation. We also give a streaming (6 +  i¾? )-approximation algorithm using  O ( i¾? i¾? 1ln ( i¾? i¾? 1)  k +  k 2) memory for a variation motivated by anonymity considerations in which each cluster must contain at least a certain number of input points.
['Richard Matthew McCutchen', 'Samir Khuller']
Streaming Algorithms for k-Center Clustering with Outliers and with Anonymity