## G. Cormode and K. Yi.
Tracking distributed aggregates over time-based sliding windows.
In *Scientific and Statistical Database Management (SSDBM)*,
2012.

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 paper, we introduce a novel paradigm for handling such
monitoring problems, which we dub the “forward/backward” approach.
This view allows us to provide
optimal or near-optimal solutions for several fundamental problems, such
as counting, tracking frequent items, and maintaining order
statistics.
The resulting protocols improve on
previous work or give the first solutions for some problems,
and operate efficiently in terms of space and time needed.
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.
We also present solutions for problems such as tracking distinct
items, entropy, and convex hull and diameter of point sets.

[ bib |
slides |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*