Clustering high dimensional dynamic data streams

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