Maintaining time-decaying stream aggregates

• DOI: 10.1016/j.jalgor.2005.01.006
• Publication Date: 2005-03-08T18:31:07Z
• Authors: Edith Cohen; Martin J. Strauss
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

We formalize the problem of maintaining time-decaying aggregates and statistics of a data stream: the relative contribution of each data item to the aggregate is scaled down by a factor that depends on, and is non-increasing with, elapsed time. Time-decaying aggregates are used in applications where the significance of data items decreases over time. We develop storage-efficient algorithms, and establish upper and lower bounds. Surprisingly, even though maintaining decaying aggregates have become a widely-used tool, our work seems to be the first both to explore it formally and to provide storage-efficient algorithms for important families of decay functions, including polynomial decay.