A Block-Wise Updating Strategy for Approximate Duplicate Detection

Approximate duplicate detection in data streams aims to determine whether an item is present within a small subsequence of the data stream. It is a fundamental query problem needed in several network applications, such as web crawling and Radio Frequency Identification (RFID) tag management. Most of the existing algorithms are not space-efficient as they overlook the distributional information of query frequency and membership likelihood. In this paper, we propose CEll Bloom Filter (CEBF) algorithm, a space-efficient data structure designed by adopting a block-wise updating strategy, to solve this problem, and two typical distributions are considered: two typical distributions: (1) uniform query frequency of items, and (2) uniform membership likelihood of items. For an arbitrary sliding window size n and an arbitrary average false positive rate $\epsilon \in (0,1)$, the proposed algorithm needs approximately $O(n{\log }_2(1/\epsilon ))$ bits, which is significantly less than the number of bits used in existing methods. Space lower bound is also derived for these two typical distributions, which demonstrates that the proposed algorithm is near-optimal in terms of space consumption. Experiments are conducted on both synthetic and real datasets, and the experimental results clearly demonstrate that the proposed method is clearly and significantly more effective and promising compared to existing other methods.