Coresets in Dynamic Geometric Data Streams

C. Sohler, G. Frahling, in: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), 2005, pp. 209–217.

Download
No fulltext has been uploaded.
Conference Paper | English
Author
;
Abstract
A dynamic geometric data stream consists of a sequence of m insert/delete operations of points from the discrete space {1,..., ∆} d [26]. We develop streaming (1 + ɛ)-approximation algorithms for k-median, k-means, MaxCut, maximum weighted matching (MaxWM), maximum travelling salesperson (MaxTSP), maximum spanning tree (MaxST), and average distance over dynamic geometric data streams. Our algorithms maintain a small weighted set of points (a coreset) that approximates with probability 2/3 the current point set with respect to the considered problem during the m insert/delete operations of the data stream. They use poly(ɛ −1, log m, log ∆) space and update time per insert/delete operation for constant k and dimension d. Having a coreset one only needs a fast approximation algorithm for the weighted problem to compute a solution quickly. In fact, even an exponential algorithm is sometimes feasible as its running time may still be polynomial in n. For example one can compute in poly(log n, exp(O((1+log(1/ɛ)/ɛ) d−1))) time a solution to k-median and k-means [21] where n is the size of the current point set and k and d are constants. Finding an implicit solution to MaxCut can be done in poly(log n, exp((1/ɛ) O(1))) time. For MaxST and average distance we require poly(log n, ɛ −1) time and for MaxWM we require O(n 3) time to do this.
Publishing Year
Proceedings Title
Proceedings of the 37th ACM Symposium on Theory of Computing (STOC)
Page
209-217
LibreCat-ID

Cite this

Sohler C, Frahling G. Coresets in Dynamic Geometric Data Streams. In: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC). ; 2005:209-217.
Sohler, C., & Frahling, G. (2005). Coresets in Dynamic Geometric Data Streams. In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC) (pp. 209–217).
@inproceedings{Sohler_Frahling_2005, title={Coresets in Dynamic Geometric Data Streams}, booktitle={Proceedings of the 37th ACM Symposium on Theory of Computing (STOC)}, author={Sohler, Christian and Frahling, Gereon}, year={2005}, pages={209–217} }
Sohler, Christian, and Gereon Frahling. “Coresets in Dynamic Geometric Data Streams.” In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), 209–17, 2005.
C. Sohler and G. Frahling, “Coresets in Dynamic Geometric Data Streams,” in Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), 2005, pp. 209–217.
Sohler, Christian, and Gereon Frahling. “Coresets in Dynamic Geometric Data Streams.” Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), 2005, pp. 209–17.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar