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_18: We initiate the study of numerical linear algebra in the sliding window model, where only the most recent @math updates in the data stream form the underlying set. Although most existing work in the sliding window model uses the smooth histogram framework, most interesting linear-algebraic problems are not smooth; we show that the spectral norm, vector induced matrix norms, generalized regression, and low-rank approximation are not amenable for the smooth histogram framework. To overcome this challenge, we first give a deterministic algorithm that achieves spectral approximation in the sliding window model that can be viewed as a generalization of smooth histograms, using the Loewner ordering of PSD matrices. We then give algorithms for both spectral approximation and low-rank approximation that are space-optimal up to polylogarithmic factors. Our algorithms are based on a new notion of "reverse online" leverage scores that account for both how unique and how recent a row is, while preserving sparsity so that both our algorithms run in input sparsity runtime, up to lower order factors. We show that our techniques have applications to linear-algebraic problems in other settings. Specifically, we show that our analysis immediately implies an algorithm for low-rank approximation in the online setting that is space-optimal up to logarithmic factors, as well as nearly input sparsity time. We show our deterministic spectral approximation algorithm can be used to handle @math spectral approximation in the sliding window model under a certain assumption on the bit complexity of the entries. Finally, we show that our downsampling framework can be applied to the problem of approximate matrix multiplication and provide upper and lower bounds that are tight up to @math factors.
  @cite_26: This paper presents algorithms for estimating aggregate functions over a "sliding window" of the N most recent data items in one or more streams. Our results include: For a single stream, we present the first e-approximation scheme for the number of 1's in a sliding window that is optimal in both worst case time and space. We also present the first e for the sum of integers in [0..R] in a sliding window that is optimal in both worst case time and space (assuming R is at most polynomial in N). Both algorithms are deterministic and use only logarithmic memory words. In contrast, we show that an deterministic algorithm that estimates, to within a small constant relative error, the number of 1's (or the sum of integers) in a sliding window over the union of distributed streams requires O(N) space. We present the first randomized (e,s)-approximation scheme for the number of 1's in a sliding window over the union of distributed streams that uses only logarithmic memory words. We also present the first (e,s)-approximation scheme for the number of distinct values in a sliding window over distributed streams that uses only logarithmic memory words. < olOur results are obtained using a novel family of synopsis data structures.
  @cite_4: We consider the problem of maintaining aggregates and statistics over data streams, with respect to the last N data elements seen so far. We refer to this model as the sliding window model. We consider the following basic problem: Given a stream of bits, maintain a count of the number of 1's in the last N elements seen from the stream. We show that, using @math bits of memory, we can estimate the number of 1's to within a factor of @math . We also give a matching lower bound of @math memory bits for any deterministic or randomized algorithms. We extend our scheme to maintain the sum of the last N positive integers and provide matching upper and lower bounds for this more general problem as well. We also show how to efficiently compute the Lp norms ( @math ) of vectors in the sliding window model using our techniques. Using our algorithm, one can adapt many other techniques to work for the sliding window model with a multiplicative overhead of @math in memory and a @math factor loss in accuracy. These include maintaining approximate histograms, hash tables, and statistics or aggregates such as sum and averages.
  @cite_33: This paper considers the problem of mining closed frequent itemsets over a data stream sliding window using limited memory space. We design a synopsis data structure to monitor transactions in the sliding window so that we can output the current closed frequent itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot monitor all possible itemsets. However, monitoring only frequent itemsets will make it impossible to detect new itemsets when they become frequent. In this paper, we introduce a compact data structure, the closed enumeration tree (CET), to maintain a dynamically selected set of itemsets over a sliding window. The selected itemsets contain a boundary between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data stream are reflected by boundary movements in the CET. In other words, a status change of any itemset (e.g., from non-frequent to frequent) must occur through the boundary. Because the boundary is relatively stable, the cost of mining closed frequent itemsets over a sliding window is dramatically reduced to that of mining transactions that can possibly cause boundary movements in the CET. Our experiments show that our algorithm performs much better than representative algorithms for the sate-of-the-art approaches.
  @cite_41: 
  @cite_46: 
  @cite_36: The sliding window model is useful for discounting stale data in data stream applications. In this model, data elements arrive continually and only the most recent N elements are used when answering queries. We present a novel technique for solving two important and related problems in the sliding window model---maintaining variance and maintaining a k--median clustering. Our solution to the problem of maintaining variance provides a continually updated estimate of the variance of the last N values in a data stream with relative error of at most e using O(1 e 2 log N) memory. We present a constant-factor approximation algorithm which maintains an approximate k--median solution for the last N data points using O(k τ4 N2τ log2 N) memory, where τ < 1 2 is a parameter which trades off the space bound with the approximation factor of O(2O(1 τ)).
  @cite_32: We consider the problem of maintaining e-approximate counts and quantiles over a stream sliding window using limited space. We consider two types of sliding windows depending on whether the number of elements N in the window is fixed (fixed-size sliding window) or variable (variable-size sliding window). In a fixed-size sliding window, both the ends of the window slide synchronously over the stream. In a variable-size sliding window, an adversary slides the window ends independently, and therefore has the ability to vary the number of elements N in the window.We present various deterministic and randomized algorithms for approximate counts and quantiles. All of our algorithms require O(1 e polylog(1 e, N)) space. For quantiles, this space requirement is an improvement over the previous best bound of O(1 e2 polylog(1 e, N)). We believe that no previous work on space-efficient approximate counts over sliding windows exists.
  @cite_24: 
  @cite_44: 
  @cite_49: We consider the problem of maintaining polynomial and exponential decay aggregates of a data stream, where the weight of values seen from the stream diminishes as time elapses. These types of aggregation were discussed by Cohen and Strauss (J. Algorithms 1(59), 2006), and can be used in many applications in which the relative value of streaming data decreases since the time the data was seen. Some recent work and space efficient algorithms were developed for time-decaying aggregations, and in particular polynomial and exponential decaying aggregations. All of the work done so far has maintained multiplicative approximations for the aggregates. In this paper we present the first O(log N) space algorithm for the polynomial decay under a multiplicative approximation, matching a lower bound. In addition, we explore and develop algorithms and lower bounds for approximations allowing an additive error in addition to the multiplicative error. We show that in some cases, allowing an additive error can decrease the amount of space required, while in other cases we cannot do any better than a solution without additive error.
  @cite_47: We formalize the problem of maintaining time-decaying aggregates and statistics of a data stream: the relative contribution of each data item to the aggregate is scaled down by a factor that depends on, and is non-decreasing with, elapsed time. Time-decaying aggregates are used in applications where the significance of data items decreases over time. We develop storage-efficient algorithms, and establish upper and lower bounds. Surprisingly, even though maintaining decayed aggregates have become a widely-used tool, our work seems to be the first both to explore it formally and to provide storage-efficient algorithms for important families of decay functions, including polynomial decay.
  @cite_10: We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of @math points or a sliding window of size @math , any exact algorithm for diameter requires @math bits of space. We present a simple @math -approximation algorithm for computing the diameter in the streaming model. Our main result is an @math -approximation algorithm that maintains the diameter in two dimensions in the sliding-window model using @math bits of space, where @math is the maximum, over all windows, of the ratio of the diameter to the minimum non-zero distance between any two points in the window.
  @cite_25: 
  @cite_12: 
  @cite_11: In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations a t -(N-1), a t-(N-2),..., a t , each a i E 1,...,u ; we are required to support queries about the data in the window. A crucial restriction is that we are only allowed o(N) (often polylogarithmic in N) storage space, so not all items within the window can be archived. We study two basic problems in the windowed data stream model. The first is the estimation of the rarity of items in the window. Our second problem is one of estimating similarity between two data stream windows using the Jacard's coefficient. The problems of estimating rarity and similarity have many applications in mining massive data sets. We present novel, simple algorithms for estimating rarity and similarity on windowed data streams, accurate up to factor 1 ± e using space only logarithmic in the window size.
summary: Cohen and Strauss @cite_47 study problems in time-decaying data streams in 2003. There are a number of results @cite_49 @cite_41 @cite_46 @cite_24 in this line of work, but the most prominent time-decay model is the sliding window model. Datar al , @cite_4 introduced the exponential histogram as a framework in the sliding window for estimating statistics such as count, sum of positive integers, average, and @math norms. This initiated an active line of research, including improvements to count and sum @cite_26 , frequent itemsets @cite_33 @cite_12 , frequency counts and quantiles @cite_32 @cite_44 , rarity and similarity @cite_11 , variance and @math -medians @cite_36 and other geometric and numerical linear algebra problems @cite_10 @cite_25 @cite_18 .