Improved Algorithms for Polynomial-Time Decay and Time-Decay with Additive Error

摘要

We consider the problem of maintaining polynomial and exponential decay aggregates of a data stream, where the weight of values seen from the stream diminishes as time elapses. These types of aggregation were discussed by Cohen and Strauss (J. Algorithms