Database Reference
In-Depth Information
TABLE 13.3
Data Set of 10 M Elements (49% Distinct)
Space (in bits)
SBF% FNR
RSBF% FNR
SBF% FPR
RSBF% FPR
16,384
88.83
87.52
11.08
12.464
262,144
88.11
86.89
10.86
12.12
4,194,304
77.33
77.73
7.822
7.914
distinct elements in the stream are roughly equal. However, with 10 M records, and
percentage of distinct elements lesser than 49%, RSBF has better FNR than SBF as
exhibited in other data set values given below.
Table 13.4 presents the FNR and FPR with 695 M records and 15% distinct records
while varying memory used for the underlying Bloom filter data structure from 262 K
bits to 4.2 B bits. Here, FNR achieved by RSBF is better than SBF, and this gap is higher
when larger memory is used. At around 67 M bits, RSBF has FNR of 58.3%, while SBF
has FNR of 82.48%; while at 1 B bits, RSBF has FNR of 23.12%, while SBF has FNR
of 37.79%. However, the FPR values remain similar across both these algorithms.
Table 13.5 presents the FNR and FPR with 1 B records and 10% distinct records
while varying memory used for the underlying Bloom filter data structure from 262
K bits to 4.2 B bits. Here again, FNR achieved by RSBF is better than SBF. At
around 67 M bits, RSBF has FNR of 58%, while SBF has FNR of 82%; while at 1
B bits, RSBF has FNR of 23.47%, while SBF has FNR of 37%. The ratio of FNR
between SBF and RSBF increases to 1.74× at 4.2 B bits. However, the FPR values
remain similar across both these algorithms. This demonstrates that RSBF has con-
sistent superior FNR compared with SBF, with FPR values close to SBF though
sometimes higher by a small margin.
TABLE 13.4
Data Set of 695 M Elements (15% Distinct)
Space (in bits)
SBF% FNR
RSBF% FNR
SBF% FPR
RSBF% FPR
262,144
88.86
87.47
12.51
11.1
67,108,864
82.48
58.2818
8.3
8.4
1,073,741,824
37.79
23.12
0.742
0.89
4,294,967,296
12.94
7.37
0.069
0.072
TABLE 13.5
Data Set of 1 B Elements (10% Distinct)
Space (in bits)
SBF% FNR
RSBF% FNR
SBF% FPR
RSBF% FPR
67,108,864
82.58
67.66
8.262
10.262
1,073,741,824
38.17
23.47
0.7
0.83
4,294,967,296
13.163
7.53
0.0634
0.0664
 
Search WWH ::




Custom Search