|
|
|
     |
                                     |
Return to Streams and Indexing
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-decreasing with, elapsed time. Time-decaying aggregates are used in applications where the significance of data items decreases over time. We develop storage-eficient algorithms, and establish upper and lower bounds. Surprisingly, even though maintaining decayed 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.
@inproceedings {DBLP:conf/pods/CohenS03, author = {Edith Cohen and Martin Strauss}, booktitle = {PODS}, title = {Maintaining time-decaying stream aggregates.}, pages = {223-233}, year = {2003}, url = {db/conf/pods/pods2003.html#CohenS03}, ee = {http://doi.acm.org/10.1145/773153.773175}, crossref = {conf/pods/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
