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