text: In the time-decay model for data streams, elements of an underlying data set arrive sequentially with the recently arrived elements being more important. A common approach for handling large data sets is to maintain a , a succinct summary of the processed data that allows approximate recovery of a predetermined query. We provide a general framework that takes any offline-coreset and gives a time-decay coreset for polynomial time decay functions. We also consider the exponential time decay model for @math -median clustering, where we provide a constant factor approximation algorithm that utilizes the online facility location algorithm. Our algorithm stores @math points where @math is the half-life of the decay function and @math is the aspect ratio of the dataset. Our techniques extend to @math -means clustering and @math -estimators as well.
  @cite_28: In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that given a point set P in Rd, one can compute a weighted set S ⊆ P, of size O(k e-d log n), such that one can compute the k-median means clustering on S instead of on P, and get an (1+e)-approximation. As a result, we improve the fastest known algorithms for (1+e)-approximate k-means and k-median. Our algorithms have linear running time for a fixed k and e. In addition, we can maintain the (1+e)-approximate k-median or k-means clustering of a stream when points are being only inserted, using polylogarithmic space and update time.
  @cite_40: We present new approximation algorithms for the @math -median and @math -means clustering problems. To this end, we obtain small coresets for @math -median and @math -means clustering in general metric spaces and in Euclidean spaces. In @math , these coresets are of size with polynomial dependency on the dimension @math . This leads to @math -approximation algorithms to the optimal @math -median and @math -means clustering in @math , with running time @math , where @math is the number of points. This improves over previous results. We use those coresets to maintain a @math -approximate @math -median and @math -means clustering of a stream of points in @math , using @math space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension.
summary: Another line of approach for @math -service problems is the construction of coresets, in particular when the data points lie in the Euclidean space. Har-Peled and Mazumdar @cite_28 give an insertion-only streaming algorithm for @math -medians and @math -means that provides a @math -approximation, using space @math , where @math is the dimension of the space. Similarly, Chen @cite_40 introduced an algorithm using @math space, with the same approximation guarantees.