TY - GEN
T1 - Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter
AU - Zhang, Yu
AU - Shen, Hong
AU - Tian, Hui
AU - Zhang, Xianchao
N1 - Funding Information:
This work is supported by Chinese Academy of Science "100 Talents" Project and National Science Foundation of China under its General Projects funding #60772034. Corresponding author: H. Shen.
PY - 2009
Y1 - 2009
N2 - The duplicate-insensitive and time-decayed sum of an arbitrary subset in a stream is an important aggregation for various analyses in many distributed stream scenarios. In general, precisely providing this sum in an unbounded and high-rate stream is infeasible. Therefore, we target at this problem and introduce a sketch, namely, time-decaying Bloom Filter (TDBF). The TDBF can detect duplicates in a stream and meanwhile dynamically maintain decayed-weight of all distinct elements in the stream according to a user-specified decay function. For a query for the current decayed sum of a subset in the stream, TDBF provides an effective estimation. In our theoretical analysis, a provably approximate guarantee has been given for the error of the estimation. In addition, the experimental results on synthetic stream validate our theoretical analysis.
AB - The duplicate-insensitive and time-decayed sum of an arbitrary subset in a stream is an important aggregation for various analyses in many distributed stream scenarios. In general, precisely providing this sum in an unbounded and high-rate stream is infeasible. Therefore, we target at this problem and introduce a sketch, namely, time-decaying Bloom Filter (TDBF). The TDBF can detect duplicates in a stream and meanwhile dynamically maintain decayed-weight of all distinct elements in the stream according to a user-specified decay function. For a query for the current decayed sum of a subset in the stream, TDBF provides an effective estimation. In our theoretical analysis, a provably approximate guarantee has been given for the error of the estimation. In addition, the experimental results on synthetic stream validate our theoretical analysis.
KW - Bloom filter
KW - Stream
KW - Time-decay
UR - http://www.scopus.com/inward/record.url?scp=70349088676&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03095-6_70
DO - 10.1007/978-3-642-03095-6_70
M3 - Conference contribution
AN - SCOPUS:70349088676
SN - 3642030947
SN - 9783642030949
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 741
EP - 750
BT - Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings
T2 - 9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009
Y2 - 8 June 2009 through 11 June 2009
ER -