A streaming model is one where data items arrive over long period of time, either one item at a time or in bursts. Typical tasks include computing various statistics over a sliding window of some fixed time-horizon. What makes the streaming model interesting is that as the time progresses, old items expire and new ones arrive. One of the simplest and central tasks in this model is sampling. That is, the task of maintaining up to @math uniformly distributed items from a current time-window as old items expire and new ones arrive. We call sampling algorithms succinct if they use provably optimal (up to constant factors) worst-case memory to maintain @math items (either with or without replacement). We stress that in many applications structures that have expected succinct representation as the time progresses are not sufficient, as small probability events eventually happen with probability 1. Thus, in this paper we ask the following question: are Succinct Sampling on Streams (or @math -algorithms)possible, and if so for what models? Perhaps somewhat surprisingly, we show that @math -algorithms are possible for all variants of the problem mentioned above, i.e. both with and without replacement and both for one-at-a-time and bursty arrival models. Finally, we use @math algorithms to solve various problems in sliding windows model, including frequency moments, counting triangles, entropy and density estimations. For these problems we present solutions with provable worst-case memory guarantees.
Datar, Gionis, Indyk and Motwani @cite_19 pioneered the research in this area, presenting exponential histograms, effective and simple solutions for a wide class of functions over sliding windows. In particular, they gave a memory-optimal algorithm for count, sum, average, @math and other functions. Gibbons and Tirthapura @cite_46 improved the results for sum and count, providing memory and time-optimal algorithms. Feigenbaum, Kannan and Zhang @cite_33 addressed the problem of computing diameter. Lee and Ting in @cite_48 gave a memory-optimal solution for the relaxed version of the count problem. Chi, Wang, Yu and Muntz @cite_2 addressed a problem of frequent itemsets. Algorithms for frequency counts and quantiles were proposed by Arasu and Manku @cite_18 . Further improvement for counts was reported by Lee and Ting @cite_41 . Babcock, Datar, Motwani and O'Callaghan @cite_23 provided an effective solution of variance and @math -medians problems. Algorithms for rarity and similarity were proposed by Datar and Muthukrishnan @cite_39 . Golab, DeHaan, Demaine, Lopez-Ortiz and Munro @cite_43 provided an effective algorithm for finding frequent elements. Detailed surveys of recent results can be found in @cite_29 @cite_24 .
@cite_18 @cite_33 @cite_41 @cite_48 @cite_29 @cite_39 @cite_24 @cite_19 @cite_43 @cite_23 @cite_2 @cite_46
2152637787 2007025103 1965972569 2600017706 2004154913 2886756691 2124507579 1569347009 1990465412
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. 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. 1 Introduction 2 Map 3 The Data Stream Phenomenon 4 Data Streaming: Formal Aspects 5 Foundations: Basic Mathematical Ideas 6 Foundations: Basic Algorithmic Techniques 7 Foundations: Summary 8 Streaming Systems 9 New Directions 10 Historic Notes 11 Concluding Remarks Acknowledgements References. 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. 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 O(1 e log2N) bits of memory, we can estimate the number of 1's to within a factor of 1 + e. We also give a matching lower bound of Ω(1 e log2 N) memory bits for any deterministic or randomized algorithms. We extend our scheme to maintain the sum of the last N positive integers. We provide matching upper and lower bounds for this more general problem as well. We apply our techniques to obtain efficient algorithms for the L p norms (for p e [1, 2]) of vectors under the sliding window model. Using the algorithm for the basic counting problem, one can adapt many other techniques to work for the sliding window model, with a multiplicative overhead of O(1 elog N) in memory and a 1 + e factor loss in accuracy. These include maintaining approximate histograms, hash tables, and statistics or aggregates such as sum and averages. 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 τ)). This paper considers the problem of mining closed frequent itemsets over a 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 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 item-sets over a sliding-window. The selected itemsets consist of 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 item-sets 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 previous approaches. 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.