Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows
Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows
复制标题
改进了滑动窗口上数据流重复项的近似检测
DOI：
10.1007/s11390-008-9192-1
复制
发表时间：
2008-11-01
影响因子：
1.9
通讯作者：
Zhang, Yu
中科院分区：
文献类型：
--
作者：
Shen, Hong;Zhang, Yu
在数据流中检测重复数据是一个具有广泛应用的重要问题。通常，在大多数流场景中，精确检测无界数据流中的重复项是不可行的，另一方面，数据流中的元素总是时间敏感的。这使得在固定的时间范围内检测数据流的新到达元素之间的重复变得特别重要。在本文中，我们提出了一种新的数据结构，衰减布隆过滤器（DBF），作为计数布隆过滤器的扩展，当新元素不断通过滑动窗口到达时，它可以有效地去除陈旧的元素。在DBF的基础上，我们提出了一种有效的算法来近似检测滑动窗口上的重复。我们的算法可能会产生假阳性误差，但不会像以前的许多结果那样产生假阴性误差。分析了时间复杂度和检测精度，给出了假阳性率的严格上界。对于给定的空间G位和滑动窗口大小W，我们的算法具有平摊的时间复杂度。在综合数据上的实验结果表明，我们的算法在执行时间和检测精度上都优于以往的结果。
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. Experimental results on synthetic data demonstrate that our algorithm is superior in both execution time and detection accuracy to the previous results.