Merging Incomplete IP-Tables

Next: Merging Complete and Incomplete Up: Merging IP-Tables Previous: Merging Complete IP-Tables

Merging Incomplete IP-Tables

Merging two incomplete IP-tables is similar to merging two complete IP-tables: equations (7.14) and (7.16) still apply when using timepoint sets like V'(R,a), V'(Q,b), V''(R) or V''(Q). The difference lies in the different properties of functions like $s_{\scriptscriptstyle R}$ and its respective counterparts or : equation (7.13) does not provide the correct result when s-labelled functions are replaced by their s'-labelled counterparts. Therefore we require another sensible way to calculate the values of .

Let us assume that with x_l-1 < x_l for , and similarly that with y_h-1 < y_h for . The notion behind the definition of was that there are intervals starting within the time range (x_l-1,x_l]. If we make the assumption that these intervals' startpoints' distribution is uniform then there are

intervals in R starting at any point . Thus there are

intervals starting in some range within (x_l-1,x_l] that comprises z timepoints. In particular, this applies to a range (t_j-1,t_j] with as being used in the merging process with t_j-1 and t_j being elements of a merged timepoint set : there are

intervals starting in (t_j-1,t_j]. As the quotient might lead to a non-integer result we have to round the result of (7.17) to get an integer:

(35)

Similarly, we can derive values for the intervals in Q.

The significance of (7.17) is that it allows us to provide an approximation for a with providing the number of intervals that have started since t_j-1<t_j. The novelty is that this is possible for any pair with for some . Consequently, we can calculate a value in the following way: we assume that the merging process has reached a stage such

that the elements
have been processed for some and some ,
that there are dummy values
and that
for some .

The merging process guarantees that

and chooses

(36)

Together with the implicit constraints that x_l-1 < x_l and that y_h-1 < y_h, this implies

Consequently, expression (7.17) can be applied to both and when choosing t_j according to (7.18). Thus it is

The modified version of the merge algorithm is shown in figure 7.18. Its general structure is the same as in the case of two complete IP-tables being merged. However, it uses (7.19) rather than equation (7.13).

**Figure:** The merge algorithm for incomplete IP-tables.

Next: Merging Complete and Incomplete Up: Merging IP-Tables Previous: Merging Complete IP-Tables

Thomas Zurek