Next: Experimental Evaluation Up: Partitioning Strategies Previous: Variations

Black-Out Preprocessing Strategy

The underflow partitioning strategies do not pay any attention to the number of overlapping intervals when they choose a breakpoint. The incorporation of a mechanism that minimises the total number of overlaps led to the minimum-overlaps strategy. However, the latter suffers from an algorithmic complexity of O(N²) which is prohibitive for the high values of N that can be expected in practice.

In this section, we describe an alternative, but heuristical technique to reduce the number of overlaps. The idea is the following: figure 9.13 shows a typical example of a function $o_{\scriptscriptstyle R}(t)$ .The general goal is to find breakpoints p_k for which is low, i.e. somewhere in the valleys formed by $o_{\scriptscriptstyle R}(t)$ . Therefore one could restrict a strategy's choice to those timepoints, i.e. `cut out' the unfavourable bits of the time domain.

In practical terms, we can do this in the following way: the IP-table I(R) is scanned and all with are blacked out. Y is called the black-out threshold. This process creates a new IP-table and is very similar to the condensation process that was described in section 7.3.3. Figure 9.14 summarise the basic algorithm for this black-out strategy.

Figure 9.15 shows the result of the black-out strategy when it is applied to $o_{\scriptscriptstyle R}(t)$ for (week-lifespan; see section 7.3.2) with

i.e. the average of $o_{\scriptscriptstyle R}$ . The parts of V(R) that are cut out are marked as black bars on the time axis. If the maximum load X (X_R, X_Q respectively) in an underflow strategy is high enough then breakpoints can be chosen to put all the tuples that are valid within one of the time periods marked by the bars to be put into one fragment. If this is not the case for only one of the `bar-periods' then an underflow strategy cannot find an allowable partition because of the black-out preprocessing. Such a situation can arise if the black-out preprocessing creates long `bar-periods', for example as shown in figure 9.16 for a different $o_{\scriptscriptstyle R}(t)$ . There are two possibilities to shorten a long `bar-period':

The threshold Y can be increased.
The `bar-period' is split by admitting some t_j that fall into this period despite the fact that .

The first possibility is not very attractive because it is difficult to determine by how much Y should be increased in order to guarantee an underflow strategy to be able to find a breakpoint when it is reaches the maximum load X. Apart from that the advantages of the black-out strategy are gradually lost when increasing Y.

The second possibility suggests that a long `bar-period' is split into pieces that can be handled by an underflow strategy. Such pieces can be created by checking the load that is created by cutting out timepoints if . If such a load would exceed a certain threshold Y' then a t_j is inserted into even if . This advanced version of the black-out strategy is summarised in figure 9.17. An example of two additional timepoints being admitted within the `bar-period' is shown in figure 9.18.

**Figure:** The function $o_{\scriptscriptstyle R}(t)$ for the temporal relation (week-lifespan; see section 7.3.2).

**Figure:** Basic black-out preprocessing for I(R).

**Figure:** Black-out strategy applied to $o_{\scriptscriptstyle R}(t)$ of figure 9.13.

**Figure:** Black-out strategy applied to $o_{\scriptscriptstyle R}(t)$ for (day-lifespan; see section 7.3.2).

**Figure:** Advanced black-out preprocessing for I(R).

**Figure:** Advanced black-out strategy applied to $o_{\scriptscriptstyle R}(t)$ for (see section 7.3.2).

Next: Experimental Evaluation Up: Partitioning Strategies Previous: Variations

Thomas Zurek