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.
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
Search WWH ::

Custom Search