Information Technology Reference
In-Depth Information
3.5.4.
Scalability Evaluation
To test the scalability of our algorithm, we use twelve synthetic databases for further eval-
uation. The synthetic databases are generated by
ClassBench
with default settings. Each
database is initialized with 16,000 filters. However, some filters might be redundant, and,
as a result, the actual number of filters in each database is usually less than 16,000. In this
experiment, we set the value of
C
threshold
to 1024K for handling large databases.
We show the storage and speed performance in Table 13 and 14, respectively. The
experimental results of
RFC
are not listed since it takes up too much storage. As shown
in Table 13, the trade-off between storage and speed performance remains in the experi-
mental results. Although our algorithm still requires more storage than
PTSS
, its storage
performance outperforms that of
ABV
and
HyperCuts
in most cases. Moreover, our scheme
provides the best search performance among these schemes. Therefore, by inheriting the
characteristics of
Cross-producting
, our algorithm could achieve superior search perfor-
mance and better scalability.
Table 13. Storage Performance of the Existing Algorithms Using Synthetic Databases.
Synthetic
Original
Our Scheme
Database
Filters
ABV
HyperCuts
PTSS
PLT
NLT
ACL1
15,926
36,523.81
369.18
1,010.32
1,563.63
1,798.65
ACL2
15,447
55,141.81
1,359.68
2,055.93
2,023.45
2,684.40
ACL3
14,729
7,803.02
2,721.50
726.90
3,294.19
3,288.41
ACL4
15,405
13,306.42
1,985.26
793.31
4,996.05
4,046.99
ACL5
10,379
4,545.09
294.45
534.08
635.45
557.82
FW1
14,898
32,494.13
23,883.84
2,205.53
1,932.36
4,427.26
FW2
15,501
39,885.48
10,859.94
1,962.20
1,673.43
2,619.59
FW3
14,297
27,532.10
27,172.06
1,878.96
1,715.81
2,023.88
FW4
13,856
31,231.93
10,717.61
2,855.36
5,096.11
5,227.80
FW5
14,009
26,260.04
19,503.95
1,750.74
1,681.79
2,307.11
IPC1
14,954
16,116.21
3,557.90
716.50
3,260.24
3,199.90
IPC2
16,000
44,405.32
12,450.29
1,893.48
1,076.68
1,076.58
Table 14. Speed Performance of the Existing Algorithms Using Synthetic Databases.
Our Scheme
Synthetic
ABV
HyperCuts
PTSS
PLT
NLT
Database
AMA
WMA
AMA
WMA
AMA
WMA
AMA
WMA
AMA
WMA
ACL1
33.30
44
21.07
56
16.49
32
14.13
18
14.17
17
ACL2
36.55
50
21.72
132
28.49
57
10.37
13
11.6
15
ACL3
52.55
84
22.78
119
41.87
82
19.31
36
19.47
32
ACL4
50.00
84
21.78
92
39.03
77
19.58
35
22.85
40
ACL5
33.72
57
28.28
60
19.18
36
15.28
23
15.22
22
FW1
47.33
56
22.52
221
77.96
113
10.96
13
11.07
13
FW2
33.28
34
21.12
43
11.15
15
7.73
10
7.73
10
FW3
51.71
61
23.47
201
77.28
112
9.97
12
10.09
12
FW4
53.47
87
24.22
639
101.31
187
13.93
16
13.03
14
FW5
51.65
61
23.95
182
106.61
142
9.86
12
9.84
12
IPC1
44.05
65
22.44
87
21.52
44
20.15
33
18.92
30
IPC2
32.34
33
17.14
41
8.36
9
6.08
8
6.08
8
