Improved Decaying Bloom Filter for duplicate detection in data streams over sliding windows

Abstract

Approximate duplicate detection based on the Decaying Bloom Filter (DBF) for data streams over sliding windows (DDMDBF) 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 <; 1)of DDMDBF by a factor of p1-√(2) for approximately same bit space. Experimental results on synthetic data validate the analytical results on the efficiency and accuracy of our method.