Probabilistic k -Median Clustering in Data Streams

We define the notion of coresets for probabilistic clustering problems and propose the first (k,e)-coreset constructions for the probabilistic k-median problem in the metric and Euclidean case. The coresets are of size poly(e − 1,k,log(W/(w min ·p min ·δ))), where W is the expected total weight of the weighted probabilistic input points, w min is the minimum weight of a probabilistic input point, p min is the minimum realization probability, and δ is the error probability of the construction. We show how to maintain our coreset for Euclidean spaces in data streams.