Advanced Algorithms for Efficient Approximate Duplicate Detection in Data Streams Using Bloom Filters - Large Scale and Big Data: Processing and Management - page 423

The count of 1s can remain the same when the i th element e i in the stream is not
inserted. Further, if the element is inserted, the count of 1s can still remain the same
if a 0 bit is selected to be set to 1 and a 1 bit is reset to 0 during deletion. Also, if the
bit to be set to 1 is already set and that to be reset is already 0, the count of 1s remain
constant. Hence,

λλ λλ ( s −+ + 1 ) ( s

s

− )

Pr() ( λ =− + 1 pp ) (13.13)

i i

2 2

s

Similarly, the count increases by one if a 0 bit is set to 1 and during deletion a 0
bit is selected.

2

+= −

s λ

Pr( λ 1 ) p (13.14)

i

s

Substituting Equations 13.12, 13.13, and 13.14 in Equation 13.11,

2

1 − s

EX () = p λ + 1

+−=+∈

λ ( 1 p ) λ p (13.15)

i i i

s

For any value that λ can assume, 0 ≤ |∈| ≤ 1 and therefore the fraction of 1s, E ( X )/ s in
a buffer is a constant. Moreover, the fraction | p i . ∈| is monotonically decreasing with
increasing values of i , which is the stream length. Hence for large i , ϵ is practically
0. This analysis holds identically for all the remaining ( k − 1) buffers. Therefore ζ is
a constant for RSBF.

By algebraic manipulations, the variance of the count of 1s in RSBF, Var [ X ] is

2 2 2

VarX [] = p ( ββ + −− ≤≤ ( 1 )) p , where 0 β 1 (13.16)

i i

Equation 13.16 implies that the variance of the count of 1s in the Bloom filters for
RSBF is significantly low. For instance, when β = 0.5, the variance is only ( /2 − .

Further, as the length of the stream increases, the variance of the number of ones
decreases. This analysis implies a faster convergence to stability for RSBF with
respect to SBF.

pp
i

)

i

13.6 EXPERIMENTS AND RESULTS

13.6.1 s etting oF P arameters
This section discusses the procedure of setting the parameters for the proposed algo-
rithm to optimize its performance. Given a fixed amount of memory space, M in bits,