Approximately Detecting Duplicates for Probabilistic Data Streams over Sliding Windows | IEEE Conference Publication | IEEE Xplore

Approximately Detecting Duplicates for Probabilistic Data Streams over Sliding Windows


Abstract:

A probabilistic data stream S is defined as a sequence of uncertain tuples <;ti, pi >;, i = 1...∞, with the semantics that element ti occurs in the stream with probabilit...Show More

Abstract:

A probabilistic data stream S is defined as a sequence of uncertain tuples <;ti, pi >;, i = 1...∞, with the semantics that element ti occurs in the stream with probability pi ϵ (0, 1). Thus each distinct element t, which occurs in tuples of S, has an existential probability based on the tuples: <; ti = t, pi >; ϵ S. Existing duplicate detection methods for a traditional deterministic data stream can't maintain these existential probabilities for elements in S, which is important query information. In this paper, we present a novel data structure, Floating Counter Bloom Filter (FCBF), as an extension of CBF, which can maintain these existential probabilities effectively. Based on FCBF, we present an efficient algorithm to approximately detect duplicates for probabilistic data streams over sliding windows. Given a sliding window size W and floating counter number N, for any t which occurs in the past sliding window, our method outputs the accurate existential probability of t with probability 1-(1/2)ln(2)*N/W. Our experimental results on the synthetic data verify the effectiveness of our approach.
Date of Conference: 18-20 December 2010
Date Added to IEEE Xplore: 17 February 2011
Print ISBN:978-1-4244-9482-8

ISSN Information:

Conference Location: Liaoning, China

References

References is not available for this document.