Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter

Yu Zhang; Hong Shen; Hui Tian; Xianchao Zhang

doi:10.1007/978-3-642-03095-6_70

Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter

Yu Zhang, Hong Shen, Hui Tian, Xianchao Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

Abstract

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.

Original language	English
Title of host publication	Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings
Pages	741-750
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-03095-6_70
Publication status	Published - 2009
Externally published	Yes
Event	9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009 - Taipei, Taiwan, Province of China Duration: 8 Jun 2009 → 11 Jun 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5574 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009
Country/Territory	Taiwan, Province of China
City	Taipei
Period	8/06/09 → 11/06/09

Keywords

Bloom filter
Stream
Time-decay

Access to Document

10.1007/978-3-642-03095-6_70

Cite this

Zhang, Y., Shen, H., Tian, H., & Zhang, X. (2009). Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter. In Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings (pp. 741-750). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5574 LNCS). https://doi.org/10.1007/978-3-642-03095-6_70

Zhang, Yu ; Shen, Hong ; Tian, Hui et al. / Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter. Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings. 2009. pp. 741-750 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{1740f571a44a483f8a50d57cfa2620ca,

title = "Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter",

abstract = "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.",

keywords = "Bloom filter, Stream, Time-decay",

author = "Yu Zhang and Hong Shen and Hui Tian and Xianchao Zhang",

note = "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.; 9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009 ; Conference date: 08-06-2009 Through 11-06-2009",

year = "2009",

doi = "10.1007/978-3-642-03095-6_70",

language = "English",

isbn = "3642030947",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "741--750",

booktitle = "Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings",

}

Zhang, Y, Shen, H, Tian, H & Zhang, X 2009, Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter. in Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5574 LNCS, pp. 741-750, 9th International Conference on Algorithms and Architectures for Parallel Processing, ICA3PP 2009, Taipei, Taiwan, Province of China, 8/06/09. https://doi.org/10.1007/978-3-642-03095-6_70

Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter. / Zhang, Yu; Shen, Hong; Tian, Hui et al.
Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings. 2009. p. 741-750 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5574 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Zhang Y, Shen H, Tian H, Zhang X. Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter. In Algorithms and Architectures for Parallel Processing - 9th International Conference, ICA3PP 2009, Proceedings. 2009. p. 741-750. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03095-6_70

Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this