Maintaining time-decaying stream aggregates

被引:58
作者
Cohen, E
Strauss, MJ
机构
[1] AT&T Labs Res, Florham Pk, NJ 07932 USA
[2] Univ Michigan, Dept Math, Ann Arbor, MI 48109 USA
[3] Univ Michigan, EECS, Ann Arbor, MI 48109 USA
来源
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2006年 / 59卷 / 01期
关键词
Database systems;
D O I
10.1016/j.jalgor.2005.01.006
中图分类号
TP301 [理论、方法];
学科分类号
081202 [计算机软件与理论];
摘要
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. (C) 2005 Elsevier Inc. All rights reserved.
引用
收藏
页码:19 / 36
页数:18
相关论文
共 16 条
[1]
BABCOCK B, 2002, P 2002 ACM S PRINC D
[2]
BREMLERBARR A, 2002, P 2 ACM SIGCOMM INT
[3]
Managing TCP connections under persistent HTTP [J].
Cohen, E ;
Kaplan, H ;
Oldham, J .
COMPUTER NETWORKS, 1999, 31 (11-16) :1709-1723
[4]
Size-estimation framework with applications to transitive closure and reachability [J].
Cohen, E .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 55 (03) :441-453
[5]
COHEN E, 2004, P 15 ACM SIAM S DISC
[6]
COHEN E, 2004, SIGMOD ACM
[7]
COHEN E, 2003, P 2003 ACM S PRINC
[8]
CORTES C, 1998, P KDD NEW YORK AUG
[9]
Maintaining stream statistics over sliding windows [J].
Datar, M ;
Gionis, A ;
Indyk, P ;
Motwani, R .
SIAM JOURNAL ON COMPUTING, 2002, 31 (06) :1794-1813
[10]
FEIGENBAUM J, 1999, P 40 ANN S FDN COMP, P501