Title: Clustering High Dimensional Dynamic Data Streams,
Abstract: We present data streaming algorithms for the $k$-median problem in
high-dimensional dynamic geometric data streams, i.e. streams allowing both
insertions and deletions of points from a discrete Euclidean space $\{1, 2,
\ldots \Delta\}^d$. Our algorithms use $k \epsilon^{-2} poly(d \log \Delta)$
space/time and maintain with high probability a small weighted set of points (a
coreset) such that for every set of $k$ centers the cost of the coreset
$(1+\epsilon)$-approximates the cost of the streamed point set. We also provide
algorithms that guarantee only positive weights in the coreset with additional
logarithmic factors in the space and time complexities. We can use this
positively-weighted coreset to compute a $(1+\epsilon)$-approximation for the
$k$-median problem by any efficient offline $k$-median algorithm. All previous
algorithms for computing a $(1+\epsilon)$-approximation for the $k$-median
problem over dynamic data streams required space and time exponential in $d$.
Our algorithms can be generalized to metric spaces of bounded doubling
dimension.