Information Technology Reference

In-Depth Information

Next, we construct searchable data structures for the two categories of filters. For the

filters stored in bit vectors,
d
one-dimensional data structures of the best matching prefixes

(BMPs) are built. Each prefix node is associated with a bit vector whose length is equal

to the number of filters in the category. We also insert an aggregate bit vector for each bit

vector to further improve its speed [12]. The filters of the other category are inserted into

a tuple space. We use
PTSS
[8] to search these filters since it also uses BMP searches to

decide which tuples are probed. We can combine the BMP searches of both categories to

facilitate faster search performance.

The search procedure acts as follows. First,
d
one-dimensional searches are carried

out to determine the BMP of each field. Subsequently, the corresponding aggregated bit

vectors are accessed to decide which words of the matching bit vectors are fetched. The

tuple pruning information is also extracted from the BMP, and those tuples which appear

in
d
BMPs are probed for a possible filter match. The tuple pruning information can be

represented in the form of bit vectors. Combining the results of both searches can derive all

the matching filters.

4.2.

Incremental Updates

A filter update can be either a deletion or an insertion. For our scheme, both types of updates

would affect one of the data structures, (
PTSS
or
ABV
). Both data structures also include

d
BMP data structures. Since the update procedures for various BMP data structures have

been studied extensively, we put our emphasis on the update procedures of the multidimen-

sional data structures. There are two types of updates in our scheme, one for tuple space and

the other for bit vectors. Since the update procedures for tuple space have been presented

in the previous section, we describe the update procedures of bit vectors in the following.

1.
Delete Filter from BV
: Deleting a filter from
BV
is more difficult than from tuple

space. Due to the property that a value matching to a prefix,
p
, also matches to
p
's

subprefixes, the corresponding bit vector of each prefix must include the same set bits

as those of its subprefixes [12]. Therefore, updating the bit vector of prefix, “
∗
”, will

affect all the bit vectors of the same field and every bit in bit vectors are updated in

the worst case. To alleviate the update cost, we merely set the bit corresponding to

the deleted filter to
zero
. Therefore, at most
P
BV
words are updated for each filter

deletion, where
P
BV
denotes the number of distinct prefixes for the filters stored in

bit vectors. Since our scheme of filter categorization has reduced the value of
P
BV
to

minimize the storage of bit vectors, the update cost is reduced as well. We note that

our approach would degrade the storage efficiency; however, the storage efficiency

can be restored by combining the procedure of filter insertion listed below.

2.
Insert Filter into BV
: In [12], the authors have reported that inserting a filter into

bit vectors is slow in the worst case, but fast on the average. The reason for the

slow updates comes from inserting a new filter which has at least one
wildcard
field

since all bit vectors of these
wildcard
fields must be updated. In addition, inserting

filters with new prefix specifications also requires the generation of
d
new bit vectors.

Hence, the number of maximum updated words is
(P
BV
+ dN
BV
/B)
, where
N
BV

denotes the number of filters stored in
BV
and
B
represents the memory width. To