Efficiently Filtering Duplicates over Distributed Data Streams

We study the problem of filtering duplicate items over physically distributed data streams to provide clean data for real-time monitoring applications. Existing approaches only filter local duplicates within each stream, and their space and time costs are hardly feasible for high-speed data streams. Based on the space/time efficient data structure Bloom filter, we propose a novel local filtering algorithm to efficiently filter local duplicates, and then extend it to global duplicates filtering which is never addressed before. To adapt to different additional communication overhead in global duplicates filtering, we present eager and lazy approaches for Bloom filter sharing. Theoretical and experimental results show that our solution can efficiently filter duplicates locally and globally, while the errors are small enough when the arguments are set properly.