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

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

0.04

RSBF
SBF

0.02

0

-0.02

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

0.002

RSBF
SBF

0.001

0

-0.001

0 500 1000 1500

Size of stream (×10 3 )

2000 2500 3000

FIGURE 13.6 Convergence rate comparison: real data set.

stabilize even at 3 M records. This demonstrates that RSBF has much better con-
vergence rate than SBF.
Figure 13.7 similarly compares the difference in the number of 1s of successive
number of records for the synthetic data set. With 512 KB memory, the difference in
the number of 1s stabilizes to zero faster for RSBF (shortly after 50 million records)
as compared with SBF, which has not yet stabilized even at 455 million records.

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

0.0001

RSBF
SBF 5e-05

0

-5e-05

-0.0001

5 6 7 8 9 10

0.0001

RSBF
SBF

5e-05

0

-5e-05

-0.0001

45 46 47 48 49 50

0.0001

RSBF
SBF 5e-05

0

-5e-05

-0.0001

450 451 452 453 454 455

Size of stream (×10 6 )

FIGURE 13.7 Convergence rate comparison: synthetic data set.