## G. Cormode and K. Yi.
Tracking distributed aggregates over time-based sliding windows
(brief announcement).
In *ACM Principles of Distributed Computing (PODC)*, 2011.

The area of distributed monitoring requires tracking the value of a
function of distributed data as new observations are made.
An important case is when attention is restricted to only a recent
time period, such as the last hour of readings-the sliding window
case.
In this announcement, we outline a novel paradigm for handling such
monitoring problems, which we dub the “forward/backward” approach.
This provides clean solutions for several fundamental problems, such
as counting, tracking frequent items, and maintaining order
statistics.
We obtain efficient protocols for these problems that improve on
previous work, and are easy to implement.
Specifically, we obtain optimal *O*((*k*)/(ε) log(ε*n*/*k*))
communication per window of *n* updates for tracking counts and heavy
hitters with accuracy ε across *k* sites; and near-optimal
communication of *O*((*k*)/(ε) log^{2}(1/ε) log(*n*/*k*))
for quantiles.

[ bib |
Alternate Version |
slides |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*