Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/58976
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Dynamically maintaining duplicate-insensitive and time-decayed sum using time-decaying bloom filter |
Author: | Zhang, Y. Shen, H. Tian, H. Zhang, X. |
Citation: | Proceedings of the International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2009): pp.741-750 |
Publisher: | Springer |
Publisher Place: | Berlin |
Issue Date: | 2009 |
Series/Report no.: | Lecture notes in computer science ; 5574 |
ISBN: | 3642030947 9783642030949 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Algorithms and Architectures for Parallel Processing (2009 : Taiwan) |
Editor: | Hua, A. Chang, S.L. |
Statement of Responsibility: | Yu Zhang, Hong Shen, Hui Tian and Xianchao Zhang |
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: | stream bloom filter time-decay |
Rights: | © Springer-Verlag Berlin Heidelberg 2009 |
DOI: | 10.1007/978-3-642-03095-6 |
Appears in Collections: | Aurora harvest 5 Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.