Information Technology Reference
In-Depth Information
avoid the worst-case update performance of filter insertion, the new filters with new
prefix specifications are inserted into a tuple space. The other new filters without
new prefix specifications are inserted into
BV
. We reuse the bits of previously deleted
filters to restore the storage efficiency. Since no new bit vectors are generated, the
number of updated words remains
P
BV
.
In sum, our update procedures perform filter deletion directly while adaptively select
the data structures for filter insertion. By combining
BV
and
PTSS
, we can avoid the high
cost of filter insertion/deletion in the worst case. Therefore, our update procedures have
superior flexibility because of the unique design of hybrid data structures. Although our
approach would degrade the storage efficiency of
BV
in the case of a heavy load of filter
deletions, it would be reasonable to reconstruct bit vectors with a storage efficiency lower
than a certain threshold due to the infrequency of filter updates [12, 27].
4.3.
Performance Evaluation
In this section we describe how our scheme performs on different filter databases in terms
of speed and storage. The performance evaluation is divided into two stages. The first stage
evaluates the effectiveness of our scheme by presenting the tradeoff between the number of
tuples and BV storage requirement. The second is a performance study that compares the
numerical results of our scheme with several notable algorithms.
4.3.1.
Trade-off Between the Number of Tuples and BV
Storage Requirement
In this section, we show the tradeoff between the number of tuples and BV storage to
illustrate the effectiveness of our scheme. For three real filter databases, Figure 4 depicts
that the required BV storage is reduced by increasing the number of tuples, where the BV
storage is measured in kilobytes. When all the filters are stored in tuple space, the BV
storage is reduced to
zero
. The figure also indicates that for those filter databases with a
large amount of tuples, our scheme is useful since we can restrict most filters to few tuples
and only few filters are stored in bit vectors. Therefore, the search performance of tuple
space search and storage performance of bit vectors could be improved simultaneously.
We further list the required BV storage for different number of tuples in Table 16 for real
databases. The term,
|TS|
, denotes the number of tuples in tuple space. While
|TS=0|
,
our scheme acts as
ABV
; hence, our scheme has the same BV storage as
ABV
. By removing
the filters of the selected tuple from bit vectors in each iteration, the BV storage is reduced
as well. Our results show that we can achieve a significant reduction of BV storage by
removing filters in the first few tuples, which conforms to the observation that the filters in
tuple space are unevenly distributed [33]. Since our scheme of filter categorization prefers
those in the tuple with a large amount of filters and distinct prefixes, we can greatly reduce
the BV storage with only a few tuples to achieve better storage efficiency.
Next, we use twelve synthetic databases for further evaluation. Each database is initial-
ized with 16,000 filters. After removing the redundant filters, the actual number of filters in
each database is usually less than 16,000. Unlike real databases, the synthetic databases re-
quire much large storage for bit vectors. Therefore, we constrain the required BV storage to
