Notice of Retraction: Improved Decaying Bloom Filter for duplicate detection in data streams over sliding windows

Xiujun Wang, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

2 Citations (Scopus)

Abstract

Approximate duplicate detection based on the Decaying Bloom Filter (DBF) for data streams over sliding windows (DDMDBF) [1] is an effective technique, but may have a large false positive rate. Because it simply takes a querying element to be duplicated when the counters that this element is hashed to are non-zero, while neglects the actual values of the counters. In this paper, we propose a new data structure, Flag Decaying Bloom Filter (FDBF), which can maintain duplicate information more accurately by extending DBF with one additional flag bit for each integer counter. Then we propose an efficient approximate duplicate detection method (DDMFDBF) based on FDBF that reduces the false positive rate (FPR) p (0 < p < l)of DDMDBF by a factor of P 1-√2 for approximately same bit space. Expenmental results on synthetic data validate the analytical results on the efficiency and accuracy of our method.

Original languageEnglish
Title of host publicationProceedings - 2010 3rd IEEE International Conference on Computer Science and Information Technology, ICCSIT 2010
PublisherIEEE Computer Society
Pages348-353
Number of pages6
ISBN (Print)9781424455386
DOIs
Publication statusPublished - 2010
Externally publishedYes

Publication series

NameProceedings - 2010 3rd IEEE International Conference on Computer Science and Information Technology, ICCSIT 2010
Volume4

Keywords

  • Counting bloom filter
  • Decay bloom filter
  • Duplicate detection
  • False positive
  • Flag deacying bloom filter

Fingerprint

Dive into the research topics of 'Notice of Retraction: Improved Decaying Bloom Filter for duplicate detection in data streams over sliding windows'. Together they form a unique fingerprint.

Cite this