---
_id: '18787'
abstract:
- lang: eng
text: 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.
author:
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
- first_name: Gereon
full_name: Frahling, Gereon
last_name: Frahling
citation:
ama: '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.'
apa: 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).
bibtex: '@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}
}'
chicago: 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.
ieee: 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.
mla: 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.
short: 'C. Sohler, G. Frahling, in: Proceedings of the 37th ACM Symposium on Theory
of Computing (STOC), 2005, pp. 209–217.'
date_created: 2020-09-01T13:49:23Z
date_updated: 2022-01-06T06:53:52Z
department:
- _id: '63'
language:
- iso: eng
page: 209-217
publication: Proceedings of the 37th ACM Symposium on Theory of Computing (STOC)
status: public
title: Coresets in Dynamic Geometric Data Streams
type: conference
user_id: '15415'
year: '2005'
...