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

|Data set| = 1 × 10 9 , Memory = 512 MB, reshold FPR = 0.1

0.5
0.4
0.3

RSBF
SBF

0.2

0.1
0

|Data set| = 1 × 10 9 , Memory = 512 MB, reshold FPR = 0.1

0.2

RSBF
SBF

0.16
0.12
0.08
0.04
0

0 200 400 600 800 1000

Size of stream (×10 6 )

FIGURE 13.3 FPR comparison.

by a significant margin. For 2 KB memory, RSBF has a stable FNR of 10%, which
is around 1.5× better as compared with SBF, which produces a stable FNR of 15%.
With increase in memory the performance gap between the two further increases in
favor of RSBF. Observe that for 4 KB memory, RSBF attains a stable FNR of nearly
12%, which is around 1.83× better than that of SBF with a stable FNR of 22%.
Figure 13.5 also compares the FNR between RSBF and SBF, albeit on synthetic
data set having 1B records and FPR threshold of 0.1. For both RSBF and SBF, the
FNR again initially increases but then stabilizes. For both 128- and 512-MB mem-
ory, RSBF similarly outperforms SBF. For 128-MB memory, RSBF has a stable
FNR of 22%, which is around 1.73× better compared with SBF, which has an FNR of
38%. With 512-MB memory, RSBF attains a stable FNR of 7%, around 1.86× better

|Data set| = 3,367,020, Memory = 2 KB, reshold FPR = 0.1

RSBF
SBF

0.2
0.15
0.1
0.05

0

|Data set| = 3,367,020, Memory = 4 KB, reshold FPR = 0.1

0.032
0.024
0.016
0.008
0

RSBF
SBF

0 500 1000 1500 2000 2500 3000

Size of stream (×10 3 )

FIGURE 13.4 FNR comparison: real data set.