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.
The first insertion-only streaming algorithm for the @math -median clustering problem was presented in 2000 by Guha, Mishra, Motwani, and O'Callaghan @cite_17 . Their algorithm uses @math space for a @math approximation, for some @math . Subsequently, Charikar al , @cite_0 present an @math -approximation algorithm for @math -means clustering that uses @math space. Their algorithm uses a number of phases, each corresponding to a different guess for the value of the cost of optimal solution. The guesses are then used in the online facility location ( ) algorithm of @cite_45 , which provides a set of centers whose number and cost allows the algorithm to reject or accept the guess. This technique is now one of the standard approaches for handling @math -service problems. Braverman al , @cite_3 improve the space usage of this technique to @math . @cite_20 and @cite_2 develop algorithms for @math -means clustering on sliding windows, in which expired data should not be included in determining the cost of a solution.
@cite_3 @cite_0 @cite_45 @cite_2 @cite_20 @cite_17
2264057010 2094048240 2018165630 2290182846
We explore clustering problems in the streaming sliding window model in both general metric spaces and Euclidean space. We present the first polylogarithmic space O(1)-approximation to the metric k-median and metric k-means problems in the sliding window model, answering the main open problem posed by Babcock, Datar, Motwani and O'Callaghan [5], which has remained unanswered for over a decade. Our algorithm uses O(k3log6W) space and poly(k, log W) update time, where W is the window size. This is an exponential improvement on the space required by the technique due to Babcock, et al We introduce a data structure that extends smooth histograms as introduced by Braverman and Ostrovsky [11] to operate on a broader class of functions. In particular, we show that using only polylogarithmic space we can maintain a summary of the current window from which we can construct an O(1)-approximate clustering solution. Merge-and-reduce is a generic method in computational geometry for adapting offline algorithms to the insertion-only streaming model. Several well-known coreset constructions are maintainable in the insertion-only streaming model using this method, including well-known coreset techniques for the k-median and k-means problems in both low-and high-dimensional Euclidean spaces [31, 15]. Previous work [27] has adapted coreset techniques to the insertion-deletion model, but translating them to the sliding window model has remained a challenge. We give the first algorithm that, given an insertion-only streaming coreset of space s (maintained using merge-and-reduce method), maintains this coreset in the sliding window model using O(s2e--2 log W) space. For clustering problems, our results constitute the first significant step towards resolving problem number 20 from the List of Open Problems in Sublinear Algorithms [39]. 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. We consider @math -median clustering in finite metric spaces and @math -means clustering in Euclidean spaces, in the setting where @math is part of the input (not a constant). For the @math -means problem, show that if the optimal @math -means clustering of the input is more expensive than the optimal @math -means clustering by a factor of @math , then one can achieve a @math -approximation to the @math -means optimal in time polynomial in @math and @math by using a variant of Lloyd's algorithm. In this work we substantially improve this approximation guarantee. We show that given only the condition that the @math -means optimal is more expensive than the @math -means optimal by a factor @math for some constant @math , we can obtain a PTAS. In particular, under this assumption, for any @math we achieve a @math -approximation to the @math -means optimal in time polynomial in @math and @math , and exponential in @math and @math . We thus decouple the strength of the assumption from the quality of the approximation ratio. We also give a PTAS for the @math -median problem in finite metrics under the analogous assumption as well. For @math -means, we in addition give a randomized algorithm with improved running time of @math . Our technique also obtains a PTAS under the assumption of that all @math approximations are @math -close to a desired target clustering, in the case that all target clusters have size greater than @math and @math is constant. Note that the motivation of is that for many clustering problems, the objective function is only a proxy for the true goal of getting close to the target. From this perspective, our improvement is that for @math -means in Euclidean spaces we reduce the distance of the clustering found to the target from @math to @math when all target clusters are large, and for @math -median we improve the largeness'' condition needed in the work of to get exactly @math -close from @math to @math . Our results are based on a new notion of clustering stability. In PODS 2003, Babcock, Datar, Motwani and O'Callaghan gave the first streaming solution for the k-median problem on sliding windows using O(frack k tau^4 W^2tau log^2 W) space, with a O(2^O(1 tau)) approximation factor, where W is the window size and tau in (0,1 2) is a user-specified parameter. They left as an open question whether it is possible to improve this to polylogarithmic space. Despite much progress on clustering and sliding windows, this question has remained open for more than a decade. In this paper, we partially answer the main open question posed by Babcock, Datar, Motwani and O'Callaghan. We present an algorithm yielding an exponential improvement in space compared to the previous result given in Babcock, et al In particular, we give the first polylogarithmic space (alpha,beta)-approximation for metric k-median clustering in the sliding window model, where alpha and beta are constants, under the assumption, also made by , that the optimal k-median cost on any given window is bounded by a polynomial in the window size. We justify this assumption by showing that when the cost is exponential in the window size, no sublinear space approximation is possible. Our main technical contribution is a simple but elegant extension of smooth functions as introduced by Braverman and Ostrovsky, which allows us to apply well-known techniques for solving problems in the sliding window model to functions that are not smooth, such as the k-median cost.