Information Technology Reference
In-Depth Information
procedure of tuple selection is not modified. For the filters in Table 1, we can repeat the
procedure of tuple selection based on nested level tuples, as shown in Table 6. In this
example, three tuples are selected,
T
1,3
,T
2,2
and
T
3,1
. Three filters,
F
5
,F
6
and
F
7
, are
inserted into the cross-product table, where
T
0
represents a nested level tuple. Although
the numbers of tuples and cross-product entries are the same as the previous result based
on prefix length tuples, it is usually not the case in practice. Our experimental results
demonstrate that the nested level tuple selection usually has better performance, which is
shown in Section 3.5.
Table 6. The Procedure of Nested Level Tuple Selection for the Filters in Table 1.
The First Iteration. (
P
1
=8,P
2
=7
)
unique(P
T
1
) unique(P
T
2
) P
1
− unique(P
T
1
)
P
2
− unique(P
T
2
)
Tuple
Filters
T
1
,
3
F
1
,F
2
1
2
7
5
T
2
,
2
F
3
,F
4
,F
8
,F
2
2
6
5
T
3
,
3
F
5
1
0
7
7
T
4
,
2
F
6
1
0
7
7
T
2
,
3
F
7
0
0
8
7
T
3
,
1
F
10
,F
11
2
1
6
6
The Second Iteration. (
P
1
=6,P
2
=5
)
unique(P
T
0
1
) unique(P
T
0
2
) P
1
− unique(P
T
0
1
P
2
− unique(P
T
0
2
Tuple
Filters
)
)
T
1
,
3
F
1
,F
2
1
2
5
3
T
3
,
3
F
5
1
0
5
5
T
4
,
2
F
6
1
0
5
5
T
2
,
3
F
7
0
0
5
5
T
3
,
1
F
10
,F
11
2
1
4
4
The Third Iteration. (
P
1
=5,P
2
=3
)
unique(P
T
1
) unique(P
T
2
) P
1
− unique(P
T
1
)
P
2
− unique(P
T
2
)
Tuple
Filters
T
3
,
3
F
5
1
0
4
3
T
4
,
2
F
6
1
0
4
2
T
2
,
3
F
7
0
0
4
3
T
3
,
1
F
10
,F
11
2
1
3
2
Although nested level tuple selection has better performance, adopting nested level tu-
ple would incur an extra problem in supporting incremental updates. Unlike prefix length
tuples, the combination of prefix nested levels of each filter correlates to the other filters.
For the case of inserting a new filter with a new prefix specification or deleting an existing
filter with at least one unique prefix specification, the prefix nested level of the existing
prefixes might be changed. In the worst case, the prefix nested levels of all the filters are
modified and the tuple space must be reconstructed. We address the issue of supporting
incremental updates in Section 3.4..
3.3.3.
Adaptive Implementation of Cross-product Table
As mentioned above, the cross-product table can be implemented in a direct access array or
a hash table. For the example in Table 6, there are three filters,
F
5
,F
6
and
F
7
, inserted into
the cross-product table. The array-based cross-product table requires
six
entries,
h0∗, 1∗i
,
