Tracking distributed aggregates over time-based sliding windows
Graham Cormode, Ke Yi · 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/epsilon log2(1/ε) log (n/k)) for quantiles.