Coresets in dynamic geometric data streams

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.

Authors

• Gereon Frahling
• Christian Sohler

Keywords

• computational geometry
• data structures
• streaming algorithms