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

Hence, RSBF tends to observe a constant FNR much lower than that of SBF as the
stream length increases. Readers can find the detailed proof in [15].

13.5.1.3 Stability Factor
SBF introduced the concept of stability of a Bloom filter, whereby the number of
1s or 0s in the structure become constant after a time period. It should be noted
that as the FPR and FNR is dependent on the 1s and 0s present in the Bloom fil-
ter, respectively, stability of their counts nearly guarantees constant performance
of the data structure. In the following analysis, RSBF structure is shown to attain
stability much earlier compared with SBF. The complete proof was presented
in [15].
The following theorem bounds the expected fraction of 1s in the RSBF. The frac-
tion of 1s (or 0s) is important because the false-positive rate (or FNR) is dependent on
the fraction of 1s (or 0s). The faster stability is attained, the better will be the overall
performance of the structure. Let E ( X ) be the expected count of 1s in one of the k
Bloom filters of RSBF; then the expected fraction of 1s in RSBF, (ζ) can be approxi-
mated by EX
s

() , where s is the size of each Bloom filter (in bits).

Theorem 1.5.1

Given an RSBF with ks bits, at any iteration i, the expected fraction of 1s (ζ) is a
constant , ∀ i > s .

Proof

Let λ denote the count of 1s in a Bloom filter after iteration ( i − 1). The analysis is
performed on a single Bloom filter as other Bloom filters (and the operations on
them) are identical. According to Algorithm 13.2, the count of 1s can either increase
or decrease by one only or remain the same in iteration i. Therefore, the expected
count of 1s can be expressed as

E ( X ) = (λ − 1) Pr(λ − 1) + λ Pr(λ) + (λ + 1) Pr(λ + 1) (13.11)

since Pr(λ ± j ) = 0, where j ≥ 2.
The count of 1s in a Bloom filter can decrease by one when an element is inserted
and the bit selected to be set was already set to 1, and during deletion, 1 of the set bits
is reset to 0. The probability is given by

λλ ( − 1 )

Pr( λ −= 1 ) p (13.12)

i

2

s