Information Technology Reference

In-Depth Information

(

(

):.

):.

):.

):.

):.

):.

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

,WHUDWLRQ

,WHUDWLRQ

(a) Prefix Length Tuples

(b) Nested Level Tuples

Figure 2. The size of cross-product table in each iteration of tuple selection for FW1.

(

(

,3&.

,3&.

,3&.

,3&.

,3&.

,3&.

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

(

,WHUDWLRQ

,WHUDWLRQ

(a) Prefix Length Tuples

(b) Nested Level Tuples

Figure 3. The size of cross-product table in each iteration of tuple selection for IPC1.

3.5.2.

Comparative Analysis of Our Refinements

In this subsection, we show the performance of our scheme with the first and third refine-

ments presented in Section 3.3.. We fix the value of
C
threshold
to 64K based on previous

evaluation. Moreover, we only use the array-based cross-product tables. To test the re-

finement of generating multiple cross-product tables, we use two different configurations

to evaluate our scheme. The first configuration is a basic scheme which only generates one

cross-product table, and the other uses the refinement to generate multiple cross-product ta-

bles. We show the numerical results of our scheme with both configurations in Table 7
∼
9.

Table 7 and 8 show the storage performance of two configurations for PLT and NLT, respec-

tively. With the refinement of generating multiple cross-product tables, the number of tuples

could be significantly reduced, regardless PLTs or NLTs. Although the required storage is

increased since cross-product tables usually store redundant entries, the search performance

of our scheme is improved with less data structures, as shown in Table 9. Therefore, there

exists a tradeoff between storage performance and the number of generated cross-product

tables.

Next, we consider the influence of cross-product table implementations on the storage