Computer Science – Data Structures and Algorithms
Scientific paper
2007-02-25
Computer Science
Data Structures and Algorithms
Scientific paper
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 $k$ uniformly distributed items from a current time-window as old items expire and new ones arrive. We call sampling algorithms {\bf succinct} if they use provably optimal (up to constant factors) {\bf worst-case} memory to maintain $k$ items (either with or without replacement). We stress that in many applications structures that have {\em 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 $S^3$-algorithms)possible, and if so for what models? Perhaps somewhat surprisingly, we show that $S^3$-algorithms are possible for {\em 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 $S^3$ algorithms to solve various problems in sliding windows model, including frequency moments, counting triangles, entropy and density estimations. For these problems we present \emph{first} solutions with provable worst-case memory guarantees.
Braverman Vladimir
Ostrovsky Rafail
Zaniolo Carlo
No associations
LandOfFree
Succinct Sampling on Streams does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Succinct Sampling on Streams, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Sampling on Streams will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-460393