Variability in Data Streams
David Felber; Rafail Ostrovsky
Abstract:
We consider the problem of tracking with small relative error an integer functions ƒ(n) defied by a distributed update stream ƒ′(n) in the distributed monitoring model. In this model ,there are k sites over which the updates ƒ′(n) are distributed, and they must communicate with a central co–ordinator to maintain an estimate of ƒ(n).
Existing streaming algorithms with worst–case guarantees for this problem assume ƒ(n) to be monotone; there are verylarge lower bounds on thespace requirements for summarizing a distributed non –monotonic stream,often linear in the size n of of the stream. However, the input streams obtaining these lower bounds are highly vaRIABLE, making high relatively large jumps from one timestep to next; in practice, the impact of ƒ(n) of any single update ƒ′(n) is usually small. What has heretofore been lacking is a framework for non monotonic streams that admits algorithms whose worst–case performance is as good as exciting algorithms for monotone streams and degrades gracefully for non–monotonic streams as those streams vary more quickly.
In this paper we propose such a framework. we introduce a stream parameter, the “variability” v, deriving its definition in a way that shows it to be a natural parameter to consider for non –monotonic streams. it is also a useful parameter. From a theoretical perspective, we can adapt existing algorithms for monotone streams to work for non –monotonic streams, with only minor modifications , in such a way that they reduce to the monotone case when the stream happens to be monotone, and in such a way that we can refine the worst –case communication bounds from Θ(n) to Õ(v). From a practical perspective, we demonstrate that v can be small in practice by proving that v is Ο(logƒ(n)) for monotone streams and o(n) for streams that are “nearly” monotone or that are generated by random walks. We expect v to be o(n) for many other intersting input classes as well.
comment: PODS PP: 251–260
Fetch PDF file of the paper
| Back to Publications List |