Improved approximate detection of duplicates for data streams over sliding windows

Hong Shen, Yu Zhang

Research output: Contribution to journalArticlepeer-review

43 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)973-987
Number of pages15
JournalJournal of Computer Science and Technology
Issue number6
Publication statusPublished - Nov 2008
Externally publishedYes


  • Approximate query
  • Bloom filter
  • Data stream
  • Duplicate detection
  • Sliding window


Dive into the research topics of 'Improved approximate detection of duplicates for data streams over sliding windows'. Together they form a unique fingerprint.

Cite this