Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/53222
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows |
Author: | Shen, H. Zhang, Y. |
Citation: | Journal of Computer Science and Technology, 2008; 23(6):973-987 |
Publisher: | Springer New York LLC |
Issue Date: | 2008 |
ISSN: | 1000-9000 1860-4749 |
Statement of Responsibility: | Hong Shen and Yu Zhang |
Abstract: | Detecting duplicates in data streams is an important problem that has a wide range of applications. In general, precisely detecting duplicates in an unbounded data stream is not feasible in most streaming scenarios, and, on the other hand, the elements in data streams are always time sensitive. These make it particular significant approximately detecting duplicates among newly arrived elements of a data stream within a fixed time frame. In this paper, we present a novel data structure, Decaying Bloom Filter (DBF), as an extension of the Counting Bloom Filter, that effectively removes stale elements as new elements continuously arrive over sliding windows. On the DBF basis we present an efficient algorithm to approximately detect duplicates over sliding windows. Our algorithm may produce false positive errors, but not false negative errors as in many previous results. We analyze the time complexity and detection accuracy, and give a tight upper bound of false positive rate. For a given space G bits and sliding window size W, our algorithm has an amortized time complexity of O( √G/W). Both analytical and experimental results on synthetic data demonstrate that our algorithm is superior in both execution time and detection accuracy to the previous results. © 2008 Springer. |
Keywords: | data stream duplicate detection bloom filter approximate query sliding window |
DOI: | 10.1007/s11390-008-9192-1 |
Published version: | http://dx.doi.org/10.1007/s11390-008-9192-1 |
Appears in Collections: | Aurora harvest 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.